鏈表是基礎數據結構,JS 中通過對象引用模擬指針實現。本文展示單向鏈表完整實現:節點類、鏈表類、冒泡排序、繼承擴展。
// 1. 節點類
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// 2. 基礎鏈表類
class LinkedList {
constructor() {
this.head = null;
this.current = null;
}
// 头插法添加
addHead(data) {
const node = new Node(data);
node.next = this.head;
this.head = node;
}
// 尾插法添加
append(data) {
const node = new Node(data);
if (!this.head) {
this.head = node;
return;
}
let cur = this.head;
while (cur.next) cur = cur.next;
cur.next = node;
}
// 打印所有節點
print() {
let cur = this.head;
while (cur) {
console.log(cur.data);
cur = cur.next;
}
}
// 查找節點
find(data) {
let cur = this.head;
while (cur) {
if (cur.data === data) return cur;
cur = cur.next;
}
return null;
}
// 刪除節點
remove(data) {
if (!this.head) return false;
if (this.head.data === data) {
this.head = this.head.next;
return true;
}
let cur = this.head;
while (cur.next) {
if (cur.next.data === data) {
cur.next = cur.next.next;
return true;
}
cur = cur.next;
}
return false;
}
// 獲取長度
get size() {
let count = 0, cur = this.head;
while (cur) { count++; cur = cur.next; }
return count;
}
}
// 3. 可排序鏈表(繼承 + 冒泡排序)
class SortableList extends LinkedList {
bubbleSort() {
if (!this.head || !this.head.next) return;
let swapped;
do {
swapped = false;
let prev = null;
let cur = this.head;
while (cur.next) {
if (cur.data > cur.next.data) {
// 交換節點
const next = cur.next;
cur.next = next.next;
next.next = cur;
if (prev === null) {
this.head = next;
} else {
prev.next = next;
}
prev = next;
swapped = true;
} else {
prev = cur;
cur = cur.next;
}
}
} while (swapped);
}
}
// 4. 測試
const list = new SortableList();
[4, 2, 5, 1, 3].forEach(v => list.addHead(v)); // 头插逆序
console.log('排序前:'); list.print(); // 3,1,5,2,4
list.bubbleSort();
console.log('排序後:'); list.print(); // 1,2,3,4,5
tail 指針優化為 O(1)。extends 實現代碼復用,SortableList 繼承所有基礎操作。prev 指針,支持雙向遍歷、O(1) 刪除已知節點。JS 實現鏈表展示了引用機制模擬指針的能力。理解節點操作、指針交換、遞歸/迭代遍歷,是掌握數據結構與算法的關鍵一步。實際工程中數組性能通常更優(緩存友好),但鏈表在頻繁頭部插刪、不可變數據結構、函數式編程中仍有優勢。