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

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

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

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

要標(biāo)識(shí)出鏈表的起始節(jié)點(diǎn)有些麻煩，因此我們經(jīng)常會(huì)在鏈表最前面有一個(gè)特殊節(jié)點(diǎn)，叫做頭節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

// 測(cè)試代碼
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

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

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

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

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

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

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

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

// 測(cè)試代碼
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)鏈表時(shí)，讓其頭節(jié)點(diǎn)的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
}

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

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

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

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

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