本篇主要有三部分

• 什么是鏈表
• 鏈表的實現
• 鏈表的變種

源碼地址：github.com/yhtx1997/Sm…

另外，今天2019年2月18日上午發現 2048-vue 版，代碼版本不對，且最新版本遺失，無奈只得重新修復了下
2048-vue地址： github.com/yhtx1997/Sm…

什么是鏈表

鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個 元素由一個存儲元素本身的節點和一個指向下一個元素的引用（也稱指針或鏈接）組成。
相對于傳統的數組，鏈表的一個好處在于，添加或移除元素的時候不需要移動其他元素。然 而，鏈表需要使用指針，因此實現鏈表時需要額外注意。數組的另一個細節是可以直接訪問任何 位置的任何元素，而要想訪問鏈表中間的一個元素，需要從起點（表頭）開始迭代列表直到找到 所需的元素。
如下圖：

注：其中 00 06 10 12 18 為假定在內存中的地址

我將已經做好的鏈表存入數據，然后在控制臺打印出來是這樣的：

它看起來就像是這樣的，一層套一層

其實應該是下面這樣，類似于栓狗的鐵鏈

鏈表的實現

鏈表功能

• 添加元素
• 獲取指定位置元素
• 在指定位置插入元素
• 移除指定位置的元素
• 返回指定元素的位置
• 移除指定元素
• 是否為空
• 長度
• 獲取表頭
• 清空鏈表
• 轉換為字符串輸出

// 鏈表元素 class Node {constructor(element) {this.element = element; // 元素this.next = undefined; // 指向下一個元素} } class LinkedList {// 構造函數聲明一些全局變量constructor(){this.count = 0; // 長度this.head = undefined; // 第一個元素}// 添加元素push(element) {}// 獲取指定位置元素getElementAt(index) {}// 在指定位置插入元素insert(element, index) {}// 移除指定位置的元素removeAt(index) {}// 返回指定元素的位置indexOf(element) {}// 移除指定元素remove(element) {}// 是否為空isEmpty() {}// 長度size() {}// 獲取表頭getHead() {}// 清空鏈表clear() {}// 轉換為字符串輸出toString() {} } 復制代碼

代碼實現

class LinkedList {// 構造函數聲明一些全局變量constructor(){this.count = 0; // 長度this.head = undefined; // 第一個元素}// 添加元素push(element) {const node = new Node(element);if (this.head === undefined) {this.head = node;} else {let current = this.head;while (current.next !== undefined) {current = current.next;}current.next = node;}this.count++;}// 獲取指定位置元素getElementAt(index) {// 判斷不是空鏈表if (this.isEmpty() || index > this.count || index < 0) { // 非空才能繼續處理// 判斷不大于最大長度，不小于最小長度（0）return undefined;}// 循環找到元素let current = this.head;for (let i = 0; i < index; i++){current = current.next;}return current;// 返回找到的元素}// 在指定位置插入元素insert(element, index) {// 創建一個元素let current = new Node(element);// 首先確定是不是在首位置插入if (index === 0){current.next = this.head;this.head = current;} else {// 找到指定位置前一個元素let previous = this.getElementAt(index - 1);// 將前一個元素的 next 賦值給插入元素的 nextcurrent.next = previous.next;// 將插入元素的 node 賦值給前一個元素的 nextprevious.next = current;}this.count++;}// 移除指定位置的元素removeAt(index) {let current = this.head;if (index === 0){this.head = current.next;} else {// 找到這個元素和這個元素之前的元素let previous = this.getElementAt(index - 1);current = previous.next;// 將這個元素的 next 賦值給這個元素之前元素的 nextprevious.next = current.next;}this.count--;// 返回要移除的元素return current.element;}// 返回指定元素的位置indexOf(element) {// 從頭開始找let current = this.head;// 不超過最大長度for (let i = 0; i < this.size() && current != null; i++){if (current.element === element){ // 找到相等的就返回下標return i;}current = current.next;}return -1;}// 移除指定元素remove(element) {// 獲取指定元素位置let index = this.indexOf(element);// 移除指定位置元素return this.removeAt(index);}// 是否為空isEmpty() {return this.size() === 0;}// 長度size() {return this.count;}// 獲取表頭getHead() {return this.head;}// 清空鏈表clear() {this.head = undefined;this.count = 0;}// 轉換為字符串輸出toString() {if (this.head == null) {return '';}let objString = `${this.head.element}`;let current = this.head.next;for (let i = 1; i < this.size() && current != null; i++) {objString = `${objString},${current.element}`;current = current.next;}return objString;} } let a = new LinkedList(); a.push('a'); a.push('b'); a.push('c'); a.push('d'); a.push('e'); a.push('f'); a.push('h'); a.push('i'); a.push('j'); a.push('k'); a.push('l'); a.push('m'); a.push('n'); a.push('o'); a.push('p'); a.push('q'); a.remove('a'); a.insert('a',1); console.log(a); 復制代碼

插入元素圖解：

現在有狗鏈兩節，我要在中間加一節

先把兩節分開，

然后把前邊的尾部與要加的頭部相連，然后把要加的尾部與后邊的頭部相連

0 連 xx , xx 連 1

鏈表的變種

雙向鏈表

我們已經知道鏈表的每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用（也稱指針或鏈接）組成，雙向鏈表除了這個基本特性，每個元素還包含一個指向前一個元素的引用，如圖所示：

循環鏈表

循環鏈表就是鏈表的最后一個指向下一個元素的引用指向了第一個元素，使其成為循環鏈表

雙向循環鏈表

雙向循環鏈表就是雙向鏈表的第一個元素指向前一個的引用指向了最后一個元素，而最后一個元素指向下一個元素的引用指向了第一個元素，如圖所示：

總結

以上是生活随笔為你收集整理的[ JavaScript ] 数据结构与算法 —— 链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。