摘要：上一篇數(shù)據(jù)結(jié)構(gòu)與算法棧隊(duì)列下一篇數(shù)據(jù)結(jié)構(gòu)與算法集合字典寫在前面說(shuō)明數(shù)據(jù)結(jié)構(gòu)與算法系列文章的代碼和示例均可在此找到上一篇博客發(fā)布以后，僅幾天的時(shí)間竟然成為了我寫博客以來(lái)點(diǎn)贊數(shù)最多的一篇博客。

上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_棧&隊(duì)列
下一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典

說(shuō)明：JS數(shù)據(jù)結(jié)構(gòu)與算法 系列文章的代碼和示例均可在此找到

上一篇博客發(fā)布以后，僅幾天的時(shí)間竟然成為了我寫博客以來(lái)點(diǎn)贊數(shù)最多的一篇博客。歡喜之余，不由得思考背后的原因，前端er離數(shù)據(jù)結(jié)構(gòu)與算法太遙遠(yuǎn)了，論壇里也少有人去專門為數(shù)據(jù)結(jié)構(gòu)與算法撰文，才使得這看似平平的文章收獲如此。不過(guò)，這樣也更加堅(jiān)定了我繼續(xù)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的決心（雖然只是入門級(jí)的）

相較于之前學(xué)習(xí)的 棧/隊(duì)列 只關(guān)心 棧頂/首尾 的模式，鏈表更加像是數(shù)組。鏈表和數(shù)組都是用于存儲(chǔ)有序元素的集合，但有幾點(diǎn)大不相同

鏈表不同于數(shù)組，鏈表中的元素在內(nèi)存中并不是連續(xù)放置的

鏈表添加或移除元素不需要移動(dòng)其他元素

數(shù)組可以直接訪問(wèn)任何一個(gè)位置的元素，鏈表必須從表頭開(kāi)始迭代到指定位置訪問(wèn)

下面是單鏈表的基本結(jié)構(gòu)

長(zhǎng)度為3的單鏈表

每個(gè)元素由一個(gè)存儲(chǔ)元素本身data的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用next(也稱指針或鏈接)組成

尾節(jié)點(diǎn)的引用next指向?yàn)?b>null

類比：尋寶游戲，你有一條線索，這條線索是指向?qū)ふ蚁乱粭l線索的地點(diǎn)的指針。你順著這條鏈接去下一個(gè)地點(diǎn)，得到另一條指向再下一處的線索。得到列表中間的線索的唯一辦法，就是從起點(diǎn)(第一條線索)順著列表尋找

鏈表的實(shí)現(xiàn)不像之前介紹的棧和隊(duì)列一般依賴于數(shù)組（至少我們目前是這樣實(shí)現(xiàn)的），它必須自己構(gòu)建類并組織邏輯實(shí)現(xiàn)。我們先創(chuàng)建一個(gè)Node類

// 節(jié)點(diǎn)基類
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

一般單鏈表有以下幾種方法：

append 在鏈表尾部添加一個(gè)元素

insert 在指定位置插入元素

removeAt 在指定位置刪除元素

getNode 獲取指定位置的元素

print 打印整個(gè)鏈表

indexOf 查找鏈表中是否有某個(gè)元素，有則返回索引，沒(méi)有則返回-1

getHead 獲取鏈表頭部

getTail 獲取鏈表尾部（有些并未實(shí)現(xiàn)尾部）

size 返回鏈表包含的元素個(gè)數(shù)

clear 清空鏈表

// 初始化鏈表
class LinkedList {
  constructor() {
    this._head = null;
    this._tail = null;
    this._length = 0;
  }
  // 方法...
}

下面我們來(lái)實(shí)現(xiàn)幾個(gè)重要的方法

在鏈表尾部添加一個(gè)新的元素可分為兩種情況：

原鏈表中無(wú)元素，添加元素后，head和tail均指向新元素

原鏈表中有元素，更新tail元素（如下）

代碼實(shí)現(xiàn)

// 在鏈表尾端添加元素
append(data) {
  const newNode = new Node(data);
  if (this._length === 0) {
    this._head = newNode;
    this._tail = newNode;
  } else {
    this._tail.next = newNode;
    this._tail = newNode;
  }

  this._length += 1;
  return true;
}

為方便驗(yàn)證，我們先實(shí)現(xiàn)print方法。方法雖簡(jiǎn)單，這里卻涉及到鏈表遍歷精髓

// 打印鏈表
print() {
  let ret = [];
  // 遍歷需從鏈表頭部開(kāi)始
  let currNode = this._head;
  // 單鏈表最終指向null，作為結(jié)束標(biāo)志
  while (currNode) {
    ret.push(currNode.data);
    // 輪詢至下一節(jié)點(diǎn)
    currNode = currNode.next;
  }
  console.log(ret.join(" --> "));
}

// 驗(yàn)證
const link = new LinkedList();
link.append(1);
link.append(2);
link.append(3);

link.print(); // 1 --> 2 --> 3

獲取指定索引位置的節(jié)點(diǎn)，依次遍歷鏈表，直到指定位置返回

// 獲取指定位置元素
getNode(index) {
  let currNode = this._head;
  let currIndex = 0;
  while (currIndex < index) {
    currIndex += 1;
    currNode = currNode.next;
  }
  return currNode;
}

// 驗(yàn)證【銜接上面的鏈表實(shí)例】
console.log(link.getNode(0));
// Node { data: 1, next: Node { data: 2, next: Node { data: 3, next: null } } }
console.log(link.getNode(3)); // null

插入元素，需要考慮三種情況

插入尾部，相當(dāng)于append

插入首部，替代_head并指向原有頭部元素

中間，需要斷開(kāi)原有鏈接并重新組合（如下）

代碼實(shí)現(xiàn)

// 在鏈表指定位置插入元素
insert(index, data) {
  // 不滿足條件的索引值
  if (index < 0 || index > this._length) return false;
  // 插入尾部
  if (index === this._length) return this.append(data);

  const insertNode = new Node(data);
  if (index === 0) {
    // 插入首部
    insertNode.next = this._head;
    this._head = insertNode;
  } else {
    // 找到原有位置節(jié)點(diǎn)
    const prevTargetNode = this.getNode(index - 1);
    const targetNode = prevTargetNode.next;
    // 重塑節(jié)點(diǎn)連接
    prevTargetNode.next = insertNode;
    insertNode.next = targetNode;
  }

  this._length += 1;
  return true;
}

// 驗(yàn)證
link.insert(0, 0);
link.insert(4, 4);
link.insert(5, 5);
link.print(); // 0 --> 1 --> 2 --> 3 --> 4 --> 5

在指定位置刪除元素同添加元素類似

首部：重新定義_head

其他：找到目標(biāo)位置的前后元素，重塑連接，如果目標(biāo)位置為尾部，則重新定義_tail

代碼實(shí)現(xiàn)

// 在鏈表指定位置移除元素
removeAt(index) {
  if (index < 0 || index >= this._length) return false;

  if (index === 0) {
    this._head = this._head.next;
  } else {
    const prevNode = this.getNode(index - 1);
    const delNode = prevNode.next;
    const nextNode = delNode.next;
    // 若移除為最后一個(gè)元素
    if (!nextNode) this._tail = prevNode;
    prevNode.next = nextNode;
  }

  this._length -= 1;
  return true;
}

// 驗(yàn)證
link.removeAt(3);
link.print(); // 0 --> 1 --> 2 --> 4 --> 5

完整的鏈表代碼，可點(diǎn)此獲取

// 判斷數(shù)據(jù)是否存在于鏈表內(nèi)，存在返回index，否則返回-1
indexOf(data) {
  let currNode = this._head;
  let index = 0;
  while (currNode) {
    if (currNode.data === data) return index;
    index += 1;
    currNode = currNode.next;
  }

  return -1;
}

getHead() {
  return this._head;
}

getTail() {
  return this._tail;
}

size() {
  return this._length;
}

isEmpty() {
  return !this._length;
}

clear() {
  this._head = null;
  this._tail = null;
  this._length = 0;
}

基于鏈表實(shí)現(xiàn)棧

class Stack {
  constructor() {
    this._link = new LinkedList();
  }
  push(item) {
    this._link.append(item);
  }
  pop() {
    const tailIndex = this._link - 1;
    return this._link.removeAt(tailIndex);
  }
  peek() {
    if (this._link.size() === 0) return undefined;
    return this._link.getTail().data;
  }
  size() {
    return this._link.size();
  }
  isEmpty() {
    return this._link.isEmpty();
  }
  clear() {
    this._link.clear()
  }
}

基于鏈表實(shí)現(xiàn)隊(duì)列

class Queue {
  constructor() {
    this._link = new LinkedList();
  }
  enqueue(item) {
    this._link.append(item);
  }
  dequeue() {
    return this._link.removeAt(0);
  }
  head() {
    if (this._link.size() === 0) return undefined;
    return this._link.getHead().data;
  }
  tail() {
    if (this._link.size() === 0) return undefined;
    return this._link.getTail().data;
  }
  size() {
    return this._link.size();
  }
  isEmpty() {
    return this._link.isEmpty();
  }
  clear() {
    this._link.clear()
  }
}

（1）迭代法

迭代法的核心就是currNode.next = prevNode，然后從頭部一次向后輪詢

代碼實(shí)現(xiàn)

reverse() {
  if (!this._head) return false;

  let prevNode = null;
  let currNode = this._head;
  while (currNode) {
    // 記錄下一節(jié)點(diǎn)并重塑連接
    const nextNode = currNode.next;
    currNode.next = prevNode;
    // 輪詢至下一節(jié)點(diǎn)
    prevNode = currNode;
    currNode = nextNode;
  }

  // 交換首尾
  let temp = this._tail;
  this._tail = this._head;
  this._head = temp;

  return true;
}

（2）遞歸法

遞歸的本質(zhì)就是執(zhí)行到當(dāng)前位置時(shí)，自己并不去解決，而是等下一階段執(zhí)行。直到遞歸終止條件，然后再依次向上執(zhí)行

function _reverseByRecusive(node) {
  if (!node) return null;
  if (!node.next) return node; // 遞歸終止條件

  var reversedHead = _reverseByRecusive(node.next);
  node.next.next = node;
  node.next = null;
  
  return reversedHead;
};

_reverseByRecusive(this._head);

利用遞歸，反向輸出

function _reversePrint(node){
  if(!node) return;// 遞歸終止條件
  _reversePrint(node.next);
  console.log(node.data);
};

雙向鏈表和普通鏈表的區(qū)別在于，在鏈表中，一個(gè)節(jié)點(diǎn)只有鏈向下一個(gè)節(jié)點(diǎn)的鏈接，而在雙向鏈表中，鏈接是雙向的：一個(gè)鏈向下一個(gè)元素，另一個(gè)鏈向前一個(gè)元素，如下圖

正是因?yàn)檫@種變化，使得鏈表相鄰節(jié)點(diǎn)之間不僅只有單向關(guān)系，可以通過(guò)prev來(lái)訪問(wèn)當(dāng)前節(jié)點(diǎn)的上一節(jié)點(diǎn)。相應(yīng)的，雙向循環(huán)鏈表的基類也有變化

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

繼承單向鏈表后，最終的雙向循環(huán)鏈表DoublyLinkedList如下【prev對(duì)應(yīng)的更改為NEW】

class DoublyLinkedList extends LinkedList {
  constructor() {
    super();
  }

  append(data) {
    const newNode = new DoublyNode(data);

    if (this._length === 0) {
      this._head = newNode;
      this._tail = newNode;
    } else {
      newNode.prev = this._tail; // NEW
      this._tail.next = newNode;
      this._tail = newNode;
    }

    this._length += 1;
    return true;
  }

  insert(index, data) {
    if (index < 0 || index > this._length) return false;
    if (index === this._length) return this.append(data);

    const insertNode = new DoublyNode(data);
    if (index === 0) {
      insertNode.prev = null; // NEW
      this._head.prev = insertNode; // NEW
      insertNode.next = this._head;
      this._head = insertNode;
    } else {
      // 找到原有位置節(jié)點(diǎn)
      const prevTargetNode = this.getNode(index - 1);
      const targetNode = prevTargetNode.next;
      // 重塑節(jié)點(diǎn)連接
      prevTargetNode.next = insertNode;
      insertNode.next = targetNode;
      insertNode.prev = prevTargetNode; // NEW
      targetNode.prev = insertNode; // NEW
    }

    this._length += 1;
    return true;
  }

  removeAt(index) {
    if (index < 0 || index > this._length) return false;

    let delNode;

    if (index === 0) {
      delNode = this._head;
      this._head = this._head.next;
      this._head.prev = null; // NEW
    } else {
      const prevNode = this.getNode(index - 1);
      delNode = prevNode.next;
      const nextNode = delNode.next;
      // 若移除為最后一個(gè)元素
      if (!nextNode) {
        this._tail = prevNode;
        this._tail.next = null; // NEW
      } else {
        prevNode.next = nextNode; // NEW
        nextNode.prev = prevNode; // NEW
      }
    }

    this._length -= 1;
    return delNode.data;
  }
}

循環(huán)鏈表可以像鏈表一樣只有單向引用，也可以像雙向鏈表一樣有雙向引用。循環(huán)鏈表和鏈 表之間唯一的區(qū)別在于，單向循環(huán)鏈表最后一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)的指針tail.next不是引用null， 而是指向第一個(gè)節(jié)點(diǎn)head，雙向循環(huán)鏈表的第一個(gè)節(jié)點(diǎn)指向上一節(jié)點(diǎn)的指針head.prev不是引用null，而是指向最后一個(gè)節(jié)點(diǎn)tail

鏈表的實(shí)現(xiàn)較于棧和隊(duì)列的實(shí)現(xiàn)復(fù)雜許多，同樣的，鏈表的功能更加強(qiáng)大

我們可以通過(guò)鏈表實(shí)現(xiàn)棧和隊(duì)列，同樣也可以通過(guò)鏈表來(lái)實(shí)現(xiàn)棧和隊(duì)列的問(wèn)題

鏈表更像是數(shù)組一樣的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，同時(shí)也避免了數(shù)組操作中刪除或插入元素對(duì)其他元素的影響

上一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_棧&隊(duì)列
下一篇：JS數(shù)據(jù)結(jié)構(gòu)與算法_集合&字典