JavaScript 的陣列在引擎層面已高度優化(V8 等引擎對稠密陣列採用連續內存存儲,對稀疏陣列轉為哈希表),push/pop/shift/unshift 等操作性能極佳。然而,陣列作為順序存儲結構,在中間插入/刪除時仍需大量元素位移,時間複雜度為 O(n)。鏈表通過鏈式存儲(節點包含數據 + 指針)將插入/刪除優化至 O(1)(已定位前驅節點時),是頻繁修改數據場景的優選。
next)prev 指針,支持雙向遍歷,空間換時間next 指向頭節點,適合循環輪詢場景
function Node(data) {
this.data = data;
this.next = null;
}
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(' -> '));
};
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;
};
then 返回新 Promise,形成單鏈表結構next() 傳遞控制權,本質是鏈表遍歷| 操作 | 陣列 | 單鏈表 | 雙向鏈表 |
|---|---|---|---|
| 隨機訪問 | 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 觀察者鏈)至關重要。實際開發中,優先考慮陣列;當出現「頻繁中間插刪、不需要隨機訪問」的明確場景時,再引入鏈表或雙向鏈表。