Introduction to bidirectional linked list
The unidirectional linked list has only one direction, and the node has only one subsequent pointer. Next points to the following node. The twoway linked list, as its name suggests, supports two directions. Each node has more than one subsequent pointer next pointing to the following node, and a precursor pointer prev pointing to the previous node.
As can be seen from the above figure, the twoway linked list needs two additional spaces to store the addresses of subsequent nodes and predecessor nodes. Therefore, if the same amount of data is stored, the twoway linked list will occupy more memory space than the single linked list. Although two pointers waste storage space, they can support twoway traversal, which also brings the flexibility of twoway linked list operation. Compared with single linked list, what kind of problem is bidirectional linked list suitable for?
Structurally, the twoway linked list can support finding the precursor node in the case of O(1) time complexity. It is this feature that also makes the insertion, deletion and other operations of the twoway linked list simpler and more efficient than the single linked list in some cases.
Add, delete, change and query operations of twoway linked list
1. Insert operation
 Head insertion: time complexity O(1)
 Tail insertion: time complexity O(1)
 Insert after specified location: time complexity O(1)
 Insert before the specified position: time complexity O(1)  pay attention to the difference between oneway linked list and oneway linked list
2. Delete
The time complexity of the delete operation is similar to that of the insert operation.
 Delete header node: time complexity O(1)
 Delete tail node: time complexity O(1)
 Delete nodes with a value equal to a certain number: time complexity O(n)
 Delete a specific node: O(1)
The deletion operation is explained here.
In actual software development, deleting a data from the linked list is no different from these two situations:

Delete the node with "value equal to a given value" in the node;

Delete the node pointed to by the given pointer.
For the first case, whether it is a single linked list or a twoway linked list, in order to find the node whose value is equal to the given value, we need to traverse and compare one by one from the first node until we find the node whose value is equal to the given value, and then delete it through the pointer operation I mentioned earlier.
Although the time complexity of simple deletion operation is O(1), the time of traversal search is the main timeconsuming point, and the corresponding time complexity is O(n). According to the addition rule in time complexity analysis, the total time complexity of the linked list operation corresponding to the node whose deletion value is equal to the given value is O(n).
For the second case, we have found the node to be deleted, but to delete a node Q, we need to know its precursor node, and the single linked list does not support direct access to the precursor node. Therefore, in order to find the precursor node, we still have to traverse the linked list from the first node until p  > next = q, indicating that P is the precursor node of Q.
But for the twoway linked list, this situation has advantages. Because the node in the bidirectional linked list has saved the pointer of the precursor node, it does not need to traverse like the single linked list. Therefore, for the second case, the single linked list deletion operation needs O(n) time complexity, while the twoway linked list only needs to be completed within O(1) time complexity!
In addition to the advantages of insert and delete operations, for an ordered linked list, the efficiency of valuebased query of twoway linked list is also higher than that of single linked list. Because we can record the location p of the last search. During each query, we decide whether to search forward or backward according to the relationship between the value to be searched and the size of p, so we only need to search half of the data on average.
Now, do you think a twoway linked list is more efficient than a single linked list? This is why in the actual software development, although the twoway linked list costs more memory, it is still more widely used than the single linked list. If you are familiar with the Java language, you must have used the LinkedHashMap container. If you deeply study the implementation principle of LinkedHashMap, you will find that the data structure of twoway linked list is used.
3. Update operation
 Update specified node: time complexity O(1)
 Update the node whose value in the linked list is equal to a specific value: time complexity O(n)
4. Query operation
 Time complexity: O(n)
Java code implementation of bidirectional linked list
public class TwoWayLinkedList<E> { public static void main(String[] args) { TwoWayLinkedList<Integer> list = new TwoWayLinkedList<>(); //Tail insertion, traversal linked list output System.out.println("Tail insertion[110]"); for (int i = 1; i <= 10; i++) { list.addLast(Integer.valueOf(i)); } list.printList(); //Insert the header and traverse the linked list output System.out.println("Head insertion[110]"); for (int i = 1; i <= 10; i++) { list.addFirst(Integer.valueOf(i)); } list.printList(); //Insert after the specified node System.out.println("Insert after header node[100]"); list.addAfter(100, list.head); list.printList(); System.out.println("Insert before header node[100]"); list.addBefore(100, list.head); list.printList(); System.out.println("Insert before tail node[100]"); list.addBefore(100, list.tail); list.printList(); System.out.println("Insert after tail node[100]"); list.addAfter(100, list.tail); list.printList(); System.out.println("Delete method test"); System.out.println("Delete header node"); list.removeFirst(); list.printList(); System.out.println("Delete tail node"); list.removeLast(); list.printList(); System.out.println("Delete the specified node"); list.removeNode(list.head.next); list.printList(); } private Node head; private Node tail; public TwoWayLinkedList() { } public TwoWayLinkedList(E data) { Node node = new Node<>(data, null,null); head = node; tail = node; } public void printList() { Node p = head; while (p != null && p.next != null) { System.out.print(p.data + ">"); p = p.next; } if (p != null) { System.out.println(p.data); } } public void addFirst(E data) { Node newNode = new Node(data,null ,head); if(head!=null){ head.pre = newNode; } head = newNode; if (tail == null) { tail = newNode; } } public void addLast(E data) { Node newNode = new Node(data, tail,null); if (tail == null) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } /** * @param data * @param node node The node must be in the linked list */ public void addAfter(E data, Node node) { if (node == null) { return; } Node newNode = new Node(data, node,node.next); if(node.next!=null){ node.next.pre = newNode; } node.next = newNode; if (tail == node) { tail = newNode; } } public void addBefore(E data, Node node) { if (node == null) { return; } if(node==head){ addFirst(data); }else { Node newNode = new Node(data,node.pre,node); node.pre.next = newNode; node.pre = newNode; } } public void removeFirst() { if (head == null) { return; } if (head == tail) { head = null; tail = null; } else { if(head.next!=null){ head.next.pre = null; } head = head.next; } } public void removeLast() { if (tail == null) { return; } if (head == tail) { head = null; tail = null; } else { if(tail.pre!=null){ tail.pre.next = null; Node p = tail.pre; tail.pre = null; tail = p; } } } public void removeNode(Node node) { if (node == null) { return; } if(node==head){ removeFirst(); } if(node==tail){ removeLast(); } node.pre.next = node.next; node.next.pre = node.pre; } private static class Node<E> { E data; Node pre; Node next; public Node(E data, Node pre, Node next) { this.data = data; this.pre = pre; this.next = next; } } }
JDK implementation of bidirectional linked list
The LinkedList in JDK is a bidirectional linked list. We can use it directly or make simple packaging.
package com.csx.algorithm.link; import java.util.Collection; import java.util.Collections; import java.util.LinkedList; import java.util.Set; import java.util.function.Predicate; public class SinglyLinkedList2<E> { private LinkedList<E> list; public SinglyLinkedList2() { this.list = new LinkedList<>(); } public SinglyLinkedList2(E data){ Set<E> singleton = Collections.singleton(data); this.list = new LinkedList<>(singleton); } public SinglyLinkedList2(Collection<? extends E> c){ this.list = new LinkedList<>(c); } // New method public void addFirst(E data){ list.addFirst(data); } public void addLast(E data){ list.addLast(data); } // Add at the end of the linked list public boolean add(E date){ return list.add(date); } public boolean addAll(Collection<? extends E> collection){ return list.addAll(collection); } public boolean addBefore(E data,E succ){ int i = list.indexOf(succ); if(i<0){ return false; } list.add(i,data); return true; } public boolean addAfter(E data,E succ){ int i = list.indexOf(succ); if(i<0){ return false; } if((i+1)==list.size()){ list.addLast(data); return true; }else { list.add(i+1,data); return true; } } // Delete method // Delete method: delete the head element of the linked list by default public E remove(){ return list.remove(); } // Delete method: delete the first element of the linked list public E removeFirst(){ return list.removeFirst(); } // Delete method to delete the last element of the linked list public E removeLast(){ return list.removeLast(); } // Delete the element that appears for the first time in the linked list, and return true after successful deletion // The criterion for object equality is to call the equals method public boolean remove(E data){ return list.remove(data); } // The logic is the same as the remove (E data) method public boolean removeFirstOccur(E data){ return list.removeFirstOccurrence(data); } // Because the LinkedList is a twoway linked list, the time complexity is the same as removefirstoccurs public boolean removeLastOccur(E data){ return list.removeLastOccurrence(data); } // Batch deletion method public boolean removeAll(Collection<?> collection){ return list.removeAll(collection); } // Delete by condition public boolean re(Predicate<? super E> filter){ return list.removeIf(filter); } // Query method // Query linked list header element public E getFirst(){ return list.getFirst(); } // Query tail elements of linked list public E getLast(){ return list.getLast(); } // Query whether the linked list contains an element // Support null judgment // The criterion for equality is data equals(item) public boolean contains(E data){ return list.contains(data); } public boolean containsAll(Collection<?> var){ return list.containsAll(var); } }
As a reminder, LinkedList is not thread safe. If you need to ensure thread safety, you need to do synchronization control yourself.
Bidirectional circular linked list
In fact, it is to point the leading pointer of the head node to the tail node and the trailing pointer of the tail node to the head node.
Comparison of arrays and linked lists
However, the comparison between arrays and linked lists cannot be limited to time complexity. Only the complexity of the data stored in the software development can not be used to determine the actual data structure.
The array is simple and easy to use. It uses continuous memory space in the implementation. The data in the array can be read in advance with the help of the CPU cache mechanism, so the access efficiency is higher. The linked list is not stored continuously in memory, so it is not friendly to CPU cache and can not be read effectively.
The disadvantage of array is that its size is fixed. Once declared, it will occupy the whole block of continuous memory space. If the declared array is too large, the system may not have enough continuous memory space allocated to it, resulting in "out of memory". If the declared array is too small, it may not be enough. At this time, you can only apply for a larger memory space to copy the original array, which is very timeconsuming. The linked list itself has no size limit and naturally supports dynamic capacity expansion. I think this is also the biggest difference between it and array.
In addition, if your code is very demanding on the use of memory, the array is more suitable for you. Because each node in the linked list needs to consume additional storage space to store a pointer to the next node, the memory consumption will double. Moreover, frequent insertion and deletion of linked lists will also lead to frequent memory application and release, which is easy to cause memory fragmentation. If it is Java language, it may lead to frequent GC (Garbage Collection). Therefore, in our actual development, for different types of projects, we should weigh whether to choose array or linked list according to the specific situation.