前言
在上一篇文章中，主要是給大家介紹了單向連結清單的特點及其原理，但是我們沒有通過代碼進行練習。今天我會繼續通過一篇文章，來給大家講解雙向連結清單的内容，尤其是會通過代碼來進行連結清單的操作，希望大家重點關注哦。
全文大約【3500】 字，不說廢話，隻講可以讓你學到技術、明白原理的純幹貨！本文帶有豐富的案例及配圖視訊，讓你更好地了解和運用文中的技術概念，并可以給你帶來具有足夠啟迪的思考...
一. 雙向連結清單簡介
1. 概念
在上一篇文章中，我們在介紹連結清單的種類時，曾經提到過雙向連結清單。雙向連結清單相比較于單連結清單，除資料域外，還具前和後兩個指向指針。
雙向連結清單中的結構術語可以解釋為：
- data：連結清單每個結點中存儲的資料域；
- next：連結清單每個結點中包含的指向下一個結點位址的指針域；
- prev：連結清單每個結點中包含的前一個結點位址的指針域。
2. 編碼定義
根據上述對雙向連結清單結點的定義，我們給出雙向連結清單結點結構的Java定義實作：
雙向連結清單是一條真實存在的連結清單，由多個結點組成。在實際的程式設計中，通常會标記連結清單的兩個特殊結點，分别為：頭結點、尾結點。用另外一個變量size表示連結清單中元素的個數。
- 頭結點： 連結清單中的第一個結點
- 尾結點： 連結清單中的最後一個元素
是以有如下連結清單類的定義：
在本篇文章接下來的内容中，我們将利用該DNode、DoubleLinkList兩個定義來實作雙向連結清單的各項操作。
二. 常見操作
因為雙向連結清單是單連結清單的基礎上擴充出來的結構，是以雙向連結清單的很多操作與單連結清單的操作都是相同的，比如：查找元素、更新元素、插入元素、删除元素。
1. 查找元素
1.1 查找頭結點
因為DoubleLinkList中已經記錄了頭結點head，是以頭結點的查找非常簡單，如下：
時間複雜度為O(1)。
1.2 查找尾結點
與頭結點同理，查找尾結點的時間複雜度同樣為O(1），編碼如下：
1.3 查找指定位置結點
當需要查找指定位置的結點元素時，雙向連結清單比單連結清單的實作方式有所不同，原因是：
單連結清單因為是單向的，是以隻能從頭結點向後單向查找；但雙向連結清單前後均可查找，是以在進行指定位置查找時，為了提高查找效率，會首先判斷要查找的位置處于連結清單的前半段還是後半段，若前半段則從頭結點向後查找，若後半段則從尾結點向前查找，具體程式設計如下所示：
在上述代碼中，size >> 1 的寫法比較少見，“>>”在計算機程式設計中代表移位操作。常見的移位操作有兩種：
- >>：向右移位操作，将一個二進制位的操作數按指定移動的位數向右移動，移出位被丢棄，左邊移出的空位一律補0，或者補符号位。
- <<：向左移位操作，将一個二進制位的操作數按指定移動的位數向左移動，移出位被丢棄，右邊移出的空位一律補0。
通過實際的程式設計驗證，我們可以知道：執行右移1位操作，變量資料會縮小為原來的1/2。左移相反。同時，我們可以分析出時間複雜度為O(n)。
2. 更新元素
更新元素操作需要兩步：
- 找到要更新的元素
- 執行更新操作
根據位置的不同，可以将更新操作分為三種情況：更新頭結點，更新尾結點，更新指定位置結點。
2.1 更新頭結點
更新頭結點代碼與查找頭結點類似，如下：
更新頭結點的時間複雜度為O(1)。
2.2 更新尾結點
更新尾結點的時間複雜度同樣是O(1)。
2.3 更新指定位置結點
如上代碼所示，修改指定結點元素的值采用的算法也是：先判斷要操作的位置在前半段還是後半段，然後再進行精準查找，最後執行修改操作。
指定位置修改操作的時間複雜度為O(n)。
3. 插入元素
分析過了查找元素和更新元素操作的具體情況，我們很清晰的便能分析出插入元素操作的具體情況，其實也分為三種具體情景：頭結點位置插入，尾結點位置插入，指定位置插入元素。
3.1 頭結點位置插入
根據如上代碼，我們可以看到，在頭結點位置插入新的元素，隻需要将新添加的結點置為head結點，同時處理好新結點和原連結清單中頭結點的指向關系即可。很明顯，頭結點位置插入的時間複雜度為O(1)。
3.2 尾結點位置插入
尾結點插入與頭結點插入原理相同，隻需要替換為尾結點以及指針的指向。如下所示：
時間複雜度為O(1)。
3.3 指定位置插入
在進行指定位置插入時，程式設計代碼稍多些，原因是需要以下幾步完成：
- 判斷插入的位置是否超範圍
- 若插入的位置在最後，則執行在尾結點的插入邏輯
- 先根據要插入的位置，查找并擷取到對應位置的結點元素
- 然後執行插入邏輯
根據上述代碼，我們可以發現插入指定位置的代碼，需要用到查找指定位置的操作，先查找再插入，是以時間複雜度同樣為O(n)。
4. 删除元素
有了前面的分析經驗，我們可以非常自然的分析出删除操作同樣分三種：删除頭結點、删除尾結點、删除指定結點。接下來，一起來看看詳細的情況：
4.1 删除頭結點
删除頭結點隻涉及頭結點的邏輯判斷和操作，是以删除頭結點時間複雜度為O(1)。
4.2 删除尾結點
與删除頭結點原理相同，操作尾結點。代碼如下：
很明顯，删除尾結點的時間複雜度為O(1)。
4.3 删除指定結點
删除指定結點的編碼實作如下：
如上代碼所示，删除指定位置的結點元素也需要先執行index(index)查找算法，至于index的實作，在前文介紹指定位置插入結點操作時，已經進行了實作，此處直接進行使用。
我們不難分析得到，删除指定位置的結點的時間複雜度是O(n)。
三. 其他操作
作為一種常見的資料結構，除了對自身結點元素的一些操作，還有一些對連結清單狀态的擷取，比如連結清單的長度，連結清單是否為空等，這裡給大家介紹一下雙向連結清單的一些其他操作。
1. 連結清單的大小(元素結點的個數)
2. 判斷連結清單是否為空
3. 擷取連結清單元素組成的數組
4. 清空連結清單
四. 結語
至此，我們已經連續用兩篇文章給大家介紹了連結清單的相關知識。
在上一篇文章中，我們主要介紹了連結清單的基礎知識和單連結清單的正常操作， 同時輔以圖示來說明各種操作情況。在本篇文章中，主要是從Java程式設計角度作為切入點，來進一步講解雙向連結清單的一些操作。 特别是本篇文章中的大量代碼實踐，需要大家能夠理清邏輯關系，希望你可以動手練起來哦。
5分鐘學會資料結構中的線性連結清單
深入淺出Spring原理及實戰「緩存Cache開發系列」
從零開始學Java之查找算法有哪些？
SQLYog使用教程
更多技術類幹貨/IT程式員資訊，關注@千鋒教育