Data structures and algorithms – bidirectional linked lists

1. What is a bidirectional list?

• Each node in a bidirectional list has one more prev that points to the previous node

• The prev of the head node of the bidirectional list points to NULL, and the next of the tail node points to NULL

• The design of the LinkedList will have a first that points to the head node and a last that points to the node

1.1. Initialization of bidirectional linked lists

• Compared to a single necklace list, there is a first pointer and a node pointer prev

  public class LinkedList3 extends AbstractList {

  private Node<E> first; Private Node<E> last; Private static class Node<E> {E element; Node<E> next; Node<E> prev; Public Node(Node<E> prev, E element, Node<E> next) {this.element = element; this.next = next; this.prev = prev; }}Copy the code

  }

2. Implementation of query methods

private Node<E> node(int index) { rangeCheck(index); If (index < (size >> 1)) {Node<E> Node = first; For (int I = 0; i < index; i++) { node = node.next; } return node; }else { Node<E> node = last; For (int I = size-1; i > index; I --) {// element from index to sie-1 node = node.prev; } return node; }}Copy the code

• The query of bidirectional linked list is very different from the previous single necklace list, and the query is more efficient
• At query time, you can determine whether the index is in the first half of size or the last half of size.
• Before 1/2 of size: the element is 0 until the index is passed in to start the query, and Node. next assigns the value to Node
• In the last half of size: the element is queried from index to size-1, the query is backwards, and node.prev is assigned to node

3. Insert elements

Public void addNode(int index, E element) {// Next = Node(index); Prev = next-prev; Next Node<E> Node = new Node<>(prev, element, next); // Next's last node is a new node. Next-prev = node; // The next node of a prev is a new node. Next = node; }Copy the code

• Inserting an element is inserting a new element at the current index position

• The node where index is saved is next

• The node with the index-1 bit before the index position is prev

• Insert newNode at index. The attribute prev of newNode should point to the node prev at index-1, and the attribute next of newNode should point to the node next at index

• The prev of next points to newNode

• Next in the index-1 node location points to newNode

When the newly inserted node index is 0, special treatment is required because first refers to the 0 node

Public void addNode(int index, E element) {// Next = Node(index); Prev = next-prev; Next Node<E> Node = new Node<>(prev, element, next); // Next's last node is a new node. Next-prev = node; If (next. Prev == null) {// First should point to first = node; }else {// The next node of prev is a new node prev.next = node; }}Copy the code

• When the index of the incoming node is 0, the prev attribute of the current node is null
• All you need is for first to point to the current property newNode

When the inserted node is at the end of the list, special treatment is also required because the last attribute refers to the last node

public void add(int index, E element) { rangeCheckForAdd(index); If (index == size) {Node<E> oldLast = last; // If (index == size) {Node<E> oldLast = last; Next = null, prev = last = new Node<>(oldLast, element, null); Oldlast.next = last; oldlast.next = last; oldlast.next = last; }else {// Next Node after adding a new Node Node<E> next = Node (index); // Node<E> prev = next-prev; Next Node<E> Node = new Node<>(prev, element, next); // Next's last node is a new node. Next-prev = node; If (next. Prev == null) {first = node; }else {// The next node of prev is a new node prev.next = node; } } size++; }Copy the code

• When index==size is passed in, the element is inserted at the last position
• The node where the last location is saved first is oldLast
• The last attribute points to newNode, the newNode that was inserted, newNode’s prev attribute points to oldLast, and newNode’s next attribute points to null
• The next attribute of oldLast points to the inserted new node, which is last

4. Delete the node

Public E remove(int index) {// Remove the Node Node<E> Node = Node (index); // Delete the previous Node of the Node Node<E> prev = node.prev; // Delete the next Node Node<E> next = node.next; Index == 0 if (prev == null) {first = next; }else { prev.next = next; } // If next == null, index== sie-1 if (next == null) {last = prev; }else { next.prev = prev; } size--; return node.element; }Copy the code

• Delete node: it is to make the current node to be deleted lose the point of the node before and after
• Again, special treatment is required to delete the first position node and the last position node
• And then finally, let’s make size–

5. Clear the linked list

public void clear() {
    size = 0;
    first = null;
    last = null;
}
Copy the code

• Size needs to be 0, and first and last all point to

6. Comparison between bidirectional linked lists and dynamic arrays

• Dynamic arrays: open, destroy memory space relatively few times, but may result in memory space waste (can be reduced by scaling)
• Bidirectional linked list: open, destroy memory space relatively more times, but does not cause memory space waste
• If you frequently add or delete the tail, you can choose either
• If the header is frequently added or deleted, you are advised to select a bidirectional linked list
• Dynamic arrays are recommended for frequent query operations