6.雙向鏈表
認識雙向鏈表
回顧單向鏈表：
只能從頭遍歷到尾或者從尾遍歷到頭（一般從頭到尾）
也就是鏈表相連的過程是單向的
實現的原理是上一個鏈表中有一個指向下一個的引用
單向鏈表有一個比較明顯的缺點：
我們可以輕松的到達下一個節點，但是回到前一個節點是很難得。
但是，在實際開發中，經常會遇到需要回到上一個節點的情況
舉個例子：假設一個文本編輯用鏈表來存儲文本。每一行用一個
String對象存儲在鏈表的一個節點中。當編輯器用戶向下移動時，
鏈表直接操作到下一個節點即可。但是當用于將光標向上以動呢？
這個時候為了回到上一個節點，我們可能需要從first開始，依次
走到想要的節點上。
雙向鏈表：
既可以從頭遍歷到尾，又可以從尾遍歷到頭
也就是鏈表項鏈的過程是雙向的。那么它的實現原理，你能猜到嗎？
一個節點既有向前連接的引用，也有一個向后連接的引用。
雙向鏈表可以有效的解決單向鏈表中提到的為題。
雙向鏈表有什么缺點呢？
每次在插入或刪除某個節點時，需要處理四個引用，而不是兩個。
也就是實現起來要肯難一些
并且相當于單向鏈表，必然占用空間更大一些。
但是這些缺點和我們使用起來的方便程度相比，是微不足道的。
雙向鏈表長什么樣子？
雙向鏈表的特點：
可以使用一個head和一個tail分別指向頭部和尾部的節點
每個節點都由三部分組成：前一個節點的指針 （prev）/保存的元素（item）/后一天節點的指針（next）
雙向鏈表的第一個節點的prev是null
雙向鏈表的最后的節點的next是null
雙向鏈表常見操作
append方法
向鏈表尾部追加數據可能有兩種：
鏈表本身為空，新添加的數據時唯一的節點。
鏈表不為空，需要向其他的節點后面追加節點。
append方法代碼
// append方法
DoublyLinkedList.prototype.append = function(data) {
// 根據data創建節點
var newNode = new Node(data)
// 判斷添加的是否哦時第一個節點
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
newNode.prey = this.tail
this.tail.next = newNode
this.tail = newNode
}
// length + 1
this.length += 1
}
toString方法
由于列表項使用了Node類，就需要重寫繼承自JavaScript對象默認的toString方法，讓其只輸出元素的值
// toString方法
DoubleLinklist.prototype.toString = function() {
return this.backwardString()
}
forwardString方法
返回正向遍歷的節點字符串形式
// forwardString方法
DoubleLinklist.prototype.forwardString = function() {
// 定義變量
var current = this.tail
var resultString = ""
// 依次向前遍歷，獲取每一個節點
while (current) {
resultString += current.data + "--"
current = current.prev
}
return resultString
}
backwordString方法
返回反向遍歷的節點字符串形式
// backwardString方法
DoubleLinklist.prototype.backwardString = function() {
// 定義變量
var current = this.head
var resultString = ""
// 依次向后遍歷，獲取每一個節點
while (current) {
resultString += current.data + "--"
current = current.next
}
return resultString
}
insert方法
向列表特定位置插入一個新的項
// insert方法
DoubleLinklist.prototype.insert = function(position, data) {
// 越界判斷
if (position < 0 || position > this.length) return false
// 根據data創建新的節點
var newNode = new Node(data)
// 判斷原來的列表是否為空
if (this.length == 0) {
this.head = newNode
this.tail = newNode
} else {
if (position == 0) { // 判斷position是都為0
this.head.prev = newNode
newNode.next = this.head
this.head = newNode
} else if (position == this.length) { // position == length
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
} else {
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
// 修改指針
newNode.next = current
newNode.prev = current.prev
current.prev.next = newNode
current.prev = newNode
}
}
// length + 1
this.length += 1
return true
}
get方法
獲取對應位置的元素
// get方法
DoubleLinklist.prototype.get = function(position) {
// 越界判斷
if (position < 0 || position >= this.length) return null
// this.length / 2 > position:從頭向后遍歷
// this.length / 2 < position:從后向前遍歷
// 獲取元素
var current = this.head
var index = 0
while (index++ < position) {
current = current.next
}
return current.data
}
indexOf方法
返回元素在列表中的索引。如果列表中沒有該元素則返回-1
// indexOf方法
DoubleLinklist.prototype.indexOf = function(data) {
// 定義變量
let current = this.head
let index = 0
// 查找和data相同的節點
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}
return -1
}
update方法
修改某個位置的元素
// update方法
DoubleLinklist.prototype.update = function(position, newData) {
// 跨界判斷
if (position < 0 || position >= this.length) return false
// 尋找正確的節點
let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
// 修改找到節點的data信息
current.data = newData
return current.data
}
removeAt方法
從列表的特定位置移除一項
// removeAt方法
DoubleLinklist.prototype.removeAt = function(position) {
// 越界判斷
if (position < 0 || position >= this.length) return null
// 判斷是否只有一個節點
let current = this.head
if (this.length == 1) {
this.head = null
this.tail = null
} else {
if (position == 0) { // 判斷是否刪除的是第一個節點
this.head.next.prev = null
this.tail = this.head.next
} else if (position == this.length - 1) { // 最后節點
this.tail.prev.next = null
this.tail = this.tail.prev
} else {
let index = 0
while (index++ < position) {
current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev
}
}
// length - 1
this.length -= 1
return current.data
}
removef方法
從列表中移除一項
// remove方法
DoubleLinklist.prototype.remove = function(data) {
// 根據data獲取下標值
let index = this.indexOf(data)
// 根據index刪除對應位置的節點
return this.removeAt(index)
}
isEmpty方法
如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0則返回false
// isEmpty方法
DoubleLinklist.prototype.isEmpty = function() {
return this.length == 0
}
sizi方法
返回鏈表包含的元素個數。與數組的length屬性類似
// size方法
DoubleLinklist.prototype.size = function() {
return this.length
}
其他方法
獲取鏈表的第一個元素，獲取鏈表的最后一個元素
// 獲取鏈表的第一個元素
DoubleLinklist.prototype.getHead = function() {
return this.head.data
}
// 獲取鏈表的最后一個元素
DoubleLinklist.prototype.getTail = function() {
return this.tail.data
}
浙公網安備 33010602011771號