摘要：前言數組是我們非常熟悉且常用的一種數據結構。但我們發現，數組不總是組織數據的最佳數據結構。參考資料數據結構與算法描述第章鏈表由于書上的源代碼出現了錯誤，因此代碼根據實際運行結果做了相應修改。

數組是我們非常熟悉且常用的一種數據結構。但我們發現，數組不總是組織數據的最佳數據結構。因為在很多編程語言中，數組的長度是固定的，所以當數組已經被數據填滿時，再加入新的元素就會非常困難。同時，在數組中添加或刪除元素也很麻煩，因為需要將數組中的其他元素向前或向后平移，以反映數組進行了添加或刪除的操作。
雖然說在JavaScript中的數組不存在上述問題，我們使用splice()方法不需要再訪問數組中的其他元素。但是在JavaScript中，數組被實現成了對象，因此與其他語言中的數組相比，效率很低。
在很多情況下，當我們發現數組在實際使用時很慢，就可以考慮使用鏈表來代替它。除了對數據的隨機訪問，鏈表幾乎可以用在任何可以使用一維數組的情況中。如果需要隨機訪問，數組仍然是最好的選擇。

鏈表是由一組節點組成的集合。每個節點都使用一個對象的引用指向它的后繼。指向另一個節點的引用叫做鏈。如下圖所示

數組元素依靠它們的位置進行引用，而鏈表元素依靠相互關系進行引用。如我們可以說Item2在Item1后面，而不能說Item2是鏈表中的第二個元素。
我們所說的遍歷鏈表，就是跟著鏈接，從鏈表的首元素一直走到尾元素（不包括鏈表的頭節點）。
我們可以發現，鏈表的尾元素指向一個null節點。

要標識出鏈表的起始節點有些麻煩，因此我們經常會在鏈表最前面有一個特殊節點，叫做頭節點。

鏈表中插入一個節點的效率很高，我們只需要修改其前面的節點，使其指向新加入的節點，同時將新加入的節點指向原來前驅指向的節點即可。

鏈表中刪除一個節點也非常容易。將待刪元素的前驅節點指向待刪元素的后繼節點，再講待刪元素指向null即可。

我們將用JavaScript構造一個基于對象的鏈表結構，各部分功能使用注釋說明。

/**
 * Node類 表示節點，我們使用構造函數來創建節點
 * element 用來保存節點上的數據
 * next 用來保存指向下一個節點的鏈接
 * @param {*} element
 */
function Node (element) {
  this.element = element
  this.next = null
}

/**
 * LList類 提供對鏈表操作的方法
 * find 用于查找元素
 * insert 用于插入新節點
 * display 用于遍歷顯示鏈表結構
 * findPrev 用于遍歷查找待刪除數據的前一個節點
 * remove 用于刪除節點
 */
function LList () {
  this.head = new Node("head")
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
}

/**
 * find() 方法用于通過遍歷鏈表，查找給定數據
 * 返回保存該數據的節點
 * @param {*} item
 */
function find (item) {
  // 初始化當前位置為鏈表頭部
  let currNode = this.head
  // 循環遍歷尋找當前位置并返回
  while ((currNode != null) && (currNode.element != null) && (currNode.next != null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * insert() 方法用于插入新節點
 * @param {*} newEle
 * @param {*} item
 */
function insert (newEle, item) {
  // 創建新節點
  let newNode = new Node(newEle)
  // 查找要插入的節點位置
  let current = this.find(item)
  // 將新節點的后繼指向要插入位置的后繼
  if (current != null) {
    newNode.next = current.next
    // 將要插入位置的后繼指向新節點
    current.next = newNode
  } else {
    // current 為null時
    newNode.next = null
    this.head.next = newNode
  }
}

/**
 * findPrev() 方法用于遍歷查找待刪除數據的前一個節點
 * @param {*} item
 */
function findPrev (item) {
  // 初始化當前節點為頭節點
  let currNode = this.head
  // 當前節點的后繼為item時停止遍歷并返回，即返回待查找節點的前驅節點
  while (!(currNode.next == null) && (currNode.next.element != item)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * remove() 方法用于刪除一個節點
 * @param {*} item
 */
function remove (item) {
  // 找到item數據節點的前驅節點
  let prevNode = this.findPrev(item)
  if (!(prevNode.next == null)) {
    // 將前驅節點的后繼節點賦值為其后繼節點的后繼節點，即跳過了待刪節點
    prevNode.next = prevNode.next.next
  }
}

/**
 * display() 方法用于遍歷鏈表
 */
function display () {
  // 初始化當前節點為頭節點
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍歷輸出節點，并指向下一節點
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

// 測試代碼
let students = new LList()
students.insert("Miyang", "head")
students.insert("Tom", "Miyang")
students.insert("Jerry", "Tom")
students.remove("Tom")
students.display()

// 輸出結果
Miyang
Tom
Jerry

關于雙向鏈表的實現，我們只需要在單向鏈表的基礎上，增加一個指向前驅節點的鏈接。
實現代碼如下：

/**
 * Node類 表示節點，我們使用構造函數來創建節點
 * element 用來保存節點上的數據
 * next 用來保存指向下一個節點的鏈接
 * @param {*} element
 */
function Node (element) {
  this.element = element
  this.next = null
  this.previous = null
}

/**
 * LList類 提供對鏈表操作的方法
 * find 用于查找元素
 * insert 用于插入新節點
 * display 用于遍歷顯示鏈表結構
 * findPrev 用于遍歷查找待刪除數據的前一個節點
 * remove 用于刪除節點
 */
function LList () {
  this.head = new Node("head")
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
  this.findLast = findLast
  this.dispReverse = dispReverse
}

/**
 * find() 方法用于通過遍歷鏈表，查找給定數據
 * 返回保存該數據的節點
 * @param {*} item
 */
function find (item) {
  // 初始化當前位置為鏈表頭部
  let currNode = this.head
  // 循環遍歷尋找當前位置并返回
  while ((currNode != null) && (currNode.element != null) && (currNode.next != null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * insert() 方法用于插入新節點
 * @param {*} newEle
 * @param {*} item
 */
function insert (newEle, item) {
  // 創建新節點
  let newNode = new Node(newEle)
  // 查找要插入的節點位置
  let current = this.find(item)
  // 將新節點的后繼指向要插入位置的后繼
  if (current != null) {
    newNode.next = current.next
    newNode.previous = current
    // 將要插入位置的后繼指向新節點
    current.next = newNode
  } else {
    // current 為null時
    newNode.next = null
    newNode.previous = null
    this.head.next = newNode
  }
}

/**
 * findPrev() 方法用于遍歷查找待刪除數據的前一個節點
 * @param {*} item
 */
function findPrev (item) {
  // 初始化當前節點為頭節點
  let currNode = this.head
  // 當前節點的后繼為item時停止遍歷并返回，即返回待查找節點的前驅節點
  while (!(currNode.next == null) && (currNode.next.element != item)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * remove() 方法用于刪除一個節點
 * @param {*} item
 */
function remove (item) {
  // 找到item數據節點的前驅節點
  let currNode = this.find(item)
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next
    currNode.next.previous = currNode.previous
    currNode.next = null
    currNode.previous = null
  }
}

/**
 * display() 方法用于遍歷鏈表
 */
function display () {
  // 初始化當前節點為頭節點
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍歷輸出節點，并指向下一節點
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

/**
 * findLast() 方法用于找到鏈表中最后一個節點
 */
function findLast () {
  let currNode = this.head
  while (!(currNode.next == null)) {
    currNode = currNode.next
  }
  return currNode
}

/**
 * dispReverse() 方法用于反向遍歷鏈表
 */
function dispReverse () {
  let currNode = this.head
  currNode = this.findLast()
  while (!(currNode.previous == null)) {
    console.log(currNode.element)
    currNode = currNode.previous
  }
}

// 測試代碼
let students = new LList()
students.insert("Miyang", "head")
students.insert("Tom", "Miyang")
students.insert("Jerry", "Tom")
students.remove("Tom")
students.display()
console.log()
students.dispReverse()

// 輸出結果
Miyang
Tom
Jerry

Jerry
Tom
Miyang

循環鏈表和單向鏈表相似，唯一的區別是，在創建循環鏈表時，讓其頭節點的next屬性指向它本身，即：

head.next = head

修改LList類的構造函數：

function LList () {
  this.head = new Node("head")
  this.head.next = this.head
  this.find = find
  this.insert = insert
  this.display = display
  this.findPrev = findPrev
  this.remove = remove
  this.findLast = findLast
  this.dispReverse = dispReverse
}

同時，其他地方也需要修改，如display()方法，否則會造成死循環

function display () {
  // 初始化當前節點為頭節點
  let currNode = this.head
  while (!(currNode.next == null) && !(currNode.next.element == "head")) {
    // 遍歷輸出節點，并指向下一節點
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

同樣的，其他方法也需要做類似修改，在此就不一一舉例了。

上面對JavaScript實現鏈表做了基本介紹，大家也可以嘗試去定義一些其他方法，如在鏈表中向前移動n個節點advance(n)、在雙向鏈表中向后移動n個節點back(n)等。

參考資料：數據結構與算法JavaScript描述 第6章 鏈表
由于書上的源代碼出現了錯誤，因此代碼根據實際運行結果做了相應修改。