鏈表(Linked list)是一種常見的基礎數據結構。它屬於線性表,但不同於數組那樣按順序在內存中排列,而是把數據分散存放在各個節點裡,每個節點通過指針指向下一個節點。這種結構的好處是插入和刪除不需要搬移大量元素。
下面用 JavaScript 完整實現一個單鏈表。
/**
* Node 類用來表示節點
* element 用來保存節點上的數據
* next 用來保存指向下一個節點的鏈接
*/
function Node(element) {
this.element = element;
this.next = null;
}
/**
* LList 類提供了對鏈表進行操作的方法
* 鏈表只有一個屬性,使用一個 Node 對象保存頭節點
*/
class LList {
constructor() {
this.head = new Node('head');
}
// 查找指定數據的節點
find(item) {
let currNode = this.head;
while (currNode.element !== item) {
currNode = currNode.next;
}
return currNode;
}
// 查找指定節點的前一個節點
findPre(item) {
if (item === 'head') throw new Error('now is head!');
let currNode = this.head;
while (currNode.next && currNode.next.element !== item) {
currNode = currNode.next;
}
return currNode;
}
// 在 item 之後插入新節點
insert(newElement, item) {
let newNode = new Node(newElement);
let currNode = this.find(item);
newNode.next = currNode.next;
currNode.next = newNode;
}
// 刪除指定節點
remove(item) {
let preNode = this.findPre(item);
if (preNode.next !== null) {
preNode.next = preNode.next.next;
}
}
// 遍歷顯示鏈表中的元素
display() {
let currNode = this.head;
while (currNode.next !== null) {
console.log(currNode.next.element);
currNode = currNode.next;
}
}
}
幾個設計要點值得說明。鏈表構造時會預置一個 element 為 'head' 的頭節點,它不存業務數據,作用是簡化插入刪除的邊界判斷。插入操作必須先接新節點的 next,再改原節點的 next,順序顛倒會丟失後續鏈路。刪除則需要先找到前驅節點,靠「前驅.next = 前驅.next.next」跳過目標——這也是很多鏈表題目需要引入虛擬頭結點的原因。
const list = new LList();
// LList { head: Node { element: 'head', next: null } }
list.insert('0', 'head');
list.insert('1', '0');
list.insert('2', '1');
list.insert('3', '2');
list.remove('1');
console.log(list);
// LList { head: Node { element: 'head', next: Node { element: '0', next: [Object] } } }
console.log(list.display()); // 依次輸出 0 2 3
console.log(list.findPre('1'));
// Node { element: '0', next: Node { element: '1', next: ... } }
注意上面 findPre('1') 是在 remove 之後調用的,此時鏈表中已無 element 為 '1' 的節點,循環會一直走到尾部,這是示例代碼在查找失敗時缺少終止條件的表現。
這份實現覆蓋了鏈表最核心的四個操作:find、findPre、insert、remove,再加上一個遍歷用的 display。真實場景中還需要補充幾處健壯性:查找失敗時返回 null 而不是 undefined、空鏈表判斷、以及循環鏈表的檢測。但作為理解指針操作的一份最小骨架,它已經足夠清晰——鏈表的全部奧妙,就在那幾行 next 賦值的先後順序裡。