建站
咨詢
售后
建站咨詢
新聞中心
前言
前面有很詳細的講過線性表(順序表和鏈表)，當時講的鏈表以單鏈表為主，但實際上在實際應用中雙鏈表的應用多一些就比如LinkedList。
我們提供的服務(wù)有：網(wǎng)站設(shè)計制作、成都做網(wǎng)站、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、臨泉ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學管理、有技術(shù)的臨泉網(wǎng)站制作公司
雙鏈表與單鏈表區(qū)別
邏輯上它們均是線性表的鏈式實現(xiàn)，主要的區(qū)別是節(jié)點結(jié)構(gòu)上的構(gòu)造有所區(qū)別，這個區(qū)別從而引起操作的一些差異。
單鏈表：
單鏈表的一個節(jié)點，有儲存數(shù)據(jù)的data，還有后驅(qū)節(jié)點next(指針)。也就是這個單鏈表想要一些遍歷的操作都得通過前節(jié)點—>后節(jié)點。
雙鏈表：
雙鏈表的一個節(jié)點，有存儲數(shù)據(jù)的data,也有后驅(qū)節(jié)點next(指針)，這和單鏈表是一樣的，但它還有一個前驅(qū)節(jié)點pre(指針)。
雙鏈表結(jié)構(gòu)的設(shè)計
上文講單鏈表的時候，我們當時設(shè)計的是一個帶頭結(jié)點的鏈表就錯過了不帶頭結(jié)點操作方式，這里雙鏈表咱們就不帶頭結(jié)點設(shè)計實現(xiàn)。并且上文單鏈表實現(xiàn)的時候是沒有尾指針tail的，在這里我們設(shè)計的雙鏈表帶尾指針。
所以我們構(gòu)造的這個雙鏈表是：不帶頭節(jié)點、帶尾指針(tail)、雙向鏈表。
對于node節(jié)點：
- class node
{ - T data;
- node
pre; - node
next; - public node() {
- }
- public node(T data) {
- this.data = data;
- }
- }
對于鏈表：
- public class doubleList
{ - private node
head;// 頭節(jié)點 - private node
tail;// 尾節(jié)點 - private int length;
- //各種方法
- }
具體操作分析
對于一個鏈表主要的操作還是增刪。增刪的話不光需要考慮鏈表是否帶頭節(jié)點，還有頭插、尾插、中間插等多種插入刪除形式，其中的一些細節(jié)處理也是比較重要的(防止鏈表崩掉出錯)，如果你對這塊理解不夠深入很容易寫錯也很難排查出來。當然，鏈表的查找、按位修改操作相比增刪操作還是容易很多。
初始化
雙鏈表在最初的時候頭指針指向為null。那么對于這個不帶頭節(jié)點的雙鏈表而言。它的head始終指向第一個真實有效的節(jié)點。tail也指向最后一個有效的節(jié)點。在最初的時候head=null，并且tail=head，此時鏈表為空，等待節(jié)點插入。
- public doubleList() {
- head = null;
- tail = head;
- length = 0;
- }
插入
空鏈表插入
對于空鏈表來說。增加第一個元素可以特殊考慮。因為在鏈表為空的時候head和tail均為null。但head和tail又需要實實在在指向鏈表中的真實數(shù)據(jù)(帶頭指針就不需要考慮)。所以這時候就新建一個node讓head、tail等于它。
- node
teamNode = new node(data); - if (isEmpty()) {
- head = teamNode;
- tail = teamNode;
- }
頭插
對于頭插入來說。步驟很簡單，只需考慮head節(jié)點的變化。
- 新建插入節(jié)點node
- head前驅(qū)指向node
- node后驅(qū)指向head
- head指向node。(這時候head只是表示第二個節(jié)點，而head需要表示第一個節(jié)點故改變指向)
尾插：
對于尾插入來說。只需考慮尾節(jié)點tail節(jié)點的變化。
- 新建插入節(jié)點node
- node前驅(qū)指向tail
- tail后驅(qū)指向node
- tail指向node。(這時候tail只是表示倒數(shù)第二個節(jié)點，而tail需要表示最后節(jié)點故指向node)
按編號插入
對于編號插入來說。要考慮查找和插入兩步，而插入既和head無關(guān)也和tail無關(guān)。
1 新建插入節(jié)點node
2 找到欲插入node的前一個節(jié)點preNode。和后一個節(jié)點nextNode
3 node后驅(qū)指向nextNode,nextNode前驅(qū)指向node(此時node和后面與鏈表已經(jīng)聯(lián)立，但是和前面處理分離狀態(tài))
4 preNode后驅(qū)指向node。node前驅(qū)指向preNode(此時插入完整操作完畢)
整個流程的動態(tài)圖為：
刪除
只有單個節(jié)點刪除
無論頭刪還是尾刪，遇到單節(jié)點刪除的需要將鏈表從新初始化!
- if (length == 1)// 只有一個元素
- {
- head = null;
- tail = head;
- length--;
- }
頭刪除
頭刪除需要注意的就是刪除不為空時候頭刪除只和head節(jié)點有關(guān)
流程大致分為：
1 head節(jié)點的后驅(qū)節(jié)點的前指針pre改為null。(head后面節(jié)點本指向head但是要刪除第一個先讓后面那個和head斷絕關(guān)系)
2 head節(jié)點指向head.next(這樣head就指向我們需要的第一個節(jié)點了，前面節(jié)點就被刪除成功，如果有c++等語言第一個被孤立的節(jié)點刪除釋放即可，但Java會自動釋放)
尾刪除
尾刪除需要注意的就是刪除不為空時候尾刪除只和tail節(jié)點有關(guān)。記得在普通鏈表中，我們刪除尾節(jié)點需要找到尾節(jié)點的前驅(qū)節(jié)點。需要遍歷整個表，而雙向鏈表可以直接從尾節(jié)點遍歷到前面。
尾刪除就是刪除雙向鏈表中的最后一個節(jié)點，也就是尾指針所指向的那個節(jié)點，思想和頭刪除的思想一致，具體步驟為：
- tail.pre.next=null尾節(jié)點的前一個節(jié)點(pre)的后驅(qū)節(jié)點等于null
- tail=tail.pre尾節(jié)點指向它的前驅(qū)節(jié)點，此時尾節(jié)點由于步驟1next已經(jīng)為null。完成刪除
普通刪除
普通刪除需要重點掌握，普通刪除要妥善處理好待刪除節(jié)點的前后關(guān)系，具體流程如下：
1：找到待刪除節(jié)點node的前驅(qū)節(jié)點prenode(prenode.next是要刪除的節(jié)點)
2 : prenode.next.next.pre=prenode.(將待刪除node的后驅(qū)節(jié)點aftnode的pre指針指向prenode，等價于aftnode.pre=prenode)
3: prenode.next=prenode.next.next;此時node被跳過成功刪除。
完成刪除整個流程的動態(tài)圖為：
實現(xiàn)與測試
通過上面的思路簡單的實現(xiàn)一下雙鏈表，當然有些地方命名不太規(guī)范，實現(xiàn)效率有待提升，主要目的還是帶著大家理解。
代碼(代碼以圖片方式貼出，如需源碼可閱讀原文或者加我好友發(fā)你)：
測試：
結(jié)語
在插入刪除的步驟，很多人可能因為繁瑣的過程而弄不明白，但實際上這個操作的寫法可能是多樣的，但本質(zhì)操作都是一致的，所以看到其他不同版本有差距也是正常的。
還有很多人可能對一堆next.next搞不清楚，那我教你一個技巧，如果在等號右側(cè)，那么它表示一個節(jié)點，如果在等號左側(cè)，那么除了最后一個.next其他的表示節(jié)點。例如node.next.next.next可以看成(node.next.next).next。
在做數(shù)據(jù)結(jié)構(gòu)與算法鏈表相關(guān)題的時候，不同題可能給不同節(jié)點去完成插入、刪除操作。這種情況操作時候要謹慎先后順序防止破壞鏈表結(jié)構(gòu)。
代碼操作可能有些優(yōu)化空間，還請各位大佬指正!如有收獲
本文名稱：雙鏈表，這回徹底搞dong了
標題鏈接：http://www.dlmjj.cn/article/dpgddpd.html
