1. The concept of linear tables
Linear tables are the most common and simplest type of data structure. In short, a linear list is a finite sequence of n data elements. Its general description is:
A data element usually contains multiple data items, in which case each data element is called a record, and a linear table with a large number of records is called a file.
The Chinese zodiac, for example, is a linear list:
In slightly more complex linear tables, a data element can consist of several data items.
For example, a student list containing the student id number, name, age, gender, etc.
From the above example, you can see that each data element has the same properties:
- That is, each data element can have at most one immediate precursor element, and each data element can have at most one immediate successor element
- Only the first data element has no immediate predecessor element, and the last data element has no immediate successor element
A linear table is a flexible data structure. Its length can be increased or shortened as required, and different operations can be performed on the data elements of a linear table (such as accessing data elements, inserting and deleting data elements, etc.).
The storage structure of linear list is divided into sequential storage and chain storage.
2. Sequence table
Sequential storage of linear tables, also known as vector storage, can also be said to be one-dimensional array storage. The physical order of nodes in a linear table is exactly the same as the logical order, which is called vector storage (generally refers to one-dimensional array storage).
The sequence table storage structure is as follows:
The position of the first data element in a linear table is usually called the starting position or base address.
Adjacent elements in a table have adjacent storage locations.
2.1 Initialize the sequence table
A sequentially allocated linear table can be described directly using a one-dimensional array as:
type arraylist[]; // The type of type is determined based on site requirements
Copy the codeIn Java, since all classes are subclasses of Object, we can declare an Object array:
// An array of elements
private Object list[];
Copy the codeThis code is just a declaration to apply an array; it has not yet allocated space to the array, so it cannot be accessed. Only after the array is initialized and memory resources are allocated, can the elements in the array be used and accessed.
// Default capacity
private static int defaultSize=10;
// Table length: the actual number of stored elements
private int length;
public SequenceList(a) {
// Initialize the array and declare the memory resources
this.list=new Object[defaultSize];
}
Copy the code
2.2, add
In this method, we dynamically expand the array. When the array runs out (size>=defaultSize), we create a new array with twice the size of the original array and move the elements from the original array to the new array. The schematic diagram is as follows
The insert operation moves all subsequent elements of the operation position backward.
/** * add element *@paramItem data element *@paramThe index position * /
public void add(Object item,int index){
//list[0]=item;
if (index>=size||index<0){
System.out.println("index can not be this value");
return;
}
// Array expansion
if (size>=defaultSize){
defaultSize=2*defaultSize;
// Double the size of the array
Object[] newArray=new Object[defaultSize];
for (int j=0; j<list.length; j++){ newArray[j]=list[j]; } list=newArray; }/ / insert
for (intk=size; k>=index; k--){// All elements move back one bit
list[k+1]=list[k];
list[index]=item;
}
size++;
}
Copy the code
Time complexity analysis
- Array capacity
In an array expansion operation, you need to copy the old array to the new one in order n time.
- The insert
The main time consumption of an insert operation is to move an array element, which is at worst list.length and at best 0. The time is order n.
2.3, delete,
/** * Removes the data element *@param index
*/
public void remove(int index){
if (index>list.length-1||index<0){
System.out.println("index can not be this value");
return;
}
// All elements move forward
for (intk=index; k<list.length; k++){ list[k]=list[k+1];
}
size--;
}
Copy the codeTime complexity analysis
The operation of deleting is similar to that of adding. Deleting moves the element forward, at best 0 times, at worst list.length times, in order of O(n).
2.4, delete,
/** * takes the data element *@param index
* @return* /
public Object get(int index){
return list[index];
}
Copy the codeTime complexity analysis
Data elements can be obtained directly according to the array subscript, there is no element movement, so the time complexity is O(1).
2.5, update,
/** * Updates the data element *@param o
* @param index
*/
public void set(Object o,int index){
if (index>=size||index<0){
System.out.println("index can not be this value");
return;
}
list[index]=o;
}
Copy the codeTime complexity analysis
The update is similar to the above fetch, with O(1) time.
2.6 AraayList and Vector
Java itself provides implementations of sequential tables: java.util.arrayList and java.util.vector.
In fact, the java.util.Arraylis implementation uses some Native methods to manipulate memory more efficiently. ArrayList source code: ArrayList source read notes
Java.util. Vector is a legacy class and is not recommended.
3, the linked list
The characteristics of the order of the linear table storage structure is the logical relationship between the adjacent two elements in the physical location or adjacent, so random access element is simpler, but this feature also makes the insert and delete elements, caused a large number of data elements move, if using static allocation of storage unit at the same time, also takes continuous storage space in advance, May cause space waste or space overflow. Chained storage does not require logically adjacent data elements to be physically adjacent, so it does not have the disadvantages of sequential storage structures, but it also loses the advantages of random access.
3.1. One-way linked lists
A single necklace list is the simplest linked list. Each node contains two parts, data field (data) and pointer field (Next). The data field stores the value of the data element, and the pointer field stores the address of the next adjacent node.
A unidirectional linked list is a chain storage structure in which the pointer field of a node has only one representation along the same direction. The schematic diagram is as follows:
3.1.1. Node Classes
Because a node is a separate object, you need a separate node class. Here is the definition of a node class:
/** * Node class */
class Node<T>{
private Object data; / / data
private Node next; // Next node
Node(Object it,Node nextVal){
this.data=it;
this.next=nextVal;
}
Node(Node nextVal){
this.next=nextVal;
}
Node(){}
public Object getData(a) {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext(a) {
return next;
}
public void setNext(Node next) {
this.next = next; }}Copy the code
3.1.2 single-linked list classes
We need to define a single linked list class with some basic attributes and constructors:
public class SinglyLinkedList<T> {
private Node head; / / head node
private Node tail; / / end nodes
private int size; // List length
public SinglyLinkedList(a){
head=null;
tail=null;
size=0; }}Copy the code
3.1.2. Get elements
Here we implement methods to get elements by ordinal and get element data fields:
/** * get the element *@param index
* @return* /
public Node getNodeByIndex(int index){
if (index>=size||size<0){
System.out.println("Out of bounds");
return null;
}
Node node=head;
for (int i=0; i<size; i++,node=node.next){if (index==i){
returnnode; }}return null;
}
/** * get the data element data field *@param index
* @return* /
public Object get(int index){
return getNodeByIndex(index).getData();
}
Copy the codeTime complexity Analysis this is a loop, starting at the head and then looking backwards one by one until the index element is found, with time complexity O(n).
3.1.3 Insert elements
There are three insertion methods:
- First insert method
The head insertion method is shown as follows:
/** ** header insertion method *@param element
*/
public void addHead(T element){
head=new Node(element,head);
// If an empty list is inserted, the last node is the first node
if(tail==null){
tail=head;
}
size++;
}
Copy the code- The tail insertion method
Tail insertion is similar to head insertion
/** ** insert *@param element
*/
public void addTail(T element){
// If the table is empty
if (head==null){
head=new Node(element,null);
tail=head;
}else {
Node node=new Node(element,null);
// The old tail points to the inserted node
tail.setNext(node);
// The tail moves backwards
tail=node;
}
size++;
}
Copy the code- Intermediate insertion method
Insert in the middle, change the point of the previous node and the point of the insert element, schematic diagram is as follows:
/** * Inserts the data element * at the specified position@param element
* @param index
*/
public void add(T element,int index){
if (index>size||size<0){
System.out.println("Out of bounds");
return;
}
if (index==0){
addHead(element);
}else if (index==size){
addTail(element);
}else{
//index is the front node of the position
Node preNode=getNodeByIndex(index-1);
//index position node
Node indexNode=getNodeByIndex(index);
// The inserted node is followed by the node at the index position before execution
Node insertNode=new Node<T>(element,indexNode);
// Forward nodes point to inserted nodespreNode.setNext(insertNode); size++; }}Copy the code
3.1.4. Delete elements
Delete the element, find the target element, and change the direction of the previous node.
/** * delete element *@param index
*/
public void remove(int index){
if (index>size||size<0){
System.out.println("Out of bounds");
return;
}
// To remove the head node, simply set the head node to the next node
if (index==0){
head=head.next;
} else {
// The node to be deleted
Node indexNode=getNodeByIndex(index);
// The previous node of the deleted node
Node preNode=getNodeByIndex(index-1);
// The front node points to the back node of the destination node
preNode.setNext(indexNode.next);
// If the last element is deleted, the end node moves forward
if(index==size-1){
tail=preNode;
}
}
size--;
}
Copy the code
3.2. Circular linked lists
Cyclic linked list is also called cyclic linear linked list, its storage structure is basically the same as unidirectional linked list.
It is improved on the basis of unidirectional linked list and can solve the shortcoming of unidirectional search in unidirectional linked list. Because one-way linked lists can only follow one direction, not reverse lookup, and the value of the pointer field of the last node is null, to solve the shortcomings of one-way linked lists, we can use the null pointer of the last node to complete the forward lookup. The null of the pointer field of the last node of a single linked list is changed to point to the first node, which logically forms a loop. The storage structure is called one-way circular linked list. The schematic diagram is as follows:
Compared with single linked list, its advantage is that it can know the address of any node and find all nodes in the linked list (circular search) without increasing any space.
An empty circular linear linked list can, by definition, be the same or different from a one-way linked list. The condition for judging the end node of a circular linked list is different from that of a unidirectional linked list. The difference lies in that a unidirectional linked list is to judge whether the pointer field of the end node is empty, while the condition for judging the end node of a circular linear linked list is that the value of the pointer field points to the head node.
The insertion and deletion operations of circular linked lists are basically the same as those of unidirectional linked lists, but the discriminant conditions are different when searching. However, the danger of this kind of circular linked list is that the list has no obvious end, which may make the algorithm into an infinite loop.
3.3. Double linked lists
In the previous single-linked list, the list has only one pointer to the next node, while the double-linked list has one more pointer to the previous node. This allows you to access the previous node from any node, as well as the latter, and the entire list.
3.3.1. Node Classes
In contrast to a single linked list, forward nodes need to be added to the node class.
/** * Node class */
class Node<T>{
private Object data; / / data
private Node next; // Next node
private Node prev; // Last node
Node(Node prevVal,Object it,Node nextVal){
this.data=it;
this.next=nextVal;
this.prev=prevVal;
}
Node(Node prevVal,Node nextVal){
this.prev=prevVal;
this.next=nextVal;
}
Node(){}
public Object getData(a) {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext(a) {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node getPrev(a) {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev; }}Copy the code
3.3.2 Double-linked list classes
Defines a double-linked list class that contains a constructor and some basic properties.
public class DoublyLinkedList<T> {
private Node head; / / head node
private Node tail; / / end nodes
private int size; // List length
public DoublyLinkedList(a){
head=null;
tail=null;
size=0; }}Copy the code
3.3.3. Get elements
The implementation of bidirectional linked list query node is basically the same as one-way linked list, as long as the direction of next to find the node can be.
/** * get the data element *@param index
* @return* /
public Node getNodeByIndex(int index){
if (index>=size||size<0){
System.out.println("Out of bounds");
return null;
}
Node node=head;
for (int i=0; i<=size; i++,node=node.next){}return node;
}
/** * get the data element data field *@param index
* @return* /
public Object get(int index){
return getNodeByIndex(index).getData();
}
Copy the code
3.3.4 Insert elements
- Head insertion: The new node forward points to NULL, the successor points to the head node, the head node forward points to the new node
/** ** header insertion method *@param element
*/
public void addHead(T element){
Node node=new Node(null,element,null);
// If the table header is empty, use the new node as the head node
if (head==null){
head=node;
}else{
// The new node then points to the head node
node.next=head;
// The header points forward to the new node
head.prev=node;
// Reassign the headerhead=node; }}Copy the code- Tail insertion method: the successor of the tail node points to the new node, and the new node points to the tail node
/** ** insert *@param element
*/
public void addTail(T element){
/ / the new node
Node node=new Node(null,element,null);
// If the table header is empty, use the new node as the head node
if (head==null){
head=node;
}else{
// The successor of the tail points to the new node
tail.next=node;
// The forward direction of the new node points to the end node
node.prev=tail;
// The end node is reassigned
tail=node;
}
size++;
}
Copy the code- Intermediate insertion method: insert data elements according to the index, find the inserted position of the element, change the forward direction of the element, and the subsequent direction of the forward element
/** * inserts * from the specified position@param element
* @param index
*/
public void add(T element,int index){
if (index>size||size<0){
System.out.println("Out of bounds");
return;
}
if (index==0){
addHead(element);
}else if (index==size){
addTail(element);
}else{
// Insert the node at the position
Node indexNode=getNodeByIndex(index);
// Insert position forward node
Node preNode=indexNode.prev;
// New node, set the forward and successor of the new node
Node node=new Node(preNode,element,indexNode);
// Insert the position node forward to the new node
indexNode.prev=node;
// The former node then points to the new nodepreNode.next=node; }}Copy the code
3.3.5. Delete elements
To delete an element, you only need to find the deleted element, change the successor of the forward node, and the forward of the successor node
/** * delete element *@param index
*/
public void remove(int index){
if (index>size||size<0){
System.out.println("Out of bounds");
return;
}
// The deleted node
Node node=getNodeByIndex(index);
/ / before
Node preNode=node.prev;
/ / the subsequent
Node nextNode=node.next;
/ / end nodes
if (nextNode==null) {// The forward node is set to NULL
preNode.next=null;
// The end node is reassigned
tail=preNode;
}else if(node.prev==null) {/ / head node
// The forward trend of subsequent nodes is null
nextNode.prev=null;
// Reassign the header
head=nextNode;
}else{
// The successor of the forward node points to the successor node
preNode.next=nextNode;
// The forward of the successor node points to the forward nodenextNode.prev=preNode; }}Copy the code
Bidirectional circular linked lists
The algorithms of bidirectional cyclic lists are almost the same as those of bidirectional cyclic lists. The difference is the same as that of single and one-way cyclic lists, that is, the conditions for judging the end nodes are different.
- The trailing pointer field of the bidirectional linked list is empty, while the trailing pointer field of the bidirectional cyclic linked list points to the first node.
- In reverse lookup, the forward pointer field of the head node of the bidirectional linked list is empty, while the forward pointer field of the head node of the bidirectional cyclic linked list points to the last node.
3.3, LinkedList
In Java collections, LinkedList is implemented based on bidirectional linked lists (previously bidirectional circular lists).
Specific source analysis can be viewed: LinkedList source read notes
4, summarize
Reference:
[1] : Deng Junhui. Data Structure and Algorithm [2] : Wang Shimin et al. Data Structure and Algorithm Analysis [3] : “Data-structures -and Algorithm-In-Java -6th-Edition” [4] : Yan Weimin, Wu Weimin. “Data Structures” [5] : Cheng Jie, Ed. “Big Talk data structure” [6] : Data structure know not know not series – linear table sequence and chain storage [7] : linear table and its algorithm (Java implementation) [8] : Data structure and algorithm Java edition – single linked list implementation [9] : Data structure and algorithm — single linked list [10] : “My first algorithm book” [11] : watch animation easy to understand “linked list” implementation “LRU cache elimination algorithm” [12] : Java implementation of bidirectional linked list [13] : Bidirectional linked list implementation (Java) [14] : bidirectional linked list and bidirectional circular linked list