Realize bidirectional linked list (with puppet node)

introduction

In the previous post , I simply shared some linked list related knowledge and some interview questions , If old fellow interested can go and see it. , Today, I have to realize a two-way linked list with puppet nodes , I did it , In the previous one-way linked list, we also encountered the need to set puppet nodes （ Question of sentinel node ）, Today, let's take a look at the implementation of two-way linked lists ( With puppet nodes ).

The basic idea

** For the linked list, it doesn't say that there are puppet nodes or virtual nodes , This linked list has no real header , But we call the first node the head node , It plays the role of identification , Identify the head node of this linked list
The position of this head node may change at any time , It's not fixed , After that, through this header node, we need to complete the addition, deletion, search and modification of some linked lists . If there is a puppet node, the position of this node is fixed , In the future, we will operate the linked list with this dummy node as the head node , Complete some basic operations of adding, deleting, checking and modifying .** It's very simple , See my previous blog post on double linked list for specific ideas .
The code below has key comments ：
DoubleLinkedList .java

/// To realize two-way linked list ( With puppet nodes ) Code 
  class ListNode {
    

        public int data;
        public ListNode prev;
        public ListNode next;

        public ListNode(int data) {
    

            this.data = data;
        }
    }
    public class DoubleLinkedList {
    
        public ListNode dummyHead;// Virtual head node 
        public ListNode last;// Caudal node 
        public DoubleLinkedList() {
    
            this.dummyHead = new ListNode(-1);// Puppet node 
        }

        // Find the node at a certain location , For deleting nodes 
        public ListNode findIndex(int index) {
    
            ListNode cur = dummyHead.next;
            while (index != 0) {
    
                cur = cur.next;
                index--;

            }
            return cur;
        }


        // The first interpolation 
        public void addFirst(int data) {
    
            ListNode node=new ListNode(data);
            // The case when there is no node inserted for the first time 
            if(this.dummyHead.next==null) {
    
                node.prev=this.dummyHead;
                this.dummyHead.next=node;
                this.last=node;
                return;
               // this.head=node;// If you take the lead, you don't have to define the head anymore 
            }else {
    
                // The newly inserted node is connected with the nodes before and after it 
                node.next=this.dummyHead.next;
                node.prev=this.dummyHead;
                this.dummyHead.next.prev=node;
                this.dummyHead.next=node;
            }
        }

        // The tail interpolation 
        public void addLast(int data) {
    
            ListNode node=new ListNode(data);
            if(this.dummyHead.next==null&&this.last==null) {
    
                node.prev=this.dummyHead;
                this.dummyHead.next=node;
                this.last=node;
                return;
            }else {
    
                this.last.next=node;
                node.prev=this.last;
                this.last=node;
            }
        }

        // Insert at any position , The first data node is 0 Subscript no. 
        public void addIndex(int index, int data) {
    
            // Judge the legitimacy of the location , Insert at any position , The first data node is 0 Subscript no. 
            if (index < 0 || index > size()) {
    
                System.out.println(" The position entered is illegal ");
                return;
            } else {
    
                if (index == 0) {
    
                    addFirst(data);
                    return;
                }
                if (index == size()) {
    
                    addLast(data);
                }else {
    
                    // Insert... In the middle 
                    ListNode node = new ListNode(data);
                    ListNode cur;
                    cur = findIndex(index);
                    cur.prev.next = node;// When index==size when , If tail interpolation is not used , A null pointer exception will occur 
                    node.prev = cur.prev;
                    cur.prev = node;
                    node.next = cur;
                }
            }

        }

        // Look for keywords key Is it in a single linked list 
        public boolean contains(int key) {
    
            ListNode cur = this.dummyHead.next;
            while (cur != null) {
    
                if (cur.data == key) return true;
                 cur=cur.next;
            }
            //return false;
            return false;
        }

        // Delete the first keyword as key The node of 
        public void remove(int key) {
    
            ListNode cur = this.dummyHead.next;

            while(cur != null) {
    
                if(cur.data == key) {
    
                    if(cur == this.dummyHead.next) {
    
                        // The situation is the same when the head node is the only node or not the only node ,
                        //  The following code is different from the previous two-way linked list without leading nodes 
                        this.dummyHead.next = this.dummyHead.next.next; // The two-step code is undertaken before and after 
                        this.dummyHead.next.prev = this.dummyHead;
                    } else {
    
                        cur.prev.next = cur.next;
                        // Determine whether it is the last node 
                        // The node to be deleted is not the last node 
                        if (cur.next != null) {
    
                            cur.next.prev = cur.prev;
                        } else {
    
                            // The node to be deleted is the last node 
                            this.last = cur.prev;
                        }
                    }
                    return;
                } else {
    
                    cur = cur.next;
                }
            }
        }

        // Delete all values as key The node of 
        public void removeAllKey(int key) {
    
            ListNode cur = dummyHead.next;
            while (cur != null) {
    
                //
                if (cur.data == key) {
    
                    // Determine whether it is a header node 
                    if (cur == this.dummyHead.next) {
    // Be careful not to make mistakes here 
                        this.dummyHead.next=this.dummyHead.next.next;
                        this.dummyHead.next.prev=null;

                    } else {
    
                        cur.prev.next = cur.next;
                        // Determine whether it is the last node 
                        if (cur.next == null) {
    
                            this.last = cur.prev;
                        } else {
    
                            cur.next.prev = cur.prev;
                        }


                    }

                }
                cur = cur.next; Keep going back   Don't stop   Until null  When 
            }
        }

        // Get the length of the single linked list 
        public int size() {
    
            ListNode cur =this.dummyHead.next;
            int count = 0;
            while (cur != null) {
    
                count++;
                cur = cur.next;
            }
            return count;
        }

        public void display() {
    

            ListNode cur = this.dummyHead.next;
            while (cur != null) {
    
                System.out.print(cur.data + " ");
                cur = cur.next;

            }
            System.out.println();

        }

        public void clear() {
    
            // Set all nodes to null
            ListNode cur =  this.dummyHead.next;
            ListNode curNext;
            while (cur != null) {
    
                curNext = cur.next;
                cur.prev = null;
                cur.next = null;
                cur = curNext;
            }
            this.dummyHead = null;
            this.last = null;


        }
    }

Test class

ublic class TestDemo {
    
    public static void main(String[] args) {
    
        DoubleLinkedList doubleLinkedList =new DoubleLinkedList();
        doubleLinkedList.addFirst(1);
        doubleLinkedList.addFirst(2);
        doubleLinkedList.addFirst(3);
        doubleLinkedList.addFirst(0);
        System.out.println(doubleLinkedList.size());
        doubleLinkedList.display();
        System.out.println(doubleLinkedList.contains(0));
        System.out.println("======================================");
        doubleLinkedList.removeAllKey(1);
        doubleLinkedList.display();
        doubleLinkedList.addFirst(0);
        doubleLinkedList.display();
    }
}

️ Too small 🧑*‍‍🧑* If 9️⃣ Remember to hold in words ,
The articles ：
The realization of double linked list （ The simple difference between two-way linked list and one-way linked list and its implementation ）
The concept and structure of linked list and the realization of basic function （ The realization of single linked list ）