Two-way linked list

Disadvantages of single linked lists:

• The entire list can only be accessed from the head node
• When deleting a single linked list, it needs to use auxiliary nodes and cannot delete itself. It needs to find the previous node of the node to be deleted and then delete it.

Bidirectional linked list:

Due to the disadvantages of single linked list, bidirectional linked list is extended. Compared with single linked list, there is one more pre in bidirectional linked list, which points to the precursor node of this node. When accessing the linked list, it can be accessed both forward and backward. And the nodes in a bidirectional list can delete themselves.

// Temp is the node to be deleted
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
Copy the code

If temp is the last node, temp.next is null, so temp.next-pre will fail. If temp is the last node, temp. next-pre will fail. Next = temp. Next; temp. Can.

Code Implementation (Java)

package com.doublelinkedlist;

public class LinkedList2 {
    public static void main(String[] args) {
        System.out.println("Two-way linked list test:");
        DoubleLinkedList List2 = new DoubleLinkedList();

        Node2 node1 = new Node2(1."Zhang"."The first");
        Node2 node2 = new Node2(2."Bill"."A second");
        Node2 node3 = new Node2(3."Fifty"."The third");
        List2.addNode2(node1);
        List2.addNode2(node2);
        List2.addNode2(node3);
        // Iterate after adding the node
        List2.showLinkedList2();

        // Change the value of the node, passing in the no value and the modified information, the same as the single linked list
        List2.changeNode2(2."Hit"."0");
        List2.showLinkedList2();

        // Delete the node and pass in the no value
        List2.del2(3); List2.showLinkedList2(); }}class Node2 {
    public int no;
    public String name;
    public String nickName;
    public Node2 next;
    public Node2 pre;

    public Node2(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName; }}class DoubleLinkedList {
    private Node2 head = new Node2(0.""."");

    // Insert the node
    public void addNode2(Node2 node) {
        Node2 temp = head;
        while(temp.next ! =null) {
            temp = temp.next;
        }
        temp.next = node;
        node.next = null;
        node.pre = temp;
    }

    // Change the value of the node. Use "no" to judge. "No" cannot be changed
    public void changeNode2(int no, String name, String nickName) {
        Node2 temp = head;
        Boolean flag = false;
        if (temp.next == null) {
            System.out.println("Linked list is empty and cannot be modified!");
        }
        while(temp.next ! =null) {
            if (temp.next.no == no) {
                temp.next.name = name;
                temp.next.nickName = nickName;
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == false) {
            System.out.println("This node is not in the list!"); }}// Delete the corresponding node according to no
    public void del2(int no) {
        Node2 temp = head.next;
        Boolean flag = false;
        if (temp == null) {
            System.out.println("Linked list is empty and cannot be deleted!");
            return;
        }
        while(temp ! =null) {
            if (temp.no == no) {
                temp.pre.next = temp.next;
                if(temp.next ! =null) {
                    temp.next.pre = temp.pre;
                }
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag == false) {
            System.out.println("This node is not in the list!"); }}// Iterate over the node information in the output list
    public void showLinkedList2(a) {
        Node2 temp = head;
        if (temp.next == null) {
            System.out.println("Linked list is empty!!");
        }
        while(temp.next ! =null) {
            System.out.printf("no = %d name = %s nickName = %s; \n", temp.next.no, temp.next.name, temp.next.nickName); temp = temp.next; }}}Copy the code