鏈表(Linked List)是資料結構中的經典入門題,它能幫助我們理解「節點」與「指標」的概念。與陣列不同,鏈表的元素在記憶體中不必連續,每個節點透過 next 指向下一個節點。下面以 JavaScript 打造一個具備新增、插入、刪除、查詢、排序與序列化能力的單向鏈表。
function linkNode(_key, _value)
{
/// <summary> 鏈表類的節點類 </summary>
this.Key = _key;
this.Value = _value;
this.next = null;
}
function Link()
{
/// <summary> 創建一個鏈表類 </summary>
this.root = new linkNode(null, null); // root 永遠是個空節點
this.end = this.root;
}
每個方法都透過原型掛載到 Link 上,涵蓋了鏈表操作最常見的需求:
Link.prototype =
{
count: 0,
// 根據 key 的值來獲取 value 值
value: function (_key) {
var i = this.root;
while (Boolean(i = i.next)) {
if (i.Key == _key) return i.Value;
}
},
// 往鏈表的尾部中加入一個節點
add: function (_key, _value) {
var i = this.root;
while (Boolean(i = i.next)) {
if (i.Key == _key) return i.Value = _value;
}
var node = new linkNode(_key, _value);
if (this.count == 0) this.root.next = node;
else this.end.next = node;
this.end = node;
this.count++;
return _value;
},
// 從鏈表類的某節點之後插入新節點 node
insert: function (_key, node) {
var i = this.root;
while (Boolean(i = i.next)) {
if (i.Key == _key) {
var tmp = i.next;
i.next = node;
node.next = tmp;
break;
}
}
},
// 從某節點之前插入新節點 node
insertBefore: function (_key, node) {
var i = this.root;
while (Boolean(i = i.next)) {
if (i.next.Key == _key) {
var tmp = i.next;
i.next = node;
node.next = tmp;
break;
}
}
},
// 從鏈表類中移除一個 key
remove: function (_key) {
var i = this.root;
do {
if (i.next.Key == _key) {
if (i.next.next == null) this.end = i;
i.next = i.next.next;
this.count--;
return;
}
} while (Boolean(i = i.next))
},
// 檢查鏈表中是否存在一個 key
exists: function (_key) {
var i = this.root;
while (Boolean(i = i.next))
if (i.Key == _key) return true;
return false;
},
// 清空鏈表
removeAll: function () {
this.root = new linkNode(null, null);
this.end = this.root;
this.count = 0;
},
// 對鏈表進行排序(氣泡排序思維)
sort: function (fn) {
if (fn != null) {
var i = this.root;
while (Boolean(i = i.next)) {
var j = this.root;
while (Boolean(j = j.next)) {
if (j.next != null) {
if (fn.call(this, j)) {
var Key = j.Key;
var Value = j.Value;
j.Key = j.next.Key;
j.Value = j.next.Value;
j.next.Key = Key;
j.next.Value = Value;
}
}
}
this.end = i;
}
}
}
};
這個實作用了一個空的 root 節點作為起點(哨兵節點),使得插入與刪除時不必特別判斷頭部,邏輯更一致。另外還提供了 getJSON、getArrayJSON 等序列化方法,可把整個鏈表結構轉成 JSON 字串。若需要完整版本,可再加上這兩個方法。透過這份程式碼,能清楚看到鏈表「靠指標串起節點」的核心精神。