摘要：本系列所有文章第一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹簡(jiǎn)單介紹鏈表鏈表一種常見的數(shù)據(jù)結(jié)構(gòu)，可

本系列所有文章：
第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列
第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹

鏈表一種常見的數(shù)據(jù)結(jié)構(gòu)，可以存儲(chǔ)有序的元素集合。不同于數(shù)組，鏈表中元素在內(nèi)存中不是連續(xù)放置，同時(shí)每一個(gè)鏈表元素中除了本身的節(jié)點(diǎn)還保存了指向下一個(gè)元素的引用，這些特點(diǎn)使得鏈表元素在動(dòng)態(tài)增加和刪除時(shí)不必移動(dòng)其他元素，但是訪問鏈表元素時(shí)必須從起點(diǎn)開始迭代列表直到找到目標(biāo)元素。

下面是兩種鏈表的JavaScript實(shí)現(xiàn)：

下圖就是一個(gè)典型的單向鏈表，這里注意：一般鏈表中的第一個(gè)元素會(huì)有一個(gè)head指針指向它，這也是我們操作鏈表必不可少的一環(huán)。

（圖片來源谷歌，侵刪）

與之前實(shí)現(xiàn)棧和隊(duì)列一樣，這里先聲明一個(gè)構(gòu)造函數(shù)：

function LinkedList () {
  var Node = function (element) {
    this.element = element
    // 保存指向下個(gè)元素的引用，默認(rèn)為null
    this.next = null
  }
  
  // 鏈表長(zhǎng)度
  var length = 0
  // head保存指向第一個(gè)元素的引用
  var head = null
}

鏈表需要實(shí)現(xiàn)以下方法：

append(element)：向鏈表尾部添加元素

insert(position, element)：向鏈表特定位置插入元素

removeAt(position)：從鏈表特定位置移除一項(xiàng)

remove(element)：在鏈表中移除某元素

indexOf(element)：返回元素在鏈表中的索引，若不存在則返回-1

isEmpty()：如果鏈表不包含任何元素就返回true，否則為false

size()：返回鏈表長(zhǎng)度

toString()：返回元素的值轉(zhuǎn)成字符串

類似數(shù)組的push方法，但是只能添加一個(gè)元素。實(shí)現(xiàn)方法的時(shí)候分兩種情況考慮：1. 鏈表為空時(shí)添加第一個(gè)元素；2. 鏈表不為空時(shí)在尾部添加元素

this.append = function (element) {

  var node = new Node(element),
      current

  if (head === null) { // 當(dāng)鏈表為空時(shí)
    // 將head指向新增的元素
    head = node
  } else { // 鏈表不為空
    // 使用一個(gè)current變量從head開始迭代鏈表
    current = head

    // 迭代鏈表，直到找到最后一項(xiàng)
    while (current.next) {
      current = current.next
    }

    // 找到最后一項(xiàng)，將其next賦為node，建立鏈接
    current.next = node
  }

  // 更新列表長(zhǎng)度
  length++
}

在鏈表中特定位置移除元素，實(shí)現(xiàn)時(shí)也需要考慮兩種情況：1. 移除第一個(gè)元素；2. 移除其他元素（包括最后一個(gè)）

this.removeAt = function (position) {
  // 判斷位置是否越界
  if (position > -1 && position < length) {
    var current = head,
        previous,
        index = 0

    // 如果刪除了第一個(gè)元素，把head指向下一個(gè)元素就行了
    if (position === 0) {
      head = current.next
    } else {
      // 根據(jù)輸入的位置查找要?jiǎng)h除的元素
      while (index++ < position) {
        previous = current
        current = current.next
      }
      // 將上一個(gè)元素的next指向current的下一項(xiàng)，跳過current，實(shí)現(xiàn)移除current
      previous.next = current.next
    }

    // 更新列表長(zhǎng)度
    length--

    // 返回刪除的元素
    return current.element
  } else {
    return null
  }
}

與removeAt類似的實(shí)現(xiàn)，大家可以先不看源碼，自己按著removeAt的思路實(shí)現(xiàn)一遍

this.insert = function (position, element) {
  // 檢查位置是否越界
  if (position >= 0 && position <= length) {
    var node = new Node(element),
        index = 0,
        previous,
        current = head

    // 在第一個(gè)位置添加
    if (position === 0) {

      node.next = current
      head = node

    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }

      node.next = current
      previous.next = node
    }

    // 更新列表長(zhǎng)度
    length++

    return true
} else {
  return false
}
}

根據(jù)元素查找在鏈表中的位置，沒找到就返回-1

this.indexOf = function (element) {
  var current = head,
      index = 0

  while (current) {
    if (element === current.element) {
      return index
    }
    index++
    current = current.next
  }

  return -1
}

// 返回所有元素的值轉(zhuǎn)成字符串
this.toString = function () {
  var current = head,
      string = ""

  while (current) {
    string += current.element
    current = current.next
  }

  return string
}

// 移除特定元素
this.remove = function (element) {
  var index = this.indexOf(element)
  return this.removeAt(index)
}

// 判斷鏈表是否為空
this.isEmpty = function () {
  return length === 0
}

// 返回鏈表長(zhǎng)度
this.size = function () {
  return length
}

// 返回第一個(gè)元素
this.getHead = function () {
  return head
}

以上是單向鏈表的實(shí)現(xiàn)，有興趣的可以下載源碼來看：

單向鏈表的實(shí)現(xiàn)-源代碼

雙向鏈表和單向鏈表的區(qū)別就是每一個(gè)元素是雙向的，一個(gè)元素中包含兩個(gè)引用：一個(gè)指向前一個(gè)元素；一個(gè)指向下一個(gè)元素。除此之外，雙向鏈表還有一個(gè)指向最后一個(gè)元素的tail指針，這使得雙向鏈表可以從頭尾兩個(gè)方向迭代鏈表，因此更加靈活。如下圖：

(圖片來源谷歌搜索，侵刪)

同單向鏈表一樣，先聲明一個(gè)構(gòu)造函數(shù)

function DoubleLinkedList () {
  var Node = function (element) {
    this.element = element
    this.prev = null // 新增了一個(gè)指向前一個(gè)元素的引用
    this.next = null
  }

  var length = 0
  var head = null
  var tail = null //新增了tail指向最后一個(gè)元素
}

雙向鏈表需要有以下方法：

append(element)：向鏈表尾部添加元素

insert(position, element)：向鏈表特定位置插入元素

removeAt(position)：從鏈表特定位置移除一項(xiàng)

showHead()：獲取雙向鏈表的頭部

showLength()：獲取雙向鏈表長(zhǎng)度

showTail()：獲取雙向鏈表尾部

同單向鏈表類似，只不過情況更復(fù)雜了，你不僅需要額外考慮在第一個(gè)元素的位置插入新元素，還要考慮在最后一個(gè)元素之后插入新元素的情況。此外如果在第一個(gè)元素插入時(shí)，鏈表為空的情況也需要考慮。

this.insert = function (position, element) {
  // 檢查是否越界
  if (position >= 0 && position <= length) {
    var node = new Node(element),
        current = head,
        previous,
        index = 0

    if (position === 0) { // 第一個(gè)元素的位置插入
      // 如果鏈表為空
      if (!head) {
        head = node
        tail = node
      } else {
        node.next = current
        current.prev = node
        head = node
      }
    } else if (position === length) { // 在最后一個(gè)元素之后插入
      current = tail
      node.prev = current
      current.next = node
      tail = node
    } else { // 在中間插入
      while (index++ < position) {
        previous = current
        current = current.next
      }

      node.next = current
      previous.next = node

      current.prev = node
      node.prev = previous
    }

    length++

    return true
  } else {
    return false
  }
}

與insert類似，這里不多解釋直接貼代碼

this.removeAt = function (position) {
  // 檢查是否越界
  if (position > -1 && position < length) {
    var current = head,
        previous,
        index = 0

    if (position === 0) { // 第一個(gè)元素
      head = current.next
      // 如果只有一個(gè)元素
      if (length === 1) {
        tail = null
      } else {
        head.prev = null
      }
    } else if (position === length - 1) { // 最后一個(gè)元素
      current = tail
      tail = current.prev
      tail.next = null
    } else {
      while (index++ < position) {
        previous = current
        current = current.next
      }

      previous.next = current.next
      current.next.prev = previous
    }

    length--

    return current.element
  } else {
    return null
  }
}

和單向鏈表的一樣，只不過多了tail有一些不同

this.append = function (element) {
  var node = new Node(element),
      current = tail

  if (head === null) {
    head = node
    tail = node
  } else {
    node.prev = current
    current.next = node
    tail = node
  }

  length++
}

其他的代碼都很簡(jiǎn)單，我就放上源代碼地址，大家自行查閱吧～

雙向鏈表的實(shí)現(xiàn)-源代碼

一開始寫的時(shí)候有點(diǎn)不習(xí)慣，但是實(shí)現(xiàn)了一兩個(gè)方法之后發(fā)現(xiàn)很多思路是類似的，于是舉一反三地寫出來，然后跟書上對(duì)比之后，發(fā)現(xiàn)還是有點(diǎn)差距的。

大家有興趣也動(dòng)手去實(shí)踐一下再對(duì)比源碼，可以認(rèn)識(shí)到自己有哪些地方不足。

鏈表暫時(shí)就這樣了，明天繼續(xù)攻克集合！