如需轉(zhuǎn)載, 請(qǐng)咨詢(xún)作者, 并且注明出處.
有任何問(wèn)題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326
前一節(jié)的篇幅有些多了, 所以我們將雙向鏈表放在這篇中介紹.
一. 認(rèn)識(shí)雙向鏈表
雙向鏈表介紹
-
單向鏈表:
- 只能從頭遍歷到尾或者從尾遍歷到頭(一般從頭到尾)
- 也就是鏈表相連的過(guò)程是單向的. 實(shí)現(xiàn)的原理是上一個(gè)鏈表中有一個(gè)指向下一個(gè)的引用.
- 單向鏈表有一個(gè)比較明顯的缺點(diǎn):
- 我們可以輕松的到達(dá)下一個(gè)節(jié)點(diǎn), 但是回到錢(qián)一個(gè)節(jié)點(diǎn)是很難的. 但是, 在實(shí)際開(kāi)發(fā)中, 經(jīng)常會(huì)遇到需要回到上一個(gè)節(jié)點(diǎn)的情況
- 舉個(gè)例子: 假設(shè)一個(gè)文本編輯用鏈表來(lái)存儲(chǔ)文本. 每一行用一個(gè)String對(duì)象存儲(chǔ)在鏈表的一個(gè)節(jié)點(diǎn)中. 當(dāng)編輯器用戶(hù)向下移動(dòng)光標(biāo)時(shí), 鏈表直接操作到下一個(gè)節(jié)點(diǎn)即可. 但是當(dāng)用于將光標(biāo)向上移動(dòng)呢? 這個(gè)時(shí)候?yàn)榱嘶氐缴弦粋€(gè)節(jié)點(diǎn), 我們可能需要從first開(kāi)始, 依次走到想要的節(jié)點(diǎn)上.
-
雙向鏈表
- 既可以從頭遍歷到尾, 又可以從尾遍歷到頭
- 也就是鏈表相連的過(guò)程是雙向的. 那么它的實(shí)現(xiàn)原理, 你能猜到嗎?
- 一個(gè)節(jié)點(diǎn)既有向前連接的引用, 也有一個(gè)向后連接的引用.
- 雙向鏈表可以有效的解決單向鏈表中提到的問(wèn)題.
- 雙向鏈表有什么缺點(diǎn)呢?
- 每次在插入或刪除某個(gè)節(jié)點(diǎn)時(shí), 需要處理四個(gè)節(jié)點(diǎn)的引用, 而不是兩個(gè). 也就是實(shí)現(xiàn)起來(lái)要困難一些
- 并且相當(dāng)于單向鏈表, 必然占用內(nèi)存空間更大一些.
- 但是這些缺點(diǎn)和我們使用起來(lái)的方便程度相比, 是微不足道的.
-
雙向連接的圖解:
img
雙向鏈表的創(chuàng)建
-
我們來(lái)創(chuàng)建一個(gè)雙向鏈表的類(lèi)
// 創(chuàng)建雙向鏈表的構(gòu)造函數(shù) function DoublyLinkedList() { // 創(chuàng)建節(jié)點(diǎn)構(gòu)造函數(shù) function Node(element) { this.element = element this.next = null this.prev = null // 新添加的 } // 定義屬性 this.length = 0 this.head = null this.tail = null // 新添加的 // 定義相關(guān)操作方法 }
-
代碼解析:
- 基本思路和單向鏈表比較相似, 都是創(chuàng)建節(jié)點(diǎn)結(jié)構(gòu)函數(shù)以及定義一些屬性和方法.
- 只是Node中添加了一個(gè)this.prev屬性, 該屬性用于指向上一個(gè)節(jié)點(diǎn).
- 另外屬性中添加了一個(gè)this.tail屬性, 該屬性指向末尾的節(jié)點(diǎn)
二. 操作雙向鏈表
雙向鏈表的操作和單向鏈表的方法都是類(lèi)似的.
只是在實(shí)現(xiàn)的過(guò)程中, 需要考慮更多節(jié)點(diǎn)之間的關(guān)系, 所以變得比單向鏈表復(fù)雜了一些.
尾部追加數(shù)據(jù)
-
我們還是先來(lái)實(shí)現(xiàn)尾部追加數(shù)據(jù)的方法
// 在尾部追加數(shù)據(jù) DoublyLinkedList.prototype.append = function (element) { // 1.根據(jù)元素創(chuàng)建節(jié)點(diǎn) var newNode = new Node(element) // 2.判斷列表是否為空列表 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } // 3.length+1 this.length++ }
-
代碼解析:
- 代碼1部分不用多講, 還是通過(guò)元素創(chuàng)建新的節(jié)點(diǎn).
- 代碼2部分相比之前有一些復(fù)雜, 但是還是兩種情況.
- 情況一: 鏈表原來(lái)為空
- 鏈表中原來(lái)如果沒(méi)有數(shù)據(jù), 那么直接讓head和tail指向這個(gè)新的節(jié)點(diǎn)即可.
- 情況二: 鏈表中已經(jīng)存在數(shù)據(jù)
- 因?yàn)槲覀兪且獙?shù)據(jù)默認(rèn)追加到尾部, 所以這個(gè)變得也很簡(jiǎn)單.
- 首先tail中的next之前指向的是null. 現(xiàn)在應(yīng)該指向新的節(jié)點(diǎn)newNode: this.tail.next = newNode
- 因?yàn)槭请p向鏈表, 新節(jié)點(diǎn)的next/tail目前都是null. 但是作為最后一個(gè)節(jié)點(diǎn), 需要有一個(gè)指向前一個(gè)節(jié)點(diǎn)的引用. 所以這里我們需要newNode.prev = this.tail
- 因?yàn)槟壳皀ewNod已經(jīng)變成了最后的節(jié)點(diǎn), 所以this.tail屬性的引用應(yīng)該指向最后: this.tail = newNode即可
- 代碼3部分不用多做解析, length需要+1
正向反向遍歷
-
鏈表的遍歷
- 之前我們?cè)趩蜗蜴湵碇袑?shí)現(xiàn)了一個(gè)toString方法, 它是一種正向的遍歷.
- 現(xiàn)在, 為了用戶(hù)使用方便, 我們實(shí)現(xiàn)三個(gè)方法
- forwardString: 正向遍歷轉(zhuǎn)成字符串的方法
- reverseString: 反向遍歷轉(zhuǎn)成字符串的方法
- toString: 正向遍歷轉(zhuǎn)成字符串的方法
-
方法的相關(guān)實(shí)現(xiàn):
// 正向遍歷的方法 DoublyLinkedList.prototype.forwardString = function () { var current = this.head var forwardStr = "" while (current) { forwardStr += "," + current.element current = current.next } return forwardStr.slice(1) } // 反向遍歷的方法 DoublyLinkedList.prototype.reverseString = function () { var current = this.tail var reverseStr = "" while (current) { reverseStr += "," + current.element current = current.prev } return reverseStr.slice(1) } // 實(shí)現(xiàn)toString方法 DoublyLinkedList.prototype.toString = function () { return this.forwardString() }
-
完成上面的代碼后, 測(cè)試append方法
// 1.創(chuàng)建雙向鏈表對(duì)象 var list = new DoublyLinkedList() // 2.追加元素 list.append("abc") list.append("cba") list.append("nba") list.append("mba") // 3.獲取所有的遍歷結(jié)果 alert(list.forwardString()) // abc,cba,nba,mba alert(list.reverseString()) // mba,nba,cba,abc alert(list) // abc,cba,nba,mba
任意位置插入
-
向雙向鏈表的任意位置插入數(shù)據(jù)會(huì)有一些復(fù)雜, 考慮的情況也會(huì)有一些多.
// 在任意位置插入數(shù)據(jù) DoublyLinkedList.prototype.insert = function (position, element) { // 1.判斷越界的問(wèn)題 if (position < 0 || position > this.length) return false // 2.創(chuàng)建新的節(jié)點(diǎn) var newNode = new Node(element) // 3.判斷插入的位置 if (position === 0) { // 在第一個(gè)位置插入數(shù)據(jù) // 判斷鏈表是否為空 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.head.prev = newNode newNode.next = this.head this.head = newNode } } else if (position === this.length) { // 插入到最后的情況 // 思考: 這種情況是否需要判斷鏈表為空的情況呢? 答案是不需要, 為什么? this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } else { // 在中間位置插入數(shù)據(jù) // 定義屬性 var index = 0 var current = this.head var previous = null // 查找正確的位置 while (index++ < position) { previous = current current = current.next } // 交換節(jié)點(diǎn)的指向順序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true }
-
代碼深度解析, 代碼比較復(fù)雜, 我們分成三種情況:
-
情況一: 將元素插入到頭部(position === 0)
- 事實(shí)上, 將元素插入到頭部是比較簡(jiǎn)單. 只是它有分成了兩種情況.
- 情況一: 列表為空. 那么直接讓head/tail指向newNode即可
- 情況二: 列表不為空, 這個(gè)時(shí)候需要修改原來(lái)head的prev指向新節(jié)點(diǎn). 新節(jié)點(diǎn)的next指向原來(lái)的head. 并且head現(xiàn)在要指向newNode
img -
情況二: 將元素插入到尾部(position === length)
- 這種情況比較簡(jiǎn)答了, 因?yàn)槲覀冊(cè)赼ppend方法中已經(jīng)處理過(guò)了.
- 注意: 這里不需要判斷元素為空的情況, 因?yàn)樵趐osition === 0的時(shí)候, 我們已經(jīng)處理過(guò)了. 所以到這里的時(shí)候, 肯定不為空.
img -
情況三: 將元素插入到中間位置
- 情況三是比較復(fù)雜一些的, 但是我們理清楚它的邏輯關(guān)系也就比較簡(jiǎn)單了.
- 首先, 我們需要找到正確的插入位置. 通過(guò)while循環(huán), 這個(gè)并不難, 因?yàn)槲覀冊(cè)趩蜗蜴湵淼臅r(shí)候已經(jīng)找過(guò)了.
- 查找正確的位置后, 需要進(jìn)行插入操作.
- 首先, 你的newNode的next/prev必然要指向前后的節(jié)點(diǎn), 也就是current和previous
- 其次, 而current的prev需要指向newNode, 而previous的next需要指向newNode.
- 邏輯搞定, 并沒(méi)有想象中的復(fù)雜, 詳細(xì)看圖解.
img
-
-
測(cè)試一下該方法
// 4.insert方法測(cè)試 list.insert(0, "100") list.insert(2, "200") list.insert(6, "300") alert(list) // 100,abc,200,cba,nba,mba,300
-
課下思考: 代碼性能能否改進(jìn)一點(diǎn)呢?
- 如果我們position大于length/2, 是否從尾部開(kāi)始迭代性能更高一些呢?
- 對(duì)于初學(xué)者來(lái)說(shuō), 可以作為思考. 但是先搞定上面的內(nèi)容吧.
位置移除數(shù)據(jù)
-
我們繼續(xù)來(lái)做下一個(gè)功能: 通過(guò)下標(biāo)值刪除某個(gè)元素
// 根據(jù)位置刪除對(duì)應(yīng)的元素 DoublyLinkedList.prototype.removeAt = function (position) { // 1.判斷越界的問(wèn)題 if (position < 0 || position >= this.length) return null // 2.判斷移除的位置 var current = this.head if (position === 0) { if (this.length == 1) { this.head = null this.tail = null } else { this.head = this.head.next this.head.prev = null } } else if (position === this.length -1) { current = this.tail this.tail = this.tail.prev this.tail.next = null } else { var index = 0 var previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } // 3.length-1 this.length-- return current.element }
-
代碼深度解析, 和插入一樣, 可以分成三種情況:
-
情況一: 刪除頭部的元素
- 刪除頭部的元素也分成兩種情況.
- 情況一: 鏈表只有一個(gè)元素, 那么將head/tail直接設(shè)置為null即可
- 情況二: 鏈表有多個(gè)元素, 這個(gè)時(shí)候刪除頭部的元素. head = head.next. head.prev = null
img -
情況二: 刪除尾部的元素
- 刪除尾部的元素和刪除頭部有多個(gè)元素的情況比較相似. (也不需要考慮個(gè)數(shù)為1的情況, 因?yàn)樯弦环N情況已經(jīng)考慮了)
- 將tail設(shè)置為tail的prev. tail的next設(shè)置為null即可.
img -
情況三: 刪除中間位置的元素
- 這種情況就需要先找到正確的位置, 還是使用while循環(huán).
- 將previous的next直接設(shè)置成current的next, 將current.next的prev設(shè)置成previous即可
img
-
-
測(cè)試removeAt方法
// 5.removeAt方法測(cè)試 alert(list.removeAt(0)) // 100 alert(list.removeAt(1)) // 200 alert(list.removeAt(4)) // 300 alert(list) // abc,cba,nba,mba
獲取元素位置
-
下面完成下一個(gè)功能: 根據(jù)元素獲取再鏈表中的位置
// 根據(jù)元素獲取在鏈表中的位置 DoublyLinkedList.prototype.indexOf = function (element) { // 1.定義變量保存信息 var current = this.head var index = 0 // 2.查找正確的信息 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.來(lái)到這個(gè)位置, 說(shuō)明沒(méi)有找到, 則返回-1 return -1 }
-
代碼解析:
- 這個(gè)代碼的實(shí)現(xiàn)和單向鏈表一樣, 不再解釋.
-
代碼測(cè)試:
// 6.indexOf方法測(cè)試 alert(list.indexOf("abc")) // 0 alert(list.indexOf("cba")) // 1 alert(list.indexOf("nba")) // 2 alert(list.indexOf("mba")) // 3
根據(jù)元素刪除
-
有了上面的indexOf方法, 我們可以非常方便實(shí)現(xiàn)根據(jù)元素來(lái)刪除信息
// 根據(jù)元素刪除 DoublyLinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) }
-
代碼解析:
- 和單向鏈表一樣, 不再解釋.
-
測(cè)試代碼:
// 7.remove方法測(cè)試 alert(list.remove("abc")) // abc alert(list) // cba,nba,mba
其他方法實(shí)現(xiàn)
-
其他四個(gè)方法, 放在一起了
// 判斷是否為空 DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0 } // 獲取鏈表長(zhǎng)度 DoublyLinkedList.prototype.size = function () { return this.length } // 獲取第一個(gè)元素 DoublyLinkedList.prototype.getHead = function () { return this.head.element } // 獲取最后一個(gè)元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.element }
-
代碼解析:
- 比較簡(jiǎn)單, 不再給出解釋了.
-
代碼測(cè)試:
// 8.測(cè)試最后四個(gè)方法 alert(list.getHead()) alert(list.getTail()) alert(list.isEmpty()) alert(list.size())
三. 完整代碼
-
給出雙向鏈表的完整代碼:
// 創(chuàng)建雙向鏈表的構(gòu)造函數(shù) function DoublyLinkedList() { // 創(chuàng)建節(jié)點(diǎn)構(gòu)造函數(shù) function Node(element) { this.element = element this.next = null this.prev = null // 新添加的 } // 定義屬性 this.length = 0 this.head = null this.tail = null // 新添加的 // 定義相關(guān)操作方法 // 在尾部追加數(shù)據(jù) DoublyLinkedList.prototype.append = function (element) { // 1.根據(jù)元素創(chuàng)建節(jié)點(diǎn) var newNode = new Node(element) // 2.判斷列表是否為空列表 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } // 3.length+1 this.length++ } // 在任意位置插入數(shù)據(jù) DoublyLinkedList.prototype.insert = function (position, element) { // 1.判斷越界的問(wèn)題 if (position < 0 || position > this.length) return false // 2.創(chuàng)建新的節(jié)點(diǎn) var newNode = new Node(element) // 3.判斷插入的位置 if (position === 0) { // 在第一個(gè)位置插入數(shù)據(jù) // 判斷鏈表是否為空 if (this.head == null) { this.head = newNode this.tail = newNode } else { this.head.prev = newNode newNode.next = this.head this.head = newNode } } else if (position === this.length) { // 插入到最后的情況 // 思考: 這種情況是否需要判斷鏈表為空的情況呢? 答案是不需要, 為什么? this.tail.next = newNode newNode.prev = this.tail this.tail = newNode } else { // 在中間位置插入數(shù)據(jù) // 定義屬性 var index = 0 var current = this.head var previous = null // 查找正確的位置 while (index++ < position) { previous = current current = current.next } // 交換節(jié)點(diǎn)的指向順序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true } // 根據(jù)位置刪除對(duì)應(yīng)的元素 DoublyLinkedList.prototype.removeAt = function (position) { // 1.判斷越界的問(wèn)題 if (position < 0 || position >= this.length) return null // 2.判斷移除的位置 var current = this.head if (position === 0) { if (this.length == 1) { this.head = null this.tail = null } else { this.head = this.head.next this.head.prev = null } } else if (position === this.length -1) { current = this.tail this.tail = this.tail.prev this.tail.next = null } else { var index = 0 var previous = null while (index++ < position) { previous = current current = current.next } previous.next = current.next current.next.prev = previous } // 3.length-1 this.length-- return current.element } // 根據(jù)元素獲取在鏈表中的位置 DoublyLinkedList.prototype.indexOf = function (element) { // 1.定義變量保存信息 var current = this.head var index = 0 // 2.查找正確的信息 while (current) { if (current.element === element) { return index } index++ current = current.next } // 3.來(lái)到這個(gè)位置, 說(shuō)明沒(méi)有找到, 則返回-1 return -1 } // 根據(jù)元素刪除 DoublyLinkedList.prototype.remove = function (element) { var index = this.indexOf(element) return this.removeAt(index) } // 判斷是否為空 DoublyLinkedList.prototype.isEmpty = function () { return this.length === 0 } // 獲取鏈表長(zhǎng)度 DoublyLinkedList.prototype.size = function () { return this.length } // 獲取第一個(gè)元素 DoublyLinkedList.prototype.getHead = function () { return this.head.element } // 獲取最后一個(gè)元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.element } // 遍歷方法的實(shí)現(xiàn) // 正向遍歷的方法 DoublyLinkedList.prototype.forwardString = function () { var current = this.head var forwardStr = "" while (current) { forwardStr += "," + current.element current = current.next } return forwardStr.slice(1) } // 反向遍歷的方法 DoublyLinkedList.prototype.reverseString = function () { var current = this.tail var reverseStr = "" while (current) { reverseStr += "," + current.element current = current.prev } return reverseStr.slice(1) } // 實(shí)現(xiàn)toString方法 DoublyLinkedList.prototype.toString = function () { return this.forwardString() } }