JS數據結構與算法_鏈表

NeverSayNever 發布于2019-08-23 14:53 / 1733人閱讀

摘要：上一篇數據結構與算法棧隊列下一篇數據結構與算法集合字典寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到上一篇博客發布以后，僅幾天的時間竟然成為了我寫博客以來點贊數最多的一篇博客。

上一篇：JS數據結構與算法_棧&隊列
下一篇：JS數據結構與算法_集合&字典

寫在前面

說明：JS數據結構與算法 系列文章的代碼和示例均可在此找到

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

一、鏈表數據結構

相較于之前學習的棧/隊列只關心棧頂/首尾的模式，鏈表更加像是數組。鏈表和數組都是用于存儲有序元素的集合，但有幾點大不相同

鏈表不同于數組，鏈表中的元素在內存中并不是連續放置的

鏈表添加或移除元素不需要移動其他元素

數組可以直接訪問任何一個位置的元素，鏈表必須從表頭開始迭代到指定位置訪問

下面是單鏈表的基本結構

長度為3的單鏈表

每個元素由一個存儲元素本身data的節點和一個指向下一個元素的引用next(也稱指針或鏈接)組成

尾節點的引用next指向為null

類比：尋寶游戲，你有一條線索，這條線索是指向尋找下一條線索的地點的指針。你順著這條鏈接去下一個地點，得到另一條指向再下一處的線索。得到列表中間的線索的唯一辦法，就是從起點(第一條線索)順著列表尋找

二、鏈表的實現

鏈表的實現不像之前介紹的棧和隊列一般依賴于數組（至少我們目前是這樣實現的），它必須自己構建類并組織邏輯實現。我們先創建一個Node類

// 節點基類
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

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

append 在鏈表尾部添加一個元素

insert 在指定位置插入元素

removeAt 在指定位置刪除元素

getNode 獲取指定位置的元素

print 打印整個鏈表

indexOf 查找鏈表中是否有某個元素，有則返回索引，沒有則返回-1

getHead 獲取鏈表頭部

getTail 獲取鏈表尾部（有些并未實現尾部）

size 返回鏈表包含的元素個數

clear 清空鏈表

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

下面我們來實現幾個重要的方法

2.1 append方法

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

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

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

代碼實現

// 在鏈表尾端添加元素
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;
}

2.2 print方法

為方便驗證，我們先實現print方法。方法雖簡單，這里卻涉及到鏈表遍歷精髓

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

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

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

2.3 getNode方法

獲取指定索引位置的節點，依次遍歷鏈表，直到指定位置返回

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

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

2.4 insert方法

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

插入尾部，相當于append

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

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

代碼實現

// 在鏈表指定位置插入元素
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 {
    // 找到原有位置節點
    const prevTargetNode = this.getNode(index - 1);
    const targetNode = prevTargetNode.next;
    // 重塑節點連接
    prevTargetNode.next = insertNode;
    insertNode.next = targetNode;
  }

  this._length += 1;
  return true;
}

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

2.5 removeAt方法

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

首部：重新定義_head

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

代碼實現

// 在鏈表指定位置移除元素
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;
    // 若移除為最后一個元素
    if (!nextNode) this._tail = prevNode;
    prevNode.next = nextNode;
  }

  this._length -= 1;
  return true;
}

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

2.6 其它方法

完整的鏈表代碼，可點此獲取

// 判斷數據是否存在于鏈表內，存在返回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;
}

三、鏈表的應用 3.1 基于鏈表實現的Stack和Queue

基于鏈表實現棧

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()
  }
}

基于鏈表實現隊列

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()
  }
}

3.2 鏈表翻轉【面試常考】

（1）迭代法

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

代碼實現

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

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

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

  return true;
}

（2）遞歸法

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

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);

3.3 鏈表逆向輸出

利用遞歸，反向輸出

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

四、雙向鏈表和循環鏈表 4.1 雙向鏈表

雙向鏈表和普通鏈表的區別在于，在鏈表中，一個節點只有鏈向下一個節點的鏈接，而在雙向鏈表中，鏈接是雙向的：一個鏈向下一個元素，另一個鏈向前一個元素，如下圖

正是因為這種變化，使得鏈表相鄰節點之間不僅只有單向關系，可以通過prev來訪問當前節點的上一節點。相應的，雙向循環鏈表的基類也有變化

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

繼承單向鏈表后，最終的雙向循環鏈表DoublyLinkedList如下【prev對應的更改為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 {
      // 找到原有位置節點
      const prevTargetNode = this.getNode(index - 1);
      const targetNode = prevTargetNode.next;
      // 重塑節點連接
      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;
      // 若移除為最后一個元素
      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;
  }
}

4.2 循環鏈表

循環鏈表可以像鏈表一樣只有單向引用，也可以像雙向鏈表一樣有雙向引用。循環鏈表和鏈 表之間唯一的區別在于，單向循環鏈表最后一個節點指向下一個節點的指針tail.next不是引用null， 而是指向第一個節點head，雙向循環鏈表的第一個節點指向上一節點的指針head.prev不是引用null，而是指向最后一個節點tail

總結

鏈表的實現較于棧和隊列的實現復雜許多，同樣的，鏈表的功能更加強大

我們可以通過鏈表實現棧和隊列，同樣也可以通過鏈表來實現棧和隊列的問題

鏈表更像是數組一樣的基礎數據結構，同時也避免了數組操作中刪除或插入元素對其他元素的影響

上一篇：JS數據結構與算法_棧&隊列
下一篇：JS數據結構與算法_集合&字典

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/101290.html

嘮叨一下js對象與哈希表那些事

摘要：的擴展知識對于哈希表來說，最重要的莫過于生成哈希串的哈希算法和處理沖突的策略了。由于鏈表的查找需要遍歷，如果我們將鏈表換成樹或者哈希表結構，那么就能大幅提高沖突元素的查找效率。最近在整理數據結構和算法相關的知識，小茄專門在github上開了個repo https://github.com/qieguo2016...，后續內容也會更新到這里，歡迎圍觀加星星！ js對象 js中的對象是基...

Nosee 2019-08-22 10:46 評論0 收藏0
探索vue源碼之緩存篇

摘要：中采用算法來實現緩存的高效管理。通過這兩個屬性，將緩存中的變量連接起來。以上圖舉例緩存這個對象中保存了三個變量。如果緩存數組為空，則返回將為傳入參數的緩存對象標識為最常使用的，即，并調整雙向鏈表，返回改變后的。 vue.js入坑也有了小半年的時間了，圈子里一直流傳著其源碼優雅、簡潔的傳說。最近的一次技術分享會，同事分享vue.js源碼的緩存部分，鄙人將其整理出來，與大家一起學習一、從...

Forest10 2019-08-20 10:23 評論0 收藏0
JS數據結構與算法_棧&隊列

摘要：下一篇數據結構與算法鏈表寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把你不知道的三部全部看完的，偶然間朋友推薦了數據結構與算法的一套入門視頻，學之。手頭上恰好有學習數據結構與算法的書籍，便轉而先把數據結構與算法學習。下一篇：JS數據結構與算法_鏈表寫在前面說明：JS數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把《你不知道的Javascript》...

AndroidTraveler 2019-08-23 14:45 評論0 收藏0
web技術分享| LRU 緩存淘汰算法

摘要：雙向鏈表用于管理緩存數據結點的順序，新增數據和緩存命中最近被訪問的數據被放置在結點，尾部的結點根據內存大小進行淘汰。了解 LRU 之前，我們應該了解一下緩存，大家都知道計算機具有緩存內存，可以臨時存儲最常用的數據，當緩存數據超過一定大小時，系統會進行回收，以便釋放出空間來緩存新的數據，但從系統中檢索數據的成本...

graf 2021-11-24 09:39 評論0 收藏0