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

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

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

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

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

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

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

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

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

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

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

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

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

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

/**
 * display() 方法用于遍歷鏈表
 */
function display () {
  // 初始化當前節(jié)點為頭節(jié)點
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍歷輸出節(jié)點，并指向下一節(jié)點
    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()

// 輸出結(jié)果
Miyang
Tom
Jerry

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

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

/**
 * LList類 提供對鏈表操作的方法
 * find 用于查找元素
 * insert 用于插入新節(jié)點
 * display 用于遍歷顯示鏈表結(jié)構(gòu)
 * findPrev 用于遍歷查找待刪除數(shù)據(jù)的前一個節(jié)點
 * remove 用于刪除節(jié)點
 */
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() 方法用于通過遍歷鏈表，查找給定數(shù)據(jù)
 * 返回保存該數(shù)據(jù)的節(jié)點
 * @param {*} item
 */
function find (item) {
  // 初始化當前位置為鏈表頭部
  let currNode = this.head
  // 循環(huán)遍歷尋找當前位置并返回
  while ((currNode != null) && (currNode.element != null) && (currNode.next != null)) {
    currNode = currNode.next
  }
  return currNode
}

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

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

/**
 * remove() 方法用于刪除一個節(jié)點
 * @param {*} item
 */
function remove (item) {
  // 找到item數(shù)據(jù)節(jié)點的前驅(qū)節(jié)點
  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 () {
  // 初始化當前節(jié)點為頭節(jié)點
  let currNode = this.head
  while (!(currNode.next == null)) {
    // 遍歷輸出節(jié)點，并指向下一節(jié)點
    console.log(currNode.next.element)
    currNode = currNode.next
  }
}

/**
 * findLast() 方法用于找到鏈表中最后一個節(jié)點
 */
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()

// 輸出結(jié)果
Miyang
Tom
Jerry

Jerry
Tom
Miyang

循環(huán)鏈表和單向鏈表相似，唯一的區(qū)別是，在創(chuàng)建循環(huán)鏈表時，讓其頭節(jié)點的next屬性指向它本身，即：

head.next = head

修改LList類的構(gòu)造函數(shù)：

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()方法，否則會造成死循環(huán)

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

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

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

參考資料：數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述 第6章 鏈表
由于書上的源代碼出現(xiàn)了錯誤，因此代碼根據(jù)實際運行結(jié)果做了相應修改。