如何在JavaScript中使用雙向鏈表

這篇文章給大家介紹如何在JavaScript中使用雙向鏈表，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

JavaScript的特點(diǎn)

1.JavaScript主要用來向HTML頁面添加交互行為。 2.JavaScript可以直接嵌入到HTML頁面，但寫成單獨(dú)的js文件有利于結(jié)構(gòu)和行為的分離。 3.JavaScript具有跨平臺(tái)特性，在絕大多數(shù)瀏覽器的支持下，可以在多種平臺(tái)下運(yùn)行。

// 創(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.判斷越界的問題
  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.判斷越界的問題
  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.來到這個(gè)位置, 說明沒有找到, 則返回-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
 }

 // 獲取第一個(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()
 }
}

關(guān)于如何在JavaScript中使用雙向鏈表就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。