JavaScript數據結構之雙向鏈表

// 創建雙向鏈表的構造函數
function DoublyLinkedList() {
 // 創建節點構造函數
 function Node(element) {
  this.element = element
  this.next = null
  this.prev = null // 新添加的
 }

 // 定義屬性
 this.length = 0
 this.head = null
 this.tail = null // 新添加的

 // 定義相關操作方法
 // 在尾部追加數據
 DoublyLinkedList.prototype.append = function (element) {
  // 1.根據元素創建節點
  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++
 }

 // 在任意位置插入數據
 DoublyLinkedList.prototype.insert = function (position, element) {
  // 1.判斷越界的問題
  if (position < 0 || position > this.length) return false

  // 2.創建新的節點
  var newNode = new Node(element)

  // 3.判斷插入的位置
  if (position === 0) { // 在第一個位置插入數據
   // 判斷鏈表是否為空
   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 { // 在中間位置插入數據
   // 定義屬性
   var index = 0
   var current = this.head
   var previous = null

   // 查找正確的位置
   while (index++ < position) {
    previous = current
    current = current.next
   }

   // 交換節點的指向順序
   newNode.next = current
   newNode.prev = previous
   current.prev = newNode
   previous.next = newNode
  }

  // 4.length+1
  this.length++

  return true
 }

 // 根據位置刪除對應的元素
 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
 }

 // 根據元素獲取在鏈表中的位置
 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
 }

 // 根據元素刪除
 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
 }

 // 遍歷方法的實現
 // 正向遍歷的方法
 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)
 }

 // 實現toString方法
 DoublyLinkedList.prototype.toString = function () {
  return this.forwardString()
 }
}