引言

在之前的博文中，我簡單的向大家分享了一些鏈表相關的知識及一些面試題，如果感興趣的老鐵可以去瞧瞧，今天做題遇到要實作帶傀儡節點的雙向鏈表，做了下，之前的單向鏈表中我們也遇到要設定傀儡節點（哨兵節點的題），今天我們就來看一下實作雙向鏈表(帶傀儡節點)，

基本思路

**對于鏈表沒說帶傀儡節點或者虛擬節點，這個鏈表沒有真正的頭結點，但是我們把第一個節點叫做頭結點，它起到標識的作用，標識這個鏈表的頭結點
這個頭結點的位置隨時可能發生這變化，是不固定的，之后通過這個頭結點我們要完成一些鏈表的增刪查改，如果帶傀儡節點這個節點的位置是固定的，那么以后我們操作鏈表就以這個傀儡節點作為頭結點，完成我們的一些基本的增刪查改操作，**這就很簡單了，具體思路見我之前雙鏈表的博文，
代碼如下內有關鍵注釋：
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??🉐🉑以🉐話記🉐點👍🏻🍹持👇🏻，🦀🦀
往期文章：
雙向鏈表的實作（雙向鏈表與單向鏈表的簡單區別聯系和實作）
鏈表的概念和結構及基本功能函式的實作（單鏈表的實作）