數據結構之LinkedList | 讓我們一塊來學習數據結構
- 2021 年 4 月 29 日
- 筆記
- javascript, linkedlist, 數據結構, 鏈表
highlight: monokai
theme: vue-pro
上一篇文章中使用列表（List）對數據排序，當時底層儲存數據的數據結構是數組。本文將討論另外一種列表：鏈表。我們會解釋為什麼有時鏈表優於數組，還會實現一個基於對象的鏈表。下面讓我們一起來學習LinkedList。
數組的缺點
在很多編程語言中，數組的長度是固定的，所以當數組已被數據填滿時，再要加入新的元素就會非常困難。在數組中，添加和刪除元素也很麻煩，因為需要將數組中的其他元素向前或向後平移，以反映數組剛剛進行了添加或刪除操作。然而，JavaScript 的數組並不存在上述問題，因為使用 split() 方法不需要再訪問數組中的其他元素了。
avaScript 中數組的主要問題是，它們被實現成了對象，與其他語言（比如 C++ 和 Java）的數組相比，效率很低。
定義鏈表
鏈表是由一組節點組成的集合。每個節點都使用一個對象的引用指向它的後繼。指向另一個節點的引用叫做鏈。下圖展示了一個鏈表。
數組元素靠它們的位置進行引用，鏈表元素則是靠相互之間的關係進行引用。在上圖中，我們說 李四 跟在 張三 後面，而不說 李四 是鏈表中的第二個元素。遍歷鏈表，就是跟着鏈接，從鏈表的首元素一直走到尾元素（但這不包含鏈表的頭節點，頭節點常常用來作為鏈表的接入點）。圖中另外一個值得注意的地方是，鏈表的尾元素指向一個 null 節點。
然而要標識出鏈表的起始節點卻有點麻煩，許多鏈表的實現都在鏈表最前面有一個特殊節點，叫做頭節點。經過改造之後，上圖中的鏈表成了下面的樣子。
設計一個基於對象的鏈表
Node類
Node 類包含兩個屬性：element 用來保存節點上的數據，next 用來保存指向下一個節點的
鏈接。我們使用一個class來創建節點：
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
LinkedList類
LList 類提供了對鏈表進行操作的方法。該類的功能包括插入刪除節點、在列表中查找給
定的值。該類也有一個構造函數，鏈表只有一個屬性，那就是使用一個 Node 對象來保存該
鏈表的頭節點。
該類如下所示
class LinkedList {
constructor() {
this.head = new Node("head");
}
find() { }
insert() { }
findPrevious() { }
remove() { }
display() { }
}
head節點的next屬性被初始化為null，當有新元素插入時，next會指向新的元素，所以在這裡我們沒有修改next的值。
插入新節點
該方法向鏈表中插入一個節點。向鏈表中插入新節點時，需要明確指出要在哪個節點前面或後面插入。首先介紹如何在一個已知節點後面插入元素。
在一個已知節點後面插入元素時，先要找到「後面」的節點。為此，創建一個輔助方法find()，該方法遍歷鏈表，查找給定數據。如果找到數據，該方法就返回保存該數據的節點。find() 方法的實現代碼如下所示：
find(element) {
let current = this.head;
while (current.element !== element) {
current = current.next;
}
return current;
}
find() 方法演示了如何在鏈表上進行移動。首先，創建一個新節點，並將鏈表的頭節點賦給這個新創建的節點。然後在鏈表上進行循環，如果當前節點的 element 屬性和我們要找的信息不符，就從當前節點移動到下一個節點。如果查找成功，該方法返回包含該數據的節點；否則，返回 null。
一旦找到「後面」的節點，就可以將新節點插入鏈表了。首先，將新節點的 next 屬性設置為「後面」節點的 next 屬性對應的值。然後設置「後面」節點的 next 屬性指向新節點。
insert() 方法的定義如下：
insert(element) {
const newNode = new Node(element);
const curNode = this.find(element);
newNode.next = cur.next;
curNode.next = newNode;
}
移除節點
在之前我們已經可以實現插入節點了，有添加自然就有移除。現在讓我們來實現remove()方法。
從鏈表中刪除節點時，需要先找到待刪除節點前面的節點。找到這個節點後，修改它的
next 屬性，使其不再指向待刪除節點，而是指向待刪除節點的下一個節點。我們可以定義
一個方法 findPrevious()，來做這件事。該方法遍歷鏈表中的元素，檢查每一個節點的下
一個節點中是否存儲着待刪除數據。如果找到，返回該節點（即「前一個」節點），這樣
就可以修改它的 next 屬性了。findPrevious() 方法的定義如下：
findPrevious(item) {
let curNode = this.head;
while (curNode.next !== null && curNode.next.element !== item) {
curNode = curNode.next;
}
return curNode;
}
現在就可以開始寫 remove() 方法了：
remove(item) {
const prevNode = this.findPrevious(item);
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next;
}
}
查看鏈表內的元素
現在已經可以開始測試我們的鏈表實現了。然而在測試之前，先來定義一個 display() 方法，該方法用來顯示鏈表中的元素：
display() {
let target = [];
let curNode = this.head;
while (curNode.next !== null) {
target.push(curNode.next.element);
curNode = curNode.next;
}
return target.join();
}
測試代碼
雙向鏈表
儘管從鏈表的頭節點遍歷到尾節點很簡單，但反過來，從後向前遍歷則沒那麼簡單。通過給 Node 對象增加一個屬性，該屬性存儲指向前驅節點的鏈接，這樣就容易多了。此時向鏈表插入一個節點需要更多的工作，我們需要指出該節點正確的前驅和後繼。但是在從鏈表中刪除節點時，效率提高了，不需要再查找待刪除節點的前驅節點了。圖 6-5 演示了雙向鏈表的工作原理。
修改Node類
首當其衝的是要為 Node 類增加一個 previous 屬性：
class Node {
constructor(element) {
this.element = element;
this.previous = null;
this.next = null;
}
}
修改insert()方法
雙向鏈表的 insert() 方法和單向鏈表的類似，但是需要設置新節點的 previous 屬性，使其指向該節點的前驅。該方法的定義如下：
insert(element, item) {
const newNode = new Node(element);
const curNode = this.find(item);
newNode.next = curNode.next;
newNode.previous = curNode; // 令新節點的previous指向當前節點
curNode.next = newNode;
}
雙向鏈表的 remove() 方法比單向鏈表的效率更高，因為不需要再查找前驅節點了。首先需要在鏈表中找出存儲待刪除數據的節點，然後設置該節點前驅的 next 屬性，使其指向待刪除節點的後繼；設置該節點後繼的 previous 屬性，使其指向待刪除節點的前驅。圖 6-6 直觀地展示了該過程。
新的remove() 方法的定義
remove(item) {
const curNode = this.find(item);
if (curNode.next !== null) {
curNode.previous.next = curNode.next;
curNode.next.previous = curNode.previous;
curNode.previous = null;
curNode.next = null;
}
}
反向顯示鏈表中的元素
為了完成以反序顯示鏈表中元素這類任務，需要給雙向鏈表增加一個工具方法，用來查找最後的節點。findLast() 方法找出了鏈表中的最後一個節點，同時免除了從前往後遍歷鏈表之苦：
findLast() {
let curNode = this.head;
while (curNode.next !== null) {
curNode = curNode.next;
}
return curNode;
}
有了這個工具方法，就可以寫一個方法，反序顯示雙向鏈表中的元素。dispReverse() 方法如下所示：
displayReverse() {
let target = [];
let currNode = this.findLast();
while (currNode.previous !== null) {
target.push(currNode.element);
currNode = currNode.previous;
}
return target.join();
}
完整的雙向鏈表實現及測試代碼
class Node {
constructor(element) {
this.element = element;
this.previous = null;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = new Node("head");
}
find(item) {
let current = this.head;
while (current.element !== item) {
current = current.next;
}
return current;
}
insert(element, item) {
const newNode = new Node(element);
const curNode = this.find(item);
newNode.next = curNode.next;
newNode.previous = curNode;
curNode.next = newNode;
}
findLast() {
let curNode = this.head;
while (curNode.next !== null) {
curNode = curNode.next;
}
return curNode;
}
remove(item) {
const curNode = this.find(item);
if (curNode.next !== null) {
curNode.previous.next = curNode.next;
curNode.next.previous = curNode.previous;
curNode.previous = null;
curNode.next = null;
}
}
display() {
let target = [];
let curNode = this.head;
while (curNode.next !== null) {
target.push(curNode.next.element);
curNode = curNode.next;
}
return target.join();
}
displayReverse() {
let target = [];
let currNode = this.findLast();
while (currNode.previous !== null) {
target.push(currNode.element);
currNode = currNode.previous;
}
return target.join();
}
}
// test code
const linkedList = new LinkedList();
linkedList.insert("張三", "head");
console.log(linkedList.display()); // 張三
linkedList.insert("李四", "張三");
console.log(linkedList.display()); // 張三,李四
linkedList.insert("王五", "李四");
console.log(linkedList.display()); // 張三,李四,王五
linkedList.remove("李四");
console.log(linkedList.display()); // 張三,王五
console.log(linkedList.displayReverse()); // 王五,張三
循環鏈表
循環鏈表和單向鏈表相似，節點類型都是一樣的。唯一的區別是，在創建循環鏈表時，讓其頭節點的 next 屬性指向它本身，即：
head.next = head
這種行為會傳導至鏈表中的每個節點，使得每個節點的 next 屬性都指向鏈表的頭節點。換句話說，鏈表的尾節點指向頭節點，形成了一個循環鏈表，如圖 6-7 所示。
創建循環鏈表，只需要修改 LinkedList 類的構造方法(constructor)：
class LinkedList {
constructor() {
this.head = new Node("head");
this.head.next = this.head;
}
find() { }
insert() { }
findPrevious() { }
remove() { }
display() { }
}
只需要修改一處，就將單向鏈表變成了循環鏈表。但是其他一些方法需要修改才能工作正常。比如，display() 就需要修改，原來的方式在循環鏈表裡會陷入死循環。while 循環的循環條件需要修改，需要檢查head節點，當循環到head節點時退出循環。
循環鏈表的display()方法如下：
display() {
let target = [];
let curNode = this.head;
while (curNode.next !== null && curNode.next.element !== "head") {
target.push(curNode.next.element);
curNode = curNode.next;
}
return target.join();
}
完整的循環鏈表實現及測試代碼
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = new Node("head");
this.head.next = this.head;
}
find(item) {
let current = this.head;
while (current.element !== item) {
current = current.next;
}
return current;
}
insert(element, item) {
const newNode = new Node(element);
const curNode = this.find(item);
newNode.next = curNode.next;
curNode.next = newNode;
}
findPrevious(item) {
let curNode = this.head;
while (curNode.next !== null && curNode.next.element !== item) {
curNode = curNode.next;
}
return curNode;
}
remove(item) {
const prevNode = this.findPrevious(item);
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next;
}
}
display() {
let target = [];
let curNode = this.head;
while (curNode.next !== null && curNode.next.element !== "head") {
target.push(curNode.next.element);
curNode = curNode.next;
}
return target.join();
}
}
// test code
const linkedList = new LinkedList();
linkedList.insert("張三", "head");
console.log(linkedList.display()); // 張三
linkedList.insert("李四", "張三");
console.log(linkedList.display()); // 張三,李四
linkedList.insert("王五", "李四");
console.log(linkedList.display()); // 張三,李四,王五
linkedList.remove("李四");
console.log(linkedList.display()); // 張三,王五
參考資料
- 數據結構與算法JavaScript描述
- 學習JavaScript數據結構與算法 第3版
如果覺得對您有幫助,動動小手點個贊；您的點贊就是對我最大的認可。
