---------------------------------------------------------------------------------------------------------------------------------------------------------
學習Java就上哪吒社區，干貨滿滿，內有每日打卡，Java資料，Java學習路線，福利多多哦，既能學習又能獲得小禮物，豈不美哉？
【哪吒社區】點此進入.
---------------------------------------------------------------------------------------------------------------------------------------------------------

【前言】在《通過Java理解和實作——順序表和單鏈表》一文中已經講完了順序表和單鏈表，接下來就是雙向鏈表了，其實和單鏈表非常相似，需要注意的就是一些小細節

🍉無頭雙向鏈表

🌵雙鏈表概念及結構

【為什么引入雙鏈表？】
?單鏈表的結點中只有一個指向其后繼的指標，使得單鏈表要訪問某個結點的前驅結點時，只能從頭開始遍歷，訪問后驅結點的復雜度為O(1)，訪問前驅結點的復雜度為O(n)，為了克服上述缺點，引入了雙鏈表，
?雙鏈表的結點中有兩個指標prev和next，分別指向前驅結點和后繼結點，

🍌無頭雙向非回圈鏈表介面實作（注釋非常詳細，我👴👴都能看懂）

先寫兩個類，一個是鏈表類（包含有一個【可變的頭結點】和【可變尾節點】和【實作各種功能的介面】，因為是無頭鏈表，所以這個頭結點和尾節點是可變的），另一個是節點類（成員屬性有value和prev（前驅）和next（后驅））

接下來的介面都是寫在鏈表類里的，因為鏈表是一個物件，我們要實作的就是一個鏈表物件所有的功能

🍈列印雙鏈表

列印鏈表其實和列印順序表類似，遍歷鏈表就好了，不過要注意一個點，這里需要引入一個區域變數cur來代替頭節點去遍歷，因為頭結點在沒添加或者洗掉節點之前是固定的，不要讓頭結點變來變去

//列印雙鏈表
   public void display() {
       //和單鏈表的列印方式是一樣的
       ListNode cur = this.head;//利用臨時變數cur代替頭結點遍歷
       while (cur != null){
           System.out.print(cur.val+" ");
           cur = cur.next;//依次往后走
       }
       System.out.println();
   }

🍈頭插法插入

顧名思義，頭插法就是從頭部插入節點，使新創建的節點成為新的頭結點，這里需要額外考慮一個點，就是頭結點是否存在（鏈表是否為空），（注意，不光要設定后驅還要注意前驅，這比單鏈表多一個前驅節點）

//頭插法
   public void addFirst(int data) {
       ListNode node = new ListNode(data);//創建一個新節點，儲存要插入的資料
       if (this.head==null){//判斷頭結點是否為空，頭結點空說明鏈表為空
           //頭結點null屬于第一次插入，直接將頭結點尾節點都指向插入節點即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           node.next=this.head;//將原頭結點變成新插入節點的后驅，實作頭插
           head.prev=node;//再將新插入節點變成原頭結點的前驅
           this.head=node;//最后將新插入的節點設定成頭結點
       }
   }

🍈尾插法插入

尾插法和頭插法類似，必須先判斷鏈表是否為空（判斷頭結點是否為null），雙鏈表區別于單鏈表，不用每次遍歷來找尾節點，雙鏈表本身就有一個尾節點last，我們只需要找到這個last，然后將新節點插入即可

//尾插法
   public void addLast(int data){
       ListNode node = new ListNode(data);//創建一個新節點，儲存要插入的資料
       if (this.head==null){//判斷頭結點是否為空，頭結點空說明鏈表為空
           //頭結點null屬于第一次插入，直接將頭結點尾節點都指向插入節點即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           this.last.next=node;//將新結點變成原尾節點的后驅，實作尾插
           node.prev=last;//再將原尾節點變成新插入節點的前驅
           this.last=node;//最后將新插入節點設定成尾節點
       }
   }

🍈查找是否包含關鍵字key在雙鏈表當中

傳入關鍵字key，依舊是引入區域變數cur遍歷鏈表，哪個節點的value等于key了，說明鏈表里有這個關鍵字，回傳true，否則回傳false，和單鏈表一模一樣

//查找是否包含關鍵字key是否在單鏈表當中
   public boolean contains(int key){
       ListNode cur = this.head;//引入區域變數cur遍歷鏈表
       while(cur != null){
           if(cur.val==key){//如果當前節點的val等于關鍵字
               return true;//回傳true
           }
           cur = cur.next;//否則繼續往后遍歷
       }
       return false;//遍歷完成都沒有找到key值，回傳false
   }

🍈得到雙鏈表的長度

依舊采取參考區域變數cur來遍歷鏈表，還要多設定一個區域變數size來計數，只要節點不為null，size就+1，最后回傳size的值就是鏈表長度了（其實和單鏈表也一模一樣）

//得到雙鏈表的長度
   public int size() {
       int size=0;//設定一個計數變數用于計數
       ListNode cur = this.head;//利用cur代替頭結點遍歷鏈表
       while (cur != null){//遍歷鏈表，節點不為空
           size++;//計數器+1
           cur = cur.next;//往后走一步
       }
       return size;//遍歷完鏈表回傳計數器的值，就是鏈表長度了
   }

🍈任意位置插入,第一個資料節點為0號下標

插入原理：臨時變數cur代替頭結點，cur先走到要插入的位置，然后將新節點插到cur和cur前一節點的中間，替代了cur的原位置，實作按位置插入節點

//任意位置插入,第一個資料節點為0號下標
   public void addIndex(int index,int data){
       ListNode node = new ListNode(data);//創建一個新節點儲存要插入的資料
       ListNode cur = this.head;//臨時變數cur代替頭結點遍歷鏈表
       if (index > 0 && index <size()) {//插入位置不是頭也不是尾
           for (int i = 0; i < index; i++){//先讓cur走到要插入的位置處
               cur = cur.next;
           }
           cur.prev.next=node;//將插入位置前一節點的后驅指向新節點
           node.prev=cur.prev;//將新節點的前驅指向插入位置的前一節點即 cur.prev
           node.next=cur;//將新節點后驅指向當前cur，也就實作了插入，插到cur和cur前一節點的中間，替代了cur的原位置
       }
       if (index ==size()){//插入位置在尾部
           addLast(data);//直接尾插法
       }
       if (index==0){//插入位置在頭部
           addFirst(data);//直接頭插法
      }
       display();//列印增加后的鏈表
   }

🍈洗掉第一次出現關鍵字為key的節點

首先判斷頭結點是否為null（鏈表是否為空），然后找要洗掉的節點，要洗掉的節點有三種情況
①關鍵字在頭節點：將頭節點下一個節點設定為新頭節點
②關鍵字在尾巴結點：將尾節點上一個節點設定為新尾節點
③關鍵字不在頭結點：則將key節點的前一個節點的后驅指向key節點的后一個節點，key節點的后一節點的前驅指向key節點前一節點

//洗掉第一次出現關鍵字為key的節點
   public void remove(int key){
       ListNode cur = this.head;//設定cur代替頭節點遍歷鏈表
       while(cur != null){
           if(cur.val==key){//如果找到了要洗掉的點，分以下三種情況
               if(cur==head){//在頭部
                   head=head.next;//將要洗掉的節點的下一節點設為新頭節點
                   if (head==null) {//如果這個雙鏈表只有一個元素，要檢查
                       break;
                   }
                   head.prev=null;//如果不止一個元素，則將頭結點的前驅指向置空
                   break;
               }
               if (cur==last){//在尾部
                   last=last.prev;//要洗掉節點的上一節點設為新尾節點
                   last.next=null;//將新尾節點后驅置空
                   break;
               } >               if (cur.prev!=null && cur.next!=null){//在中間
                   cur.prev.next=cur.next;//將key節點前一節點的后驅指向key節點的后一節點
                   cur.next.prev=cur.prev;//將key節點后一節點的前驅指向key節點的前一節點
                   break;
               }
           }
           cur=cur.next;//如果沒找到目標點則往后走一步
       }
       display();//列印洗掉后的雙鏈表
   }

🍈洗掉所有值為key的節點

和上邊洗掉第一次出現的key類似（注釋可以看上邊洗掉第一次出現的key），只不過在洗掉節點過后不要break，讓遍歷回圈繼續進行

//洗掉所有值為key的節點
   public void removeAllKey(int key){
       ListNode cur = this.head;
       while(cur != null){
           if(cur.val==key){
               if(cur==head){//在頭部
                   head=head.next;
                   if (head==null) {//只有一個元素，要檢查
                       break;
                   }
                   head.prev=null;
               }
               if (cur==last){//在尾部
                   last=last.prev;
                   last.next=null;
               }
               if (cur.prev!=null && cur.next!=null){//在中間
                   cur.prev.next=cur.next;
                   cur.next.prev=cur.prev;
               }
           }
           cur=cur.next;
       }
       display();
   }

🍈清空鏈表

暴力清空，直接將頭尾結點置空，這樣整個鏈表就無法找到了

//清空鏈表
   public void clear() {
       head=null;
       last=null;
   }

🍉單鏈表和雙鏈表到底有啥區別

一、指代不同
1、雙向鏈表：也叫雙鏈表，是鏈表的一種，每個資料結點中都有兩個指標，分別指向直接后繼和直接前驅
2、單向鏈表：是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始，
二、優點不同
1、雙向鏈表：從雙向鏈表中的任意一個結點開始，都可以很方便地訪問前驅結點和后繼結點，
2、單向鏈表：單個結點創建非常方便，普通的線性記憶體通常在創建的時候就需要設定資料的大小，結點的訪問方便，可以通過回圈或者遞回的方法訪問到任意資料，
三、缺點不同
1、雙向鏈表：增加洗掉節點復雜，需要多分配一個指標存盤空間，
2、單向鏈表：結點的洗掉非常方便，不需要像線性結構那樣移動剩下的資料，但是平均的訪問效率低于線性表，

🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
?原創不易，如有錯誤，歡迎評論區留言指出，感激不盡?
? 如果覺得內容不錯，給個三連不過分吧~ ?
? 看到會回訪~ ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙