 # Data structures - Linked lists

Posted on Dec. 3, 2022, 7:52 a.m. by Cassandra Gallagher
Category: The back-end

This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

# The list

``Physical storage unit not continuous, sequential storage structure, the logical sequence of data elements by pointer address list implementation Each element contains at least two nodes, one is a data storage element domain (memory), and the other is a pointer to the next node address domain chain table there are two main advantages: First, the time complexity of insert and delete operation is O(1). Second, it can dynamically change the sizeCopy the code``

``Linked list is a very common data structure, do not need to initialize the capacity, you can add or subtract elements arbitrarily; When adding or deleting an element, you only need to change the pointer field of the node before and after the two elements to point to the address, so adding and deleting quickly;Copy the code``

``Because contains a large number of pointer fields, occupies a large space; Finding an element requires traversing a linked list to find it, which is time-consumingCopy the code``

## structure

``A unidirectional linked list (singly linked list) is a type of linked list that consists of nodes, each containing a pointer to the next nodeCopy the code``
``````/** * Node information */
public class OneWayNodeT {
private T  data; // Node data
private OneWayNodeT next; // Next node address
public OneWayNode(T data) {
this.data = data;
}
public OneWayNodeT getNext(a) {
return next;
}
public void setNext(OneWayNodeT next) {
this.next = next;
}
public T getData(a) {
return this.data;
}
public void setData(T data) {
this.data = data; }}public class OneWayLinkeListT {
private static OneWayNode endNode = null;	/ / end nodes
private static int size = 0;		// List length
public void show(a) { / / traverse
while(item! =null) {
System.out.print(item.getData() + ""); item = item.getNext(); }}}Copy the code``````

There are three scenarios for adding operations

• Head add: first set the head node to the next node of the new node, then set the new node to the head node
• Tail-add: Directly sets the next node of a tail-node to the new node
• Add in the middle: first find the location to add, and then set the next node of the current node to the new node, and then the next node of the new node to the current node
``````public static void main(String[] args) {
}
public void add(T data, int index) {
if (index  this.size) {
System.out.println("Subscript out of bounds!");
}
this.size ++;
OneWayNode node = new OneWayNodeT(data);
OneWayNode item = null;
this.endNode = node;
} else {
}
return;
}
if (index == this.size-1) { // Add at the end
item = this.endNode;
item.setNext(node);
this.endNode = node;
return;
}
int x = 0;
OneWayNode lastNode = null;
while(item! =null) {	// Add intermediate
if (x==index) {
lastNode.setNext(node);
node.setNext(item);
break; } lastNode = item; item = item.getNext(); x++; }}Copy the code``````

#### Manual code - modified

Modify: Find the location of the node to be modified, set the next node of the current node to the new node, and set the next node of the current node to the next node of the new node

Finally, you have to decide whether it's head or tail

``````public static void main(String[] args) {
}
public void update(T data, int index) {
if (index  this.size) {
System.out.println("Subscript out of bounds!");
}
OneWayNode node = new OneWayNodeT(data);
int x = 0;
OneWayNode lastNode = null;
while(item! =null) {	/ / modify
if (x==index) {
lastNode.setNext(node);
node.setNext(item.getNext());
if (index == 0) {
}
if (index == this.size - 1) {
this.endNode = node;
}
break; } lastNode = item; item = item.getNext(); x++; }}Copy the code``````

#### Hand code - delete

There are also three cases of deletion

• Tail deletion: We need to start from the head node to traverse the whole list, traversing to the last node, the last node of the last node of the next node data set to NULL;
• Intermediate deletion: Need to start from the node to traverse the list, find the node to be deleted, the next node data of the previous node is set to the next node data of the current deleted node
• The three types of deletion can share the same method, the first node can be obtained by deleting the head, the middle and tail deletion need to traverse the list, and the tail need to traverse the whole list O(∩_∩) haha ~
``````public static void main(String[] args) {
}
public void delete(T data) {
OneWayNode lastNode = null;
while(item! =null) {
if (item.getData().equals(data)) {
if (lastNode==null) {
break;
}
lastNode.setNext(item.getNext());
if (item.getNext() == null) {
this.endNode = lastNode;
}
break; } lastNode = item; item = item.getNext(); }}Copy the code``````

#### Hand code - query

According to the index query need to traverse the list, according to the memory query also need to traverse the list (^▽^)

``````public static void main(String[] args) {
}
public void get(int index) {
int x = 0;
while(item ! =null) {
if (x==index) {
System.out.println(item.getData());
break; } item = item.getNext(); x++; }}Copy the code``````

``The double linked list is also composed of nodes. Each data node of the double linked list has two Pointers, respectively pointing to the direct successor and the direct precursor. Two Pointers are a waste of space, but can be traversed in both directions, improving the flexibility of the listCopy the code``
``````public class TwoWayNodeT {
private T  data;	// Node information
private TwoWayNodeT next; // Next node
private TwoWayNodeT last; // Last node
public TwoWayNode(T data) {
this.data = data;
}
public TwoWayNodeT getNext(a) {
return next;
}
public void setNext(TwoWayNodeT next) {
this.next = next;
}
public TwoWayNodeT getLast(a) {
return last;
}
public void setLast(TwoWayNodeT last) {
this.last = last;
}
public T getData(a) {
return this.data;
}
public void setData(T data) {
this.data = data; }}public class TwoWayLinkeListT {
private static TwoWayNode endNode = null;	/ / end nodes
private static int size = 0;				// List length
}
Copy the code``````

There are also three cases of the add operation

• Tail-adding: Different from single-way linked lists, the next node of a tail-node is directly set to the new node, and then the new node sets the previous node to the previous tail-node
``Set the next node of the last node to the new node, set the last node of the new node to the last node, set the next node of the next node to the next node, set the last node of the next node to the new node, set the next node of the next node to the new node, set the next node of the next node to the new nodeCopy the code``
``````public void add(T data, int index) {
if (index  this.size) {
System.out.println("Subscript out of bounds!");
}
this.size ++;
TwoWayNode node = new TwoWayNodeT(data);
TwoWayNode item = null;
this.endNode = node;
} else {
item.setLast(node);
node.setNext(item);
}
return;
}
if (index == this.size-1) { // Add at the end
item = this.endNode;
item.setNext(node);
node.setLast(item);
this.endNode = node;
return;
}
int x = 0;
while(item! =null) {	// Add intermediate
if (x==index) {
item.getLast().setNext(node);
node.setLast(item.getLast());
node.setNext(item);
item.setLast(node);
break; } item = item.getNext(); x++; }}Copy the code``````

#### Manual code - modified

The modification logic is the same as the single-direction linked list, and the last step is added: the last node of the current modified node points to the node in the previous position

Finally, you have to decide whether it's head or tail

``````public void update(T data, int index) {
if (index  this.size) {
System.out.println("Subscript out of bounds!");
}
TwoWayNode node = new TwoWayNodeT(data);
int x = 0;
TwoWayNode lastNode = null;
while(item! =null) {	/ / modify
if (x==index) {
item.getLast().setNext(node);
node.setLast(item.getLast());
node.setNext(item.getNext());
item.getNext().setLast(node);
if (index == 0) {
}
if (index == this.size - 1) {
this.endNode = node;
}
break; } lastNode = item; item = item.getNext(); x++; }}Copy the code``````

#### Hand code - delete

``````public void delete(T data) {
TwoWayNode lastNode = null;
while(item! =null) {
lastNode = item.getLast();
if (item.getData().equals(data)) {
if (lastNode==null) {
break;
}
if (item.getNext() == null) {
lastNode.setNext(null);
this.endNode = lastNode;
break;
}
lastNode.setNext(item.getNext());
item.setLast(lastNode);
break; } item = item.getNext(); }}Copy the code``````

### Manual code - Single linked list reversal

Read the above code, single linked list inversion is actually very simple

• 1, create an empty new list, loop the list that needs to be reversed
• 2. First save the data of the next loop, set the next node of the loop to the next node of the new list, and then set the next node of the new list to the node of the current loop until the end of the loop
• 3, show a head node insertion method, there are other methods, but I won't show too many for now (^ del ^)
``````public static void main(String[] args) {
System.out.print("List to reverse:");
System.out.println("");
System.out.println("");
}

public void reversal(OneWayNodeString node) {
OneWayNode resultList = new OneWayNodeString(null);
OneWayNode p = node;
while(p! =null) {// Save the data after the insertion point
OneWayNode tempList = p.getNext();
p.setNext(resultList.getNext());
resultList.setNext(p);
p = tempList;
}
``Here is just a simple demonstration of one-way, two-way linked list part of the basic operation, the shortcomings of a lot of instruction; There are circular list, the principle of the same, interested friends can have a look.Copy the code``
``Scenarios in which the data volume is small and needs to be frequently added or deletedCopy the code``