实现双向链表(带傀儡节点)

引言

在之前的博文中，我简单的向大家分享了一些链表相关的知识及一些面试题，如果感兴趣的老铁可以去瞧瞧，今天做题遇到要实现带傀儡节点的双向链表，做了下，之前的单向链表中我们也遇到要设置傀儡节点（哨兵节点的题），今天我们就来看一下实现双向链表(带傀儡节点)。

基本思路

**对于链表没说带傀儡节点或者虚拟节点，这个链表没有真正的头结点，但是我们把第一个节点叫做头结点，它起到标识的作用，标识这个链表的头结点
这个头结点的位置随时可能发生这变化，是不固定的，之后通过这个头结点我们要完成一些链表的增删查改。如果带傀儡节点这个节点的位置是固定的，那么以后我们操作链表就以这个傀儡节点作为头结点，完成我们的一些基本的增删查改操作。**这就很简单了，具体思路见我之前双链表的博文。
代码如下内有关键注释：
DoubleLinkedList .java

///实现双向链表(带傀儡节点)代码
  class ListNode {
    

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

        public ListNode(int data) {
    

            this.data = data;
        }
    }
    public class DoubleLinkedList {
    
        public ListNode dummyHead;//虚拟头结点
        public ListNode last;//尾结点
        public DoubleLinkedList() {
    
            this.dummyHead = new ListNode(-1);//傀儡节点
        }

        //找到某一位置的节点,用于删除节点
        public ListNode findIndex(int index) {
    
            ListNode cur = dummyHead.next;
            while (index != 0) {
    
                cur = cur.next;
                index--;

            }
            return cur;
        }


        //头插法
        public void addFirst(int data) {
    
            ListNode node=new ListNode(data);
            //第一次插入一个节点也没有时的情况
            if(this.dummyHead.next==null) {
    
                node.prev=this.dummyHead;
                this.dummyHead.next=node;
                this.last=node;
                return;
               // this.head=node;//带头了就不用再定义头了
            }else {
    
                //新插入的节点和他前后的节点连接
                node.next=this.dummyHead.next;
                node.prev=this.dummyHead;
                this.dummyHead.next.prev=node;
                this.dummyHead.next=node;
            }
        }

        //尾插法
        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;
            }
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
    
            //判断位置的合法性，任意位置插入,第一个数据节点为0号下标
            if (index < 0 || index > size()) {
    
                System.out.println("输入的位置不合法");
                return;
            } else {
    
                if (index == 0) {
    
                    addFirst(data);
                    return;
                }
                if (index == size()) {
    
                    addLast(data);
                }else {
    
                    //中间插
                    ListNode node = new ListNode(data);
                    ListNode cur;
                    cur = findIndex(index);
                    cur.prev.next = node;//当index==size时，如果不采用尾插法，会出现空指针异常
                    node.prev = cur.prev;
                    cur.prev = node;
                    node.next = cur;
                }
            }

        }

        //查找是否包含关键字key是否在单链表当中
        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;
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key) {
    
            ListNode cur = this.dummyHead.next;

            while(cur != null) {
    
                if(cur.data == key) {
    
                    if(cur == this.dummyHead.next) {
    
                        //头结点是唯一的一个节点或不是唯一的一个节点的情况是一样的，
                        // 都是下面的代码和之前的不带头结点的双向链表不同
                        this.dummyHead.next = this.dummyHead.next.next; //两步代码是前后承接的
                        this.dummyHead.next.prev = this.dummyHead;
                    } else {
    
                        cur.prev.next = cur.next;
                        //判断是不是最后一个节点
                        //要删除的节点不是最后一个节点
                        if (cur.next != null) {
    
                            cur.next.prev = cur.prev;
                        } else {
    
                            //要删除的节点是最后一个节点
                            this.last = cur.prev;
                        }
                    }
                    return;
                } else {
    
                    cur = cur.next;
                }
            }
        }

        //删除所有值为key的节点
        public void removeAllKey(int key) {
    
            ListNode cur = dummyHead.next;
            while (cur != null) {
    
                //
                if (cur.data == key) {
    
                    //判断是不是头结点
                    if (cur == this.dummyHead.next) {
    //注意这里不要出错
                        this.dummyHead.next=this.dummyHead.next.next;
                        this.dummyHead.next.prev=null;

                    } else {
    
                        cur.prev.next = cur.next;
                        //判断是不是最后一个节点
                        if (cur.next == null) {
    
                            this.last = cur.prev;
                        } else {
    
                            cur.next.prev = cur.prev;
                        }


                    }

                }
                cur = cur.next;继续往后走 不要停 直到为null 的时候
            }
        }

        //得到单链表的长度
        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() {
    
            //把所有的节点都置为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;


        }
    }

测试类

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();
    }
}

️过小🧑*‍‍🧑*如果9️⃣以话记点持，
往期文章：
双向链表的实现（双向链表与单向链表的简单区别联系和实现）
链表的概念和结构及基本功能函数的实现（单链表的实现）