單向鏈表在遍歷時只能從頭到尾或者從尾遍歷到頭；所以單向鏈表可以輕松到達(dá)下一節(jié)點，但是回到上一個節(jié)點是很困難的

而雙向鏈表既可以從頭遍歷到尾, 又可以從尾遍歷到頭，鏈表的相聯(lián)是雙向的，一個節(jié)點既有向前連接的引用，也有向后連接的引用

但是正因如此，雙向鏈表在插入或者刪除某個節(jié)點時，需要處理四個節(jié)點的引用，并且所占用內(nèi)存空間也更大一些

雙向鏈表實現(xiàn)

JavaScript 代碼實現(xiàn)雙向鏈表

// 創(chuàng)建雙向鏈表的構(gòu)造函數(shù)function DoublyLinkedList() { // 創(chuàng)建節(jié)點構(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é)點 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.判斷越界的問題 if (position < 0 || position > this.length) return false // 2.創(chuàng)建新的節(jié)點 var newNode = new Node(element) // 3.判斷插入的位置 if (position === 0) { // 在第一個位置插入數(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é)點的指向順序 newNode.next = current newNode.prev = previous current.prev = newNode previous.next = newNode } // 4.length+1 this.length++ return true } // 根據(jù)位置刪除對應(yīng)的元素 DoublyLinkedList.prototype.removeAt = function (position) { // 1.判斷越界的問題 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.來到這個位置, 說明沒有找到, 則返回-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 } // 獲取鏈表長度 DoublyLinkedList.prototype.size = function () { return this.length } // 獲取第一個元素 DoublyLinkedList.prototype.getHead = function () { return this.head.element } // 獲取最后一個元素 DoublyLinkedList.prototype.getTail = function () { return this.tail.element } // 遍歷方法的實現(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) } // 實現(xiàn)toString方法 DoublyLinkedList.prototype.toString = function () { return this.forwardString() }}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。