最近在看《JavaScript 資料結構與算法》這本書,想補一下資料結構方面的底子,因為一直覺得這是我的弱項。以下把鏈結串列(Linked List)的觀念與實作做個筆記。
鏈結串列用來儲存「有序的元素集合」,但和陣列不同,它的元素在記憶體中並不連續。每個元素由兩部分組成:存放資料本身的節點,以及指向下一個元素的引用(也稱 pointer 或 link)。
它的好處是可以輕易地在任意位置新增或移除元素,並在需要時自然擴容,不必搬動其他元素。
・陣列:可以直接以索引存取任何位置的元素,時間複雜度 O(1)。
・鏈結串列:要存取某個元素,必須從表頭開始逐個走訪,直到找到目標,時間複雜度 O(n)。
這就是典型的空間與時間取捨:鏈結串列犧牲了隨機存取的效率,換來插入與刪除的靈活性。
function LinkedList() {
var Node = function (element) {
this.element = element;
this.next = null;
};
var length = 0;
var head = null;
// 尾端追加
this.append = function (element) {
var node = new Node(element);
var current;
if (head == null) {
head = node; // 串列為空,直接作為表頭
} else {
current = head;
while (current.next) { // 走到最後一項
current = current.next;
}
current.next = node;
}
length++; // 更新長度
};
// 指定位置插入
this.insert = function (position, element) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position >= 1 && position <= length) { // 越界檢查
if (position === 0) {
node.next = current; // 插入表頭
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
} else {
return false;
}
};
// 取得元素索引
this.indexOf = function (element) {
var current = head;
var index = -1;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
// 依位置移除
this.removeAt = function (position) {
if (position > -1 && position < length) {
var current = head;
var previous;
var index = 0;
if (position === 0) {
head = current.next; // 移除第一個節點
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next; // 跳過目前節點
}
length--;
return current.element;
} else {
return null;
}
};
// 依值移除
this.remove = function (element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
this.isEmpty = function () {
return length == 0;
};
this.size = function () {
return length;
};
this.toString = function () {
var current = head;
var string = "";
while (current) {
string = "," + current.element;
current = current.next;
}
return string.slice(1);
};
this.getHead = function () {
return head;
};
}
這份實作刻意用閉包把 Node、length、head 藏起來,只透過 this 上掛的方法對外開放,這是避免使用 ES6 class 之前的常見封裝手法。若換成 class 語法搭配 private 欄位,結構會更清楚。
另外提醒一下,書上的 indexOf 範例有個小瑕疵:起始 index 設為 -1 卻在比對之後才遞增,導致第一個節點永遠比對不到。實作時建議把 index 初始化為 0,或改成先比對 current 再前移指標的寫法。