摘要：在存儲(chǔ)多個(gè)元素時(shí)，我們最常用的數(shù)據(jù)結(jié)構(gòu)可能是數(shù)組，究其原因可能是數(shù)組訪問方便，可以直接通過訪問，但是數(shù)組也存在一定的缺點(diǎn)，數(shù)組的大小是固定，數(shù)組在執(zhí)行插入或者刪除的時(shí)候成本很高。

在存儲(chǔ)多個(gè)元素時(shí)，我們最常用的數(shù)據(jù)結(jié)構(gòu)可能是數(shù)組，究其原因可能是數(shù)組訪問方便，可以直接通過[]訪問，但是數(shù)組也存在一定的缺點(diǎn)，數(shù)組的大小是固定，數(shù)組在執(zhí)行插入或者刪除的時(shí)候成本很高。

鏈表存儲(chǔ)的是有序的元素集合，和數(shù)組不同的是，鏈表中的元素在內(nèi)存并不是連續(xù)放置，每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用組成，結(jié)構(gòu)如下圖所示：

和數(shù)組相比，鏈表的優(yōu)勢在于：添加或者刪除元素不需要移動(dòng)其他元素,劣勢在與鏈表相對于數(shù)組結(jié)構(gòu)更復(fù)雜，需要一個(gè)指向下一個(gè)元素的指針，在訪問鏈表中的某個(gè)元素也需要從頭迭代，而不是像數(shù)組一樣直接訪問

首先讓我們來看一下鏈表的大概骨架，需要定義一些什么屬性：

function LinkedList() {
  let Node = function (element) {
    this.element = element
    this.next = null
  }
  let length = 0
  let head = null
  this.append = function (element) {
  }
  this.insert = function (position, element) {
  }
  this.removeAt = function (position) {
  }
  this.remove = function (element) {
  }
  this.indexOf = function (element) {
  }
  this.isEmpty = function () {
  }
  this.size = function () {
  }
  this.getHead = function () {
  }
  this.toString = function () {
  }
  this.print = function () {
  }
}

首先LinkedList里面需要定義一個(gè)Node輔助類，表示要加入鏈表的項(xiàng)，包含一個(gè)element屬性和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針next，接下來定義了一個(gè)指針的頭head和指針的長度length，然后就是最重要的類里面的方法，接下來就讓我們一起來看這些方法的職責(zé)和實(shí)現(xiàn)

鏈表在向尾部追加元素的時(shí)候有兩種情況：鏈表為空，添加的是第一個(gè)元素，或者鏈表不為空，追加元素，下面來看具體實(shí)現(xiàn)：

this.append = function (element) {
    let node = new Node(element), current
    if (head === null) {
      head = node // 鏈表為空時(shí)，插入
    } else {
      current = node
      while (current.next) { // 循環(huán)鏈表，直到最后一項(xiàng)
        current = current.next
      }
      current.next = node // 找到最后一項(xiàng)，將新增元素連接
    }
    length++
  }

現(xiàn)在讓我們先來看第一個(gè)種情況，鏈表為空時(shí)，插入就直接是頭，因此直接將node賦值給head就行，第二種情況，當(dāng)鏈表有元素時(shí)，就需要先循環(huán)鏈表，找到最后一項(xiàng)，然后將最后一項(xiàng)的next指針指向node

現(xiàn)在讓我們來看看怎么從指定位置移除元素，移除元素也有兩個(gè)場景，第一種是移除第一個(gè)元素，第二種是移除第一個(gè)以外的任意一個(gè)元素，來看具體實(shí)現(xiàn)：

this.removeAt = function (position) {
    if (position > -1 && position < length) { // 判斷邊界
      let previous, index = 0, current = head
      if (position === 0) { // 移除第一項(xiàng)
        head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }

接下來一起來分析一下上面的代碼，首先判斷要?jiǎng)h除的位置是不是有效的位置，然后來看第一種情況，當(dāng)移除的元素是第一項(xiàng)是時(shí)，此時(shí)直接將head指向第二個(gè)元素就行了，第二種情況就會(huì)稍微復(fù)雜一點(diǎn)，首先需要一個(gè)index控制遞增，previous記錄前一個(gè)位置，移除當(dāng)前元素，就是將前一個(gè)元素的next指向下一個(gè)元素，來看一個(gè)示意圖：

因此在while循環(huán)中始終用previous記錄上一個(gè)位置元素，current記錄下一個(gè)元素，跳出循環(huán)時(shí)，上一個(gè)元素的next指針指向當(dāng)前元素的next指針指向的元素，就將當(dāng)前元素移出鏈表

接下來來看在任意位置插入的insert方法，這個(gè)方法同樣需要考慮兩種情況，插入位置在頭部和插入位置不在頭部，下面來看一下具體實(shí)現(xiàn)：

this.insert = function (position, element) {
    if (position > -1 && position <= length) {
      let node = new Node(element),previous, index = 0, current = head
      if (position === 0) {
        node.next = current
        head = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current
      }
      length++
      return true
    } else {
      return false
    }
  }

先來看第一種情況，鏈表起點(diǎn)添加一個(gè)元素，將node.next指向current，然后再將node的引用賦值給head，這樣就再鏈表的起點(diǎn)添加了一個(gè)元素，第二種情況，在其他位置插入一個(gè)元素，previous是插入元素的前一個(gè)元素，current為插入元素的后一個(gè)元素，想要插入一個(gè)元素，就需要將前一個(gè)元素的next指向要插入的元素，要插入元素的next指向下一個(gè)元素，來看示意圖：

如上圖所示：將新項(xiàng)node插入到previous和current之間，需要將previous.next指向node，node.next指向current，這樣就在鏈表中插入了一個(gè)新的項(xiàng)

toString方法會(huì)把LinkedList對象轉(zhuǎn)換成一個(gè)字符串，下面來看具體實(shí)現(xiàn)：

this.toString = function () {
    let current = head, string = ""
    while (current) {
      string += current.element + (current.next ? "n" : "")
      current = current.next
    }
    return string
  }

循環(huán)遍歷所有元素，以head為起點(diǎn)，當(dāng)存在下一個(gè)元素時(shí)，就將其拼接到字符串中，直到next為null

indexOf方法返回對應(yīng)元素的位置，存在就返回對應(yīng)的索引，不存在返回-1，來看具體的實(shí)現(xiàn)：

this.indexOf = function (element) {
    let current = head, index = 0
    while (current) {
      if (current.element === element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }

遍歷鏈表，當(dāng)前元素的值與目標(biāo)值一致時(shí)返回元素的位置index，遍歷完鏈表還沒找到則返回-1

由于這幾個(gè)方法實(shí)現(xiàn)比較簡單，直接來看具體實(shí)現(xiàn)：

this.remove = function (element) { // 移除指定元素
    let index = this.indexOf(element)
    return this.removeAt(index)
  }
this.isEmpty = function () { // 判斷鏈表是否為空
    return length === 0
  }
this.size = function () { // 獲取鏈表長度
    return length
  }
this.getHead = function () { // 獲取鏈表頭
    return head
  }

這篇文章主要對鏈表做了簡單介紹，對鏈表的簡單實(shí)現(xiàn)。如果有錯(cuò)誤或不嚴(yán)謹(jǐn)?shù)牡胤剑瑲g迎批評指正，如果喜歡，歡迎點(diǎn)贊。