鏈結串列是每個資料結構課程的起點。它用「節點 + 指標」取代連續記憶體,因此插入與刪除不必搬動其他元素。本文用 JavaScript 建立一個可擴充的鏈表,並示範氣泡排序。
function Node() {
this.data = null;
this.next = null;
}
function GenericList() {
this.head = null;
this.current = null;
// 輸出所有節點
this.print = function() {
this.current = this.head;
while (this.current != null) {
alert(this.current.data);
this.current = this.current.next;
}
};
// 插入到鏈頭
this.addHead = function(t) {
var node = new Node();
node.data = t;
node.next = this.head;
this.head = node;
};
}addHead 是鏈表最關鍵的操作,三步驟順序不能錯:新節點的 next 指向舊頭 → head 指向新節點。若顛倒順序,舊鏈表就會失去入口。
function SortList() {
// 對鏈表做氣泡排序
this.BubbleSort = function() {
if (this.head == null || this.head.next == null) return;
var swapped;
do {
this.previous = null;
this.current = this.head;
swapped = false;
while (this.current.next != null) {
if (this.current.data - this.current.next.data > 0) {
// 交換相鄰兩節點
var tmp = this.current.next;
this.current.next = this.current.next.next;
tmp.next = this.current;
if (this.previous == null) {
this.head = tmp; // 交換的是頭兩個節點
} else {
this.previous.next = tmp;
}
this.previous = tmp;
swapped = true;
} else {
this.previous = this.current;
this.current = this.current.next;
}
}
} while (swapped);
};
}
SortList.prototype = new GenericList();這裡的指標操作順序值得細看。交換相鄰兩節點 p 與 q(q 在 p 後面)時:
1. 暫存 q
2. p.next = q.next(讓 p 跳過 q)
3. q.next = p(讓 q 接到 p)
4. 把 q 的前驅節點的 next 指向 q(若 p 是頭節點,則更新 head)
順序錯了就會斷鏈,這是鏈表排序最容易出錯的地方。previous 指標的存在,正是為了處理第 4 步。
(function Main() {
var sl = new SortList();
for (var i = 0; i < arguments.length; i++) {
sl.addHead(arguments[i]);
}
alert("未排序的鏈表");
sl.print();
sl.BubbleSort();
alert("已排序的鏈表 從小到大");
sl.print();
})("1", "2", "3", "4");注意這裡的資料是字串 "1"、"2"、"3",而氣泡排序用減法比較。字串相減會被隱含轉為數字,因此剛好能運作——但這是巧合而非設計。若資料是 "10" 與 "9",字串比較會出錯,減法則正確。實作時應明確轉型或改用可傳入比較函式的設計。
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// 尾端追加,維持插入順序
append(data) {
const node = new Node(data);
if (!this.head) { this.head = node; }
else {
let cur = this.head;
while (cur.next) cur = cur.next;
cur.next = node;
}
this.size++;
return this;
}
// 氣泡排序,使用比較函式而非硬編碼減法
bubbleSort(compare = (a, b) => a - b) {
if (!this.head || !this.head.next) return this;
let swapped;
do {
swapped = false;
let prev = null;
let cur = this.head;
while (cur.next) {
if (compare(cur.data, cur.next.data) > 0) {
const next = cur.next;
cur.next = next.next;
next.next = cur;
if (prev) prev.next = next; else this.head = next;
prev = next;
swapped = true;
} else {
prev = cur;
cur = cur.next;
}
}
} while (swapped);
return this;
}
toArray() {
const result = [];
for (let cur = this.head; cur; cur = cur.next) result.push(cur.data);
return result;
}
}
const list = new LinkedList();
[5, 3, 8, 1, 9, 2].forEach(n => list.append(n));
console.log(list.toArray()); // [5,3,8,1,9,2]
list.bubbleSort();
console.log(list.toArray()); // [1,2,3,5,8,9]print 用 alert 不適合除錯。改用 toArray 加 console.log,能一次看清整個結構,也不必反覆關閉彈窗。
addHead 會反轉順序。依序傳入 1、2、3、4 之後,串列實際是 4→3→2→1。若你要維持輸入順序,應該用 append(如上)或先在陣列反轉。
氣泡排序在鏈表上其實不划算。鏈表沒有隨機存取能力,氣泡排序的優勢(可提前結束)還在,但整體仍是 O(n²)。若真要排序鏈表,合併排序(merge sort)才是正解——它只需 O(n log n),且不需要額外的陣列空間,非常適合鏈表。
至於 JavaScript 的實務:除非在解題或特殊場景,日常開發幾乎用不到自己實作的鏈表,陣列與 Map 已足夠應付絕大多數需求。這個練習的價值在於理解指標操作與資料結構的底層思維。