萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 數據結構與算法(三):深度解析鏈表實現

引言:為什麼需要鏈表?

JavaScript 的陣列在引擎層面已高度優化(V8 等引擎對稠密陣列採用連續內存存儲,對稀疏陣列轉為哈希表),push/pop/shift/unshift 等操作性能極佳。然而,陣列作為順序存儲結構,在中間插入/刪除時仍需大量元素位移,時間複雜度為 O(n)。鏈表通過鏈式存儲(節點包含數據 + 指針)將插入/刪除優化至 O(1)(已定位前驅節點時),是頻繁修改數據場景的優選。

鏈表核心概念

  • 節點:數據塊 + 指向下一節點的引用(next)
  • 頭節點:鏈表入口,不存儲業務數據
  • 單鏈表:單向指向,只能從頭遍歷到尾
  • 雙向鏈表:額外保存 prev 指針,支持雙向遍歷,空間換時間
  • 循環鏈表:尾節點 next 指向頭節點,適合循環輪詢場景

鏈表邏輯結構圖

單鏈表從零實現

1. 節點構造函數

function Node(data) {
  this.data = data;
  this.next = null;
}

2. 鏈表類封裝

function LinkedList() {
  this.head = new Node('head'); // 哨兵頭節點
  this.length = 0;
}

// 尋找指定數據的節點
LinkedList.prototype.find = function(item) {
  var currNode = this.head;
  while (currNode && currNode.data !== item) {
    currNode = currNode.next;
  }
  return currNode;
};

// 尋找目標節點的前驅節點(用於刪除)
LinkedList.prototype.findPrevious = function(item) {
  var currNode = this.head;
  while (currNode.next && currNode.next.data !== item) {
    currNode = currNode.next;
  }
  return currNode;
};

// 插入:在 item 節點後插入新節點
LinkedList.prototype.insert = function(newElement, item) {
  var newNode = new Node(newElement);
  var current = this.find(item);
  if (current) {
    newNode.next = current.next;
    current.next = newNode;
    this.length++;
    return true;
  }
  return false;
};

// 刪除
LinkedList.prototype.remove = function(item) {
  var prevNode = this.findPrevious(item);
  if (prevNode.next) {
    prevNode.next = prevNode.next.next;
    this.length--;
    return true;
  }
  return false;
};

// 顯示所有節點
LinkedList.prototype.display = function() {
  var currNode = this.head.next;
  var arr = [];
  while (currNode) {
    arr.push(currNode.data);
    currNode = currNode.next;
  }
  console.log(arr.join(' -> '));
};

3. 使用演示

var list = new LinkedList();
list.insert('arron1', 'head'); // head -> arron1
list.insert('arron2', 'arron1'); // head -> arron1 -> arron2
list.insert('arron3', 'arron2'); // head -> arron1 -> arron2 -> arron3
list.display(); // arron1 -> arron2 -> arron3

list.remove('arron2');
list.display(); // arron1 -> arron3

進階:雙向鏈表實現

雙向鏈表新增 prev 指針,使反向遍歷、尾部插入、任意節點刪除均為 O(1)。

function DoublyNode(data) {
  this.data = data;
  this.next = null;
  this.prev = null;
}

function DoublyLinkedList() {
  this.head = new DoublyNode('head');
  this.tail = this.head; // 維護尾指針,尾部插入 O(1)
  this.length = 0;
}

DoublyLinkedList.prototype.append = function(data) {
  var newNode = new DoublyNode(data);
  this.tail.next = newNode;
  newNode.prev = this.tail;
  this.tail = newNode;
  this.length++;
};

DoublyLinkedList.prototype.remove = function(data) {
  var current = this.head.next;
  while (current) {
    if (current.data === data) {
      current.prev.next = current.next;
      if (current.next) {
        current.next.prev = current.prev;
      } else {
        this.tail = current.prev; // 刪除尾節點時更新尾指針
      }
      this.length--;
      return true;
    }
    current = current.next;
  }
  return false;
};

鏈表在 JS 中的實際應用場景

  1. jQuery Deferred / Promise 鏈式調用:then 返回新 Promise,形成單鏈表結構
  2. 中間件鏈:Express/Koa 中間件通過 next() 傳遞控制權,本質是鏈表遍歷
  3. LRU 緩存淘汰算法:雙向鏈表 + HashMap 實現 O(1) 讀寫與淘汰
  4. 虛擬 DOM Diff 算法:子節點列表對比時的移動操作可借鑑鏈表思想

性能對比與選型建議

操作陣列單鏈表雙向鏈表
隨機訪問O(1)O(n)O(n)
頭部插入/刪除O(n)O(1)O(1)
尾部插入/刪除O(1)*O(n)O(1)
中間插入/刪除O(n)O(1)**O(1)**
內存開銷低中(1 指針)高(2 指針)

* 陣列尾部操作摊銷 O(1),但擴容時需複製
** 前提是已定位到目標節點或其前驅

總結

鏈表雖在 JS 中不如陣列常用,但理解其指針操控與內存非連續存儲的本質,對掌握底層數據結構、優化高頻寫入場景、閱讀框架源碼(如 React Fiber 鏈表樹、RxJS 觀察者鏈)至關重要。實際開發中,優先考慮陣列;當出現「頻繁中間插刪、不需要隨機訪問」的明確場景時,再引入鏈表或雙向鏈表。

copyright © 萬盛學電腦網 all rights reserved