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

advantages

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

disadvantages

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

Singly linked list

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 OneWayNode<T> {
    private T  data; // Node data
    private OneWayNode<T> next; // Next node address
    public OneWayNode(T data) {
        this.data = data;
    }
    public OneWayNode<T> getNext(a) {
         return next;
    }
    public void setNext(OneWayNode<T> next) {
        this.next = next;
    }
    public T getData(a) {
        return this.data;
    }
    public void setData(T data) {
        this.data = data; }}public class OneWayLinkeList<T> {
    private static OneWayNode headNode = null;	/ / head node
    private static OneWayNode endNode = null;	/ / end nodes
    private static int size = 0;		// List length
    public void show(a) { / / traverse
        OneWayNode item = this.headNode;
        while(item! =null) {
            System.out.print(item.getData() + ""); item = item.getNext(); }}}Copy the code

Hand code – add

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) {
    OneWayLinkeList linkeList =	new OneWayLinkeList<String>();
    linkeList.add("hello");
    linkeList.add("hello2");
    linkeList.add("hello3");
    linkeList.show(); // hello1 hello2 hello3 
}
public void add(T data, int index) {
    if (index > this.size) {
        System.out.println("Subscript out of bounds!");
    }
    this.size ++;
    OneWayNode node = new OneWayNode<T>(data);
    OneWayNode item = null;
    if (index == 0) {	// Add the header
        if (this.headNode == null) {
            this.headNode = node;
            this.endNode = node;
        } else {
            item = this.headNode;
            this.headNode = node;
            this.headNode.setNext(item);
        }
        return;
    }
    if (index == this.size-1) { // Add at the end
        item = this.endNode;
        item.setNext(node);
        this.endNode = node;
        return;
    }
    int x = 0;
    item = this.headNode;
    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) {
    OneWayLinkeList linkeList =	new OneWayLinkeList<String>();
    linkeList.add("hello1");
    linkeList.add("hello2");
    linkeList.add("hello3");
    linkeList.update("hello4".2);
    linkeList.show(); // hello1 hello2 hello4 
}
public void update(T data, int index) {
    if (index > this.size) {
        System.out.println("Subscript out of bounds!");
    }
    OneWayNode node = new OneWayNode<T>(data);
    int x = 0;
    OneWayNode item = this.headNode;
    OneWayNode lastNode = null;
    while(item! =null) {	/ / modify
        if (x==index) {
            lastNode.setNext(node);
            node.setNext(item.getNext());
            if (index == 0) {
                this.headNode = node;
            }
            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

• Head removal: Directly sets the next node to the head node as the head node
• 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) {
    OneWayLinkeList linkeList =	new OneWayLinkeList<String>();
    linkeList.add("hello1");
    linkeList.add("hello2");
    linkeList.add("hello3");
    linkeList.delete("hello2");
    linkeList.show(); // hello1 hello3
}
public void delete(T data) {
    OneWayNode item = this.headNode;
    OneWayNode lastNode = null;
    while(item! =null) {
        if (item.getData().equals(data)) {
            if (lastNode==null) {
                 this.headNode = item.getNext();
                 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) {
    OneWayLinkeList linkeList =	new OneWayLinkeList<String>();
    linkeList.add("hello1");
    linkeList.add("hello2");
    linkeList.add("hello3");
    linkeList.get(1); // hello2
}
public void get(int index) {
    int x = 0;
    OneWayNode item = this.headNode;
    while(item ! =null) {
        if (x==index) {
            System.out.println(item.getData());
            break; } item = item.getNext(); x++; }}Copy the code

Two-way linked list

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 TwoWayNode<T> {
    private T  data;	// Node information
    private TwoWayNode<T> next; // Next node
    private TwoWayNode<T> last; // Last node
    public TwoWayNode(T data) {
        this.data = data;
    }
    public TwoWayNode<T> getNext(a) {
         return next;
    }
    public void setNext(TwoWayNode<T> next) {
        this.next = next;
    }
    public TwoWayNode<T> getLast(a) {
         return last;
    }
    public void setLast(TwoWayNode<T> last) {
        this.last = last;
    }
    public T getData(a) {
        return this.data;
    }
    public void setData(T data) {
        this.data = data; }}public class TwoWayLinkeList<T> {
	private static TwoWayNode headNode = null;	/ / head node
	private static TwoWayNode endNode = null;	/ / end nodes
	private static int size = 0;				// List length
}
Copy the code

Hand code – add

There are also three cases of the add operation

• Header added: same as single – way linked list
• 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
• Middle add: First find the place to add

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 TwoWayNode<T>(data);
    TwoWayNode item = null;
    if (index == 0) {	// Add the header
        if (this.headNode == null) {
            this.headNode = node;
            this.endNode = node;
        } else {
            item = this.headNode;
            item.setLast(node);
            node.setNext(item);
            this.headNode = node;
        }
        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;
    item = this.headNode;
    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 TwoWayNode<T>(data);
    int x = 0;
    TwoWayNode item = this.headNode;
    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) {
                this.headNode = node;
            }
            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 item = this.headNode;
    TwoWayNode lastNode = null;
    while(item! =null) {
        lastNode = item.getLast();
        if (item.getData().equals(data)) {
            if (lastNode==null) {
                 this.headNode = item.getNext();
                 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) {
    OneWayLinkeList<String> linkeList =	new OneWayLinkeList<String>();
    linkeList.add("hello1");
    linkeList.add("hello2");
    linkeList.add("hello3");
    System.out.print("List to reverse:");
    linkeList.show();
    System.out.println("");
    System.out.println("");
    OneWayLinkeList<String> reversalLinkeList =	new OneWayLinkeList<String>();
    reversalLinkeList.reversal(linkeList.headNode);
    System.out.print("Inverted linked list:");
    reversalLinkeList.show();
}

public void reversal(OneWayNode<String> node) {
    OneWayNode resultList = new OneWayNode<String>(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;
    }
    this.headNode = resultList.getNext();
}
Copy the code

conclusion

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

Applicable scenario

Scenarios in which the data volume is small and needs to be frequently added or deletedCopy the code