日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
雙鏈表，這回徹底搞dong了

前言

前面有很詳細(xì)的講過線性表(順序表和鏈表)，當(dāng)時(shí)講的鏈表以單鏈表為主，但實(shí)際上在實(shí)際應(yīng)用中雙鏈表的應(yīng)用多一些就比如LinkedList。

我們提供的服務(wù)有：網(wǎng)站設(shè)計(jì)制作、成都做網(wǎng)站、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、臨泉ssl等。為上千余家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的臨泉網(wǎng)站制作公司

雙鏈表與單鏈表區(qū)別

邏輯上它們均是線性表的鏈?zhǔn)綄?shí)現(xiàn)，主要的區(qū)別是節(jié)點(diǎn)結(jié)構(gòu)上的構(gòu)造有所區(qū)別，這個(gè)區(qū)別從而引起操作的一些差異。

單鏈表：

單鏈表的一個(gè)節(jié)點(diǎn)，有儲存數(shù)據(jù)的data，還有后驅(qū)節(jié)點(diǎn)next(指針)。也就是這個(gè)單鏈表想要一些遍歷的操作都得通過前節(jié)點(diǎn)—>后節(jié)點(diǎn)。

雙鏈表：

雙鏈表的一個(gè)節(jié)點(diǎn)，有存儲數(shù)據(jù)的data,也有后驅(qū)節(jié)點(diǎn)next(指針)，這和單鏈表是一樣的，但它還有一個(gè)前驅(qū)節(jié)點(diǎn)pre(指針)。

雙鏈表結(jié)構(gòu)的設(shè)計(jì)

上文講單鏈表的時(shí)候，我們當(dāng)時(shí)設(shè)計(jì)的是一個(gè)帶頭結(jié)點(diǎn)的鏈表就錯(cuò)過了不帶頭結(jié)點(diǎn)操作方式，這里雙鏈表咱們就不帶頭結(jié)點(diǎn)設(shè)計(jì)實(shí)現(xiàn)。并且上文單鏈表實(shí)現(xiàn)的時(shí)候是沒有尾指針tail的，在這里我們設(shè)計(jì)的雙鏈表帶尾指針。

所以我們構(gòu)造的這個(gè)雙鏈表是：不帶頭節(jié)點(diǎn)、帶尾指針(tail)、雙向鏈表。

對于node節(jié)點(diǎn)：

 
 
 
 
    
  
  
  
  
  1. class node { 
    2. 
  
  
  
  
  2.   T data; 
    3. 
  
  
  
  
  3.     node pre; 
    4. 
  
  
  
  
  4.     node next; 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.     public node() { 
    7. 
  
  
  
  
  7.     } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9.     public node(T data) { 
    10. 
  
  
  
  
  10.         this.data = data; 
    11. 
  
  
  
  
  11.     } 
    12. 
  
  
  
  
  12. } 
    13.

對于鏈表：

 
 
 
 
    
  
  
  
  
  1. public class doubleList { 
    2. 
  
  
  
  
  2.   private node head;// 頭節(jié)點(diǎn) 
    3. 
  
  
  
  
  3.     private node tail;// 尾節(jié)點(diǎn) 
    4. 
  
  
  
  
  4.     private int length; 
    5. 
  
  
  
  
  5.     //各種方法     
    6. 
  
  
  
  
  6. } 
    7.

具體操作分析

對于一個(gè)鏈表主要的操作還是增刪。增刪的話不光需要考慮鏈表是否帶頭節(jié)點(diǎn)，還有頭插、尾插、中間插等多種插入刪除形式，其中的一些細(xì)節(jié)處理也是比較重要的(防止鏈表崩掉出錯(cuò))，如果你對這塊理解不夠深入很容易寫錯(cuò)也很難排查出來。當(dāng)然，鏈表的查找、按位修改操作相比增刪操作還是容易很多。

初始化

雙鏈表在最初的時(shí)候頭指針指向?yàn)閚ull。那么對于這個(gè)不帶頭節(jié)點(diǎn)的雙鏈表而言。它的head始終指向第一個(gè)真實(shí)有效的節(jié)點(diǎn)。tail也指向最后一個(gè)有效的節(jié)點(diǎn)。在最初的時(shí)候head=null，并且tail=head，此時(shí)鏈表為空，等待節(jié)點(diǎn)插入。

 
 
 
 
    
  
  
  
  
  1. public doubleList() { 
    2. 
  
  
  
  
  2.     head = null; 
    3. 
  
  
  
  
  3.     tail = head; 
    4. 
  
  
  
  
  4.     length = 0; 
    5. 
  
  
  
  
  5.     } 
    6.

插入

空鏈表插入

對于空鏈表來說。增加第一個(gè)元素可以特殊考慮。因?yàn)樵阪湵頌榭盏臅r(shí)候head和tail均為null。但head和tail又需要實(shí)實(shí)在在指向鏈表中的真實(shí)數(shù)據(jù)(帶頭指針就不需要考慮)。所以這時(shí)候就新建一個(gè)node讓head、tail等于它。

 
 
 
 
    
  
  
  
  
  1. node teamNode = new node(data); 
    2. 
  
  
  
  
  2. if (isEmpty()) { 
    3. 
  
  
  
  
  3.     head = teamNode; 
    4. 
  
  
  
  
  4.     tail = teamNode;     
    5. 
  
  
  
  
  5. } 
    6.

頭插

對于頭插入來說。步驟很簡單，只需考慮head節(jié)點(diǎn)的變化。

  1. 新建插入節(jié)點(diǎn)node
  2. head前驅(qū)指向node
  3. node后驅(qū)指向head
  4. head指向node。(這時(shí)候head只是表示第二個(gè)節(jié)點(diǎn)，而head需要表示第一個(gè)節(jié)點(diǎn)故改變指向)

尾插：

對于尾插入來說。只需考慮尾節(jié)點(diǎn)tail節(jié)點(diǎn)的變化。

  1. 新建插入節(jié)點(diǎn)node
  2. node前驅(qū)指向tail
  3. tail后驅(qū)指向node
  4. tail指向node。(這時(shí)候tail只是表示倒數(shù)第二個(gè)節(jié)點(diǎn)，而tail需要表示最后節(jié)點(diǎn)故指向node)

按編號插入

對于編號插入來說。要考慮查找和插入兩步，而插入既和head無關(guān)也和tail無關(guān)。

1 新建插入節(jié)點(diǎn)node

2 找到欲插入node的前一個(gè)節(jié)點(diǎn)preNode。和后一個(gè)節(jié)點(diǎn)nextNode

3 node后驅(qū)指向nextNode,nextNode前驅(qū)指向node(此時(shí)node和后面與鏈表已經(jīng)聯(lián)立，但是和前面處理分離狀態(tài))

4 preNode后驅(qū)指向node。node前驅(qū)指向preNode(此時(shí)插入完整操作完畢)

整個(gè)流程的動(dòng)態(tài)圖為：

刪除

只有單個(gè)節(jié)點(diǎn)刪除

無論頭刪還是尾刪，遇到單節(jié)點(diǎn)刪除的需要將鏈表從新初始化!

 
 
 
 
    
  
  
  
  
  1. if (length == 1)// 只有一個(gè)元素 
    2. 
  
  
  
  
  2. { 
    3. 
  
  
  
  
  3.     head = null; 
    4. 
  
  
  
  
  4.     tail = head; 
    5. 
  
  
  
  
  5.     length--; 
    6. 
  
  
  
  
  6. } 
    7.

頭刪除

頭刪除需要注意的就是刪除不為空時(shí)候頭刪除只和head節(jié)點(diǎn)有關(guān)

流程大致分為：

1 head節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)的前指針pre改為null。(head后面節(jié)點(diǎn)本指向head但是要?jiǎng)h除第一個(gè)先讓后面那個(gè)和head斷絕關(guān)系)

2 head節(jié)點(diǎn)指向head.next(這樣head就指向我們需要的第一個(gè)節(jié)點(diǎn)了，前面節(jié)點(diǎn)就被刪除成功，如果有c++等語言第一個(gè)被孤立的節(jié)點(diǎn)刪除釋放即可，但Java會自動(dòng)釋放)

尾刪除

尾刪除需要注意的就是刪除不為空時(shí)候尾刪除只和tail節(jié)點(diǎn)有關(guān)。記得在普通鏈表中，我們刪除尾節(jié)點(diǎn)需要找到尾節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。需要遍歷整個(gè)表，而雙向鏈表可以直接從尾節(jié)點(diǎn)遍歷到前面。

尾刪除就是刪除雙向鏈表中的最后一個(gè)節(jié)點(diǎn)，也就是尾指針?biāo)赶虻哪莻€(gè)節(jié)點(diǎn)，思想和頭刪除的思想一致，具體步驟為：

  1. tail.pre.next=null尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)(pre)的后驅(qū)節(jié)點(diǎn)等于null
  2. tail=tail.pre尾節(jié)點(diǎn)指向它的前驅(qū)節(jié)點(diǎn)，此時(shí)尾節(jié)點(diǎn)由于步驟1next已經(jīng)為null。完成刪除

普通刪除

普通刪除需要重點(diǎn)掌握，普通刪除要妥善處理好待刪除節(jié)點(diǎn)的前后關(guān)系，具體流程如下：

1：找到待刪除節(jié)點(diǎn)node的前驅(qū)節(jié)點(diǎn)prenode(prenode.next是要?jiǎng)h除的節(jié)點(diǎn))

2 : prenode.next.next.pre=prenode.(將待刪除node的后驅(qū)節(jié)點(diǎn)aftnode的pre指針指向prenode，等價(jià)于aftnode.pre=prenode)

3: prenode.next=prenode.next.next;此時(shí)node被跳過成功刪除。

完成刪除整個(gè)流程的動(dòng)態(tài)圖為：

實(shí)現(xiàn)與測試

通過上面的思路簡單的實(shí)現(xiàn)一下雙鏈表，當(dāng)然有些地方命名不太規(guī)范，實(shí)現(xiàn)效率有待提升，主要目的還是帶著大家理解。

代碼(代碼以圖片方式貼出，如需源碼可閱讀原文或者加我好友發(fā)你)：

測試：

結(jié)語

在插入刪除的步驟，很多人可能因?yàn)榉爆嵉倪^程而弄不明白，但實(shí)際上這個(gè)操作的寫法可能是多樣的，但本質(zhì)操作都是一致的，所以看到其他不同版本有差距也是正常的。

還有很多人可能對一堆next.next搞不清楚，那我教你一個(gè)技巧，如果在等號右側(cè)，那么它表示一個(gè)節(jié)點(diǎn)，如果在等號左側(cè)，那么除了最后一個(gè).next其他的表示節(jié)點(diǎn)。例如node.next.next.next可以看成(node.next.next).next。

在做數(shù)據(jù)結(jié)構(gòu)與算法鏈表相關(guān)題的時(shí)候，不同題可能給不同節(jié)點(diǎn)去完成插入、刪除操作。這種情況操作時(shí)候要謹(jǐn)慎先后順序防止破壞鏈表結(jié)構(gòu)。

代碼操作可能有些優(yōu)化空間，還請各位大佬指正!如有收獲


文章題目：雙鏈表，這回徹底搞dong了
當(dāng)前路徑：http://www.5511xx.com/article/dpgddpd.html