1.1 basic introduction

1. Advantages and disadvantages of one-way linked list

• For one-way linked lists, the search direction can only be one direction, while two-way linked lists can search forward or backward.
• A one-way linked list cannot be deleted by itself. It needs to rely on auxiliary nodes, while a two-way linked list can be deleted by itself.

2. Basic introduction to bidirectional linked list

Bidirectional linked list, also known as bidirectional list, is a kind of linked list. It is composed of multiple nodes. Each node is composed of a data field and two pointer fields. The data field (data) is used to store data, one pointer field (next) is used to point to its successor node, and the other pointer field is used to point to the predecessor node (prev pointer). The data field of the head node of the linked list does not store data, the pointer field value pointing to the predecessor node is null, and the pointer field pointing to the successor node points to the first node that actually stores data.

1.2 add operation

1. Train of thought analysis

Head insertion

• New insert node newNode.

• The first precursor points to the newNode.

• The rear drive of newNode points to first.

• The first point to the newNode. At this time, the head only represents the second node, and the head needs to represent the first node, so the direction is changed.

Tail insertion

• New insert node newNode.
• The newNode precursor points to last.
• The last rear drive points to the newNode.
• Last points to newNode. At this time, last only represents the penultimate node, and last needs to represent the last node, so it points to newNode.

Middle insertion

New insert node newNode

Locate the previous node to insert the newNode. And the next node nextNode

The newNode trailing driver points to the nextnode, and the nextnode leading driver points to the newNode. At this time, the newNode and the following are associated with the linked list, but they are separated from the previous processing.

The preNode driver points to the newNode and the newNode precursor points to the preNode. At this time, the complete insertion operation is completed.

2. Code example

Linked list class: DoubleLinkedList

package cn.linkedlist.demo03;

public class DoubleLinkedList<E> {
    // Number of linked list elements
    private int size;
    // Declaration header node
    private Node first;
    // Declare tail node
    private Node last;

    // Create Node
    private class Node{
        // Storage content
        public E data;
        // Point to the previous node of the linked list
        public Node prev;
        // Point to next node
        public Node next;
        // Construction method
        
        public Node() {
            
        }
        
        public Node(Node prev, E data, Node next) {
            this.prev = prev;
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString(){
            return data.toString();
        }
    }

    // Initialize header node
    public DoubleLinkedList(){
        first = null;
        last = null;
        size = 0;
    }

    /***
     * Gets the number of elements in the linked list
     * @return
     */
    public int getSize(){
        return size;
    }

    /***
     * Returns whether the linked list is empty
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /***
     * Add a new element according to the index position of the linked list e
     * @param index
     * @param data
     */
    public void add(int index, E data){
        // Call method
        rangeCheckAdd(index);

        if (index == size) { // Add the last element
            addLast(data);
        } else if(index == 0){
            addLast(data);
        } else {
            // Add new node next element
            Node nextNode = node(index);
            // The previous element of the newly added node
            Node prevNode = nextNode.prev;
            // Add new node
            Node newNode = new Node (prevNode, data, nextNode);
            // The previous prev of the next node points to the new node
            nextNode.prev = newNode;
            // The next of the prevNode node points to the new node
            prevNode.next = newNode;
        }
        size++;
    }

    /***
     * Add a new element to the linked list header e
     * @param data
     */
    public void addFirst(E data){
        // Create a new node
       Node newNode = new Node(null, data, null);
       if(isEmpty()){
           last = newNode; // last -> newNode
       }else {
           first.prev = newNode; // first.prev->newNode
       }
       newNode.next = first; // newNode.next -> first;
       first = newNode;
       size++;
    }

    /***
     * Add a new element at the end of the linked list e
     * @param data
     */
    public void addLast(E data){
        // Create a new node
        Node newNode = new Node(null, data, null);
        if(isEmpty()){
            first = newNode; // first->newNode
        }else{
            last.next = newNode; // The node pointed to by last points to the new node
            newNode.prev = last; // The precursor of the new node points to the last pointer
        }
        last = newNode; // The last pointer points to the new node
        size++;
    }
	
    /**
     * Get the node object corresponding to the index location
     * @param index
     * @return
     */
    private Node node(int index) {
        rangeCheck(index);
        Node node;
        if (index < (size >> 1)) {
            node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = last;
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("size=").append(size).append(", [");
        // Define a pointer variable
        Node cur = first;
        while(cur != null){
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL");
        res.append("]");
        return res.toString();
    }

    // Index value check range method
    private void rangeCheck(int index){
        if(index < 0 || index >=size){
            // Call out of bounds processing method
            outOfBounds(index);
        }
    }

    // Add method index check scope
    private void rangeCheckAdd(int index){
        if(index < 0 || index >size){
            // Call out of bounds processing method
            outOfBounds(index);
        }
    }
    // Array index out of bounds processing
    private void outOfBounds(int index){
        throw new IndexOutOfBoundsException("index:" + index + ", Size:" + size);
    }
}

Test class: DoubleLikedListTest

package cn.linkedlist.demo03;

public class DoubleLinkedListDemo01 {
    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        System.out.println("===Linked list header insertion===");
        for(int i=0; i<5; i++){
            list.addFirst(i);
            System.out.println(list);
        }

        System.out.println("===Tail insertion of linked list===");
        list.addLast(12);
        list.addLast(111);
        list.addLast(123);
        list.addLast(15);
        System.out.println(list);

        System.out.println("===Insert in the middle of linked list===");
        list.add(2, 23);
        list.add(7, 66);
        list.add(8, 39);

        System.out.println(list);
    }
}

3. Code example

1.3 modifying and querying

1. Query operation

Linked list class: DoubleLinkedList

/***
 * Get the element at the index position of the linked list
 * @param index
 * @return
*/
public E get(int index){
    return node(index).data;
}

/***
  * Get the first element of the linked list
  * @return
 */
public E getFirst(){
    return get(0);
}

/***
  * Get the last element of the linked list
  * @return
 */
public E getLast(){
    return get(size - 1);
}

/***
 * Find out if there is an element e in the linked list
 * @param data
 * @return
*/
public boolean contains(E data){
    Node cur = first.next;
    while(cur != null){
        if(cur.data.equals(data))
            return true;
        cur = cur.next;
    }
    return false;
}

Test class: DoubleLikedListTest

package cn.linkedlist.demo03;

public class DoubleLinkedListDemo01 {
    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        for(int i=0; i<5; i++){
            list.addFirst(i);
        }
        list.addLast(12);
        list.addLast(111);
        list.addLast(123);
        list.addLast(15);
       
        list.add(2, 23);
        list.add(7, 66);
        list.add(8, 39);
        
        System.out.println("===Find element===");
        Integer integer = list.get(2);
        System.out.println("Get elements by index:" + integer);
        Integer first = list.getFirst();
        System.out.println("First linked list element:" + first);
        Integer last = list.getLast();
        System.out.println("Last linked list element:" + last);
        boolean b = list.contains(23);
        System.out.println("Does the element exist:" + b);
    }
}

2. Execution results

3. Modify operation

Linked list class: DoubleLinkedList

/***
     * Modify the element at the index(0-based) position of the linked list to e
     * @param index
     * @param data
     */
public void update(int index, E data){
    // Call index detection method
    rangeCheck(index);
    // Create cur pointer to virtual header node
    Node cur = first;
    for(int i = 0 ; i < index ; i ++) {
        cur = cur.next;
    }
    cur.data = data;
}

Test class: DoubleLikedListTest

package cn.linkedlist.demo03;

public class DoubleLinkedListDemo01 {
    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        for(int i=0; i<5; i++){
            list.addFirst(i);
        }
        list.addLast(12);
        list.addLast(111);
        list.addLast(123);
        list.addLast(15);
       
        list.add(2, 23);
        list.add(7, 66);
        list.add(8, 39);

        System.out.println("===Modify node elements===");
        System.out.println("linkedList(Before modification)" + list);
        list.update(4, 38);
        System.out.println("linkedList(After modification)" + list);
    }
}

4. Execution results

1.4 delete

1. Train of thought analysis

Because it is a two-way linked list, you can delete a node by yourself and directly find the node to be deleted.

Head node deletion

The front pointer prev of the driver node of the first node is changed to null.

The first node points to first Next, so that first points to the first node required.

Tail node deletion

Tail deletion is to delete the last node in the two-way linked list, that is, the node pointed to by the tail pointer. The idea is the same as that of head deletion.

last.prev.next=null the trailing node of the previous node (prev) of the trailing node is equal to null.

last = last. The prev tail node points to its predecessor node. At this time, the tail node is deleted because step 1next is null.

Intermediate deletion

Find the precursor node of the node to be deleted, preNode, preNode Next is the node to delete

preNode.next.next.pre=preNode, point the prev pointer of the rear drive node nextNode of the node to be deleted to the prenode, which is equivalent to nextNode pre=preNode.

preNode.next=preNode.next.next;， At this time, the deleteNode is skipped and successfully deleted.

2. Code example

Linked list class: DoubleLinkedList

/***
 * Delete the element at the index position from the linked list and return the deleted element
 * @param index
*/
public void remove(int index){
    // Call index detection method
    rangeCheck(index);
    // Conditional judgment
    if(index == 0){
        removeFirst();
    }else if(index == size -1 ){
        removeLast();
    }else {

        //Deletes the previous element of the location
        Node preNode = first;
        for(int i=0; i < index-1; i++) {
            preNode = preNode.next;
        }
        //The element of the location to delete
        Node deleteNode = preNode.next;
        //The next element to delete
        Node nextNode = deleteNode.next;
        
        preNode.next = nextNode;
        nextNode.prev = preNode;

        size--;
    }
}

/***
 * Delete the first element from the linked list and return the deleted element
*/
public void removeFirst(){
    if (size == 1)
    {
        first = null;
        last = null;
    } else {
        first =first.next;
    }
    size--;
}

/***
 * Delete the last element from the linked list and return the deleted element
*/
public void removeLast(){
    if (size == 1)
    {
        first = null;
        last = null;
    } else {
        last.prev.next = null;
        last = last.prev;
    }
    size--;
}

/***
 * Delete element e from linked list
 * @param data
 */
public void removeElement(E data){
    // Create header node
    Node prev = first;
    while(prev.next != null){
        if(prev.next.data.equals(data))
            break;
        prev = prev.next;
    }

    if(prev.next != null){
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
    }
}

Test class: DoubleLikedListTest

package cn.linkedlist.demo03;

public class DoubleLinkedListDemo01 {
    public static void main(String[] args) {
        DoubleLinkedList<Integer> list = new DoubleLinkedList<>();
        for(int i=0; i<5; i++){
            list.addFirst(i);
        }
        
        list.addLast(12);
        list.addLast(111);
        list.addLast(123);
        list.addLast(15);
        
        list.add(2, 23);
        list.add(7, 66);
        list.add(8, 39);

        System.out.println("===Before deleting a linked list node====");
        System.out.println(list);
        System.out.println("===After deleting a linked list node====");

        // Delete the first node of the linked list
        list.removeFirst();
        System.out.println(list);
        // Returns the deleted element according to the element in the index position of the linked list
        list.remove(2);
        System.out.println(list);

        // Delete the last node in the linked list
        list.removeLast();
        System.out.println(list);

        // Delete elements in linked list
        list.removeElement(39);
        System.out.println(list);
    }
}

3. Execution results