JS數據結構第二篇—鏈表
一、什麼是鏈表
鏈表是一種鏈式存儲的線性表,是由一組節點組成的集合,每一個節點都存儲了下一個節點的地址;指向另一個節點的引用叫鏈;和數組中的元素內存地址是連續的相比,鏈表中的所有元素的內存地址不一定是連續的。結構模擬如圖:
一般來說,說到鏈表,就要提下數組,一般鏈表都是和數組進行對比。
在很多編程語言中,數組的長度時固定的,所以數組中的增加和刪除比較麻煩,需要頻繁的移動數組中的其他元素。
然而,JavaScript中的數組並不存在上述問題,JS中的數組相對其他語言使用上更方便,因為JS中的數組本質是一個類似數組的對象,這就使得JS的數組雖然使用更方便,但比其他語言(C++、Java、C#)的數組效率要低。
所以,在實際應用中如果發現數組很慢,就可以考慮使用鏈表來替代它。除了對數據的隨機訪問,鏈表幾乎可以用在任何可以使用一維數組的情況中。如果需要隨機訪問,數組仍然是更好的選擇。
二、鏈表的設計
為了對鏈表更好的使用,我們設計了類LinkedList, 對鏈表中節點的增刪改查方法進行了封裝。結構如圖:
其中size和head為LinkedList構造函數私有屬性,size記錄鏈表中有多少個節點,head指向鏈表的頭結點。
根據需要對外暴露了以下方法(可以根據需要自定義其他方法):
單向LinkedList完整設計代碼:
/** * 自定義鏈表:對外公開的方法有 * append(element) 在鏈表最後追加節點 * insert(index, element) 根據索引index, 在索引位置插入節點 * remove(element) 刪除節點 * removeAt(index) 刪除指定索引節點 * removeAll(element) 刪除所有匹配的節點 * set(index, element) 根據索引,修改對應索引的節點值 * get(index) 根據索引獲取節點信息 * indexOf(element) 獲取某個節點的索引位置 * clear() 清空所有節點 * length() 返回節點長度 * print() 打印所有節點信息 * toString() 打印所有節點信息,同print * */ const LinkedList = function(){ let head = null; let size = 0; //記錄鏈表元素個數 //Node模型 function LinkNode(element, next){ this.element = element; this.next = next; } //元素越界檢查, 越界拋出異常 function outOfBounds(index){ if (index < 0 || index >= size){ throw("抱歉,目標位置不存在!"); } } //根據索引,獲取目標對象 function node(index){ outOfBounds(index); let obj = head; for (let i = 0; i < index; i++){ obj = obj.next; } return obj; } //新增一個元素 function append(element){ if (size == 0){ head = new LinkNode(element, null); } else{ let obj = node(size-1); obj.next = new LinkNode(element, null); } size++; } //插入一個元素 function insert(index, element){ if (index == 0){ head = new LinkNode(element, head); } else{ let obj = node(index-1); obj.next = new LinkNode(element, obj.next); } size++; } //修改元素 function set(index, element){ let obj = node(index); obj.element = element; } //根據值移除節點元素 function remove(element){ if (size < 1) return null; if (head.element == element){ head = head.next; size--; return element; } else{ let temp = head; while(temp.next){ if (temp.next.element == element){ temp.next = temp.next.next; size--; return element; } else{ temp = temp.next; } } } return null; } //根據索引移除節點 function removeAt(index){ outOfBounds(index); let element = null; if (index == 0){ element = head.element; head = head.next; } else{ let prev = node(index-1); element = prev.next.element; prev.next = prev.next.next; } size--; return element; } //移除鏈表裡面的所有匹配值element的元素 function removeAll(element){ let virHead = new LinkNode(null, head); //創建一個虛擬頭結點,head為次節點 let tempNode = virHead, ele = null; while(tempNode.next){ if (tempNode.next.element == element){ tempNode.next = tempNode.next.next; size--; ele = element; } else{ tempNode = tempNode.next; } } //重新賦值 head = virHead.next; return ele; } //獲取某個元素 function get(index){ return node(index).element; } //獲取元素索引 function indexOf(element){ let obj = head, index = -1; for (let i = 0; i < size; i++){ if (obj.element == element){ index = i; break; } obj = obj.next; } return index; } //清除所有元素 function clear(){ head = null; size = 0; } //屬性轉字符串 function getObjString(obj){ let str = ""; if (obj instanceof Array){ str += "["; for (let i = 0; i < obj.length; i++){ str += getObjString(obj[i]); } str = str.substring(0, str.length - 2); str += "], " } else if (obj instanceof Object){ str += "{"; for (var key in obj){ let item = obj[key]; str += "\"" + key + "\": " + getObjString(item); } str = str.substring(0, str.length-2); str += "}, " } else if (typeof obj == "string"){ str += "\"" + obj + "\"" + ", "; } else{ str += obj + ", "; } return str; } function toString(){ let str = "", obj = head; for (let i = 0; i < size; i++){ str += getObjString(obj.element); obj = obj.next; } if (str.length > 0) str = str.substring(0, str.length -2); return str; } //打印所有元素 function print(){ console.log(this.toString()) } //對外公開方法 this.append = append; this.insert = insert; this.remove = remove; this.removeAt = removeAt; this.removeAll = removeAll; this.set = set; this.get = get; this.indexOf = indexOf; this.length = function(){ return size; } this.clear = clear; this.print = print; this.toString = toString; } ////測試 // let obj = new LinkedList(); // let obj1 = { title: "全明星比賽", stores: [{name: "張飛vs岳飛", store: "2:3"}, { name: "關羽vs秦瓊", store: "5:5"}]}; // // obj.append(99); // obj.append("hello") // obj.append(true) // obj.insert(3, obj1); // obj.insert(0, [12, false, "Good", 81]); // obj.print(); // console.log("obj1.index: ", obj.indexOf(obj1)); // obj.remove(0); // obj.removeAll(obj1); // obj.print(); ////測試2 console.log("\n\n......test2.....") var obj2 = new LinkedList(); obj2.append(8); obj2.insert(1,99); obj2.append('abc'); obj2.append(8); obj2.append(false); obj2.append(12); obj2.append(8); obj2.append('123'); obj2.append(8); obj2.print(); obj2.removeAll(8); //刪除所有8 obj2.print();
View Code
另外,可以在LinkedList中增加一個虛擬節點,即在頭結點之前增加一個節點,一直保留,結構如圖:
這裏代碼就不提供了,在上一份鏈表代碼中的removeAll(刪除鏈表中指定值的所有節點)方法中有用到虛擬頭結點, 下面的練習題中也有應用到虛擬頭結點,應用場景還是蠻多的。
三、鏈表練習題
推薦一個神奇的網站,可以以動畫的方式演示各種數據結構增刪改查變化,先來張展示鏈表的增刪效果圖看看:
網址:https://visualgo.net/zh
接下來做幾個鏈表的練習題,題目來自力扣,可以先自己先做一下,看看自己得分,再對比下官方提供的代碼demo
3.1 刪除排序鏈表中的重複元素_第83題
參考demo:
/** * 給定一個排序鏈表,刪除所有重複的元素,使得每個元素只出現一次。 示例 1: 輸入: 1->1->2 輸出: 1->2 示例 2: 輸入: 1->1->2->3->3 輸出: 1->2->3 力扣得分: 執行用時 :108 ms, 在所有 JavaScript 提交中擊敗77.12%的用戶 內存消耗 :37.4 MB, 在所有 JavaScript 提交中擊敗了5.03%的用戶 */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ function ListNode(val){ this.val = val; this.next = null; } /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { let virHead = new ListNode(0); //增加一個虛擬節點 virHead.next = head; let temp = virHead, obj = {}; while(temp.next){ if (obj[temp.next.val]){ //表示為重複節點,刪除這個節點 temp.next = temp.next.next; } else{ // obj[temp.next.val] = 1; temp = temp.next; } } return virHead.next; } //測試 var obj = new ListNode(1); obj.next = new ListNode(2); obj.next.next = new ListNode(1); obj.next.next.next = new ListNode(3); obj.next.next.next.next = new ListNode(1); obj.next.next.next.next.next = new ListNode(2); obj.next.next.next.next.next.next = new ListNode(3); console.log(obj); console.log(".>>>>>>刪除重複節點:") console.log(deleteDuplicates(obj));
View Code
3.2 判斷是否環形鏈表_第141題
參考demo:
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function(head) { //快慢指針,快指針每次走兩步,慢指針每次走一步 let obj1 = head, obj2 = head; //obj1快指針,obj2為慢指針 while(obj2){ obj2 = obj2.next; if (obj1){ obj1 = obj1.next; } if (obj1){ obj1 = obj1.next; } if (obj2 == obj1 && obj1) return true; } return false; }; function ListNode(val){ this.val = val; this.next = null; } //測試 console.log(">>>>>>環形鏈表》》測試》》") let node1 = new ListNode(1); let node2 = new ListNode(2); let node3 = new ListNode(3); let node4 = new ListNode(4); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node2; let res = hasCycle(node1); console.log("res: ", res);
View Code
3.3 移除鏈表中給定值的所有元素_第203題
參考demo1:
/** 刪除鏈表中等於給定值 val 的所有節點。 示例: 輸入: 1->2->6->3->4->5->6, val = 6 輸出: 1->2->3->4->5 * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * 在力扣中得分:耗時160ms, 打敗Javascript中17.87%; 內存消耗37.5M, 打敗JavaScript中24.79% , 更優化的寫法是? * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { let newHead = null, curNode = null; while(head){ if (head.val != val){ if (curNode){ curNode.next = new ListNode(head.val); curNode = curNode.next; } else{ curNode = new ListNode(head.val); newHead = curNode; } } head = head.next; } return newHead; } function ListNode(val){ this.val = val; this.next = null; } //測試 console.log(">>>>移除鏈表元素測試》》》") var node = new ListNode(1); node.next = new ListNode(2); // node.next.next = new ListNode(5); // node.next.next.next = new ListNode(4); // node.next.next.next.next = new ListNode(6); // node.next.next.next.next.next = new ListNode(8); // node.next.next.next.next.next.next = new ListNode(4); // var newNode = removeElements(node, 6); // console.log(newNode); var newNode = removeElements(node, 2); console.log(newNode);
View Code
參考demo2:
/** 刪除鏈表中等於給定值 val 的所有節點。 示例: 輸入: 1->2->6->3->4->5->6, val = 6 輸出: 1->2->3->4->5 * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** 第二種寫法 * 在力扣中得分:耗時112ms, 打敗Javascript中90.28%; 內存消耗37.5M, 打敗JavaScript中24.79% * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { if (!head) return head; let newHead = new ListNode(-1); newHead.next = head; //把head作為newHead的下一個 let tmpNode = newHead; while(tmpNode.next){ if (tmpNode.next.val == val){ tmpNode.next = tmpNode.next.next; } else{ tmpNode = tmpNode.next; } } return newHead.next; //返回newHead的下一個,就是我們想要的結果 } function ListNode(val){ this.val = val; this.next = null; } //測試 console.log(">>>>移除鏈表元素測試》》》") var node = new ListNode(1); node.next = new ListNode(2); // node.next.next = new ListNode(5); // node.next.next.next = new ListNode(4); // node.next.next.next.next = new ListNode(6); // node.next.next.next.next.next = new ListNode(8); // node.next.next.next.next.next.next = new ListNode(4); // var newNode = removeElements(node, 6); // console.log(newNode); var newNode = removeElements(node, 2); console.log(newNode);
View Code
3.4 反轉鏈表_第206題
參考demo1_迭代方式:
/* 反轉一個單鏈表。使用迭代方式實現 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 力扣中測試執行用時 : 76 ms, 在所有 JavaScript 提交中擊敗了97.74%的用戶 內存消耗 :36 MB, 在所有 JavaScript 提交中擊敗了6.92%的用戶 * */ function ListNode(val){ this.val = val; this.next = null; } /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let newHead = null; while(head){ let tmpNode= newHead; newHead = new ListNode(head.val); newHead.next = tmpNode; head = head.next; } return newHead; } ////測試 var node = new ListNode(9); node.next = new ListNode(99); node.next.next = new ListNode(999); node.next.next.next = new ListNode(33); console.log("原鏈表:", node); console.log(".....反轉....") console.log(reverseList(node))
View Code
參考demo2_遞歸方式:
/* 反轉一個單鏈表。 使用遞歸方式實現 示例: 輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL 力扣測試得分: 執行用時 :80 ms, 在所有 JavaScript 提交中擊敗了95.56%的用戶 內存消耗 :36.3 MB, 在所有 JavaScript 提交中擊敗了5.03%的用戶 * */ function ListNode(val){ this.val = val; this.next = null; } /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { return getNewNode(head).first; } /** * 遞歸,好繞啊: * 推演:加入2->3->4->5 遞歸: * @param node */ function getNewNode(node){ if (!node) return {first: null, cur: null }; var cur = new ListNode(node.val); ////一直遞歸遞歸,拿到原鏈表最後一個元素開始返回 var res = getNewNode(node.next); if (res.first) { res.cur.next = cur; //設置 return { first: res.first, //反轉鏈表的第一個元素 cur: cur } } console.log("666_node.val: ", node.val); /** * 原鏈表最後一個元素會執行到這裏,最後一個元素作為反轉鏈表的第一個元素返回 */ return { first: cur, //反轉鏈表的第一個元素 cur: cur //每次遞歸返回的一個元素 }; } //測試 var node = new ListNode(2); node.next = new ListNode(3); node.next.next = new ListNode(4); node.next.next.next = new ListNode(5); console.log("\n\n*****原鏈表****") console.log(node); console.log("......反轉.....") console.log(reverseList(node));
View Code
3.5 查找鏈表的中間結點_第876題
參考代碼demo1_迭代方式:
/** * 給定一個帶有頭結點 head 的非空單鏈表,返回鏈表的中間結點。 如果有兩个中間結點,則返回第二个中間結點。 示例 1: 輸入:[1,2,3,4,5] 輸出:此列表中的結點 3 (序列化形式:[3,4,5]) 返回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。 注意,我們返回了一個 ListNode 類型的對象 ans,這樣: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2: 輸入:[1,2,3,4,5,6] 輸出:此列表中的結點 4 (序列化形式:[4,5,6]) 由於該列表有兩个中間結點,值分別為 3 和 4,我們返回第二個結點。 提示: 給定鏈表的結點數介於 1 和 100 之間。 力扣得分: 執行用時 :108 ms, 在所有 JavaScript 提交中擊敗了19.44%的用戶 內存消耗 :33.6 MB, 在所有 JavaScript 提交中擊敗了74.60%的用戶 */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ function ListNode(val){ this.val = val; this.next = null; } /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { if (!head) return head; let arr = []; while(head){ arr.push(head); head = head.next; } let len = arr.length; return len % 2 == 0 ? arr[len/2] : arr[(len-1)/2]; }; //測試 var obj = new ListNode(1), temp = obj; for (let i = 0; i < 6; i++){ temp.next = new ListNode(2+i); temp = temp.next; } console.log(obj); console.log("獲取中間節點:") console.log(middleNode(obj));
View Code
參考代碼demo2_快慢指針:
/** * 給定一個帶有頭結點 head 的非空單鏈表,返回鏈表的中間結點。 如果有兩个中間結點,則返回第二个中間結點。 示例 1: 輸入:[1,2,3,4,5] 輸出:此列表中的結點 3 (序列化形式:[3,4,5]) 返回的結點值為 3 。 (測評系統對該結點序列化表述是 [3,4,5])。 注意,我們返回了一個 ListNode 類型的對象 ans,這樣: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2: 輸入:[1,2,3,4,5,6] 輸出:此列表中的結點 4 (序列化形式:[4,5,6]) 由於該列表有兩个中間結點,值分別為 3 和 4,我們返回第二個結點。 提示: 給定鏈表的結點數介於 1 和 100 之間。 力扣得分: 執行用時 :120 ms, 在所有 JavaScript 提交中擊敗了12.22%的用戶 內存消耗 :34.1 MB, 在所有 JavaScript 提交中擊敗了11.11%的用戶 官方答案,官方這個確實簡潔: let slow = fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; 官方力扣得分: 執行用時 :64 ms, 在所有 JavaScript 提交中擊敗了99.44%的用戶 內存消耗 :34.1 MB, 在所有 JavaScript 提交中擊敗了11.11%的用戶 */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ function ListNode(val){ this.val = val; this.next = null; } /** 用快慢指針來處理下 * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { // let slow = head, fast = head; // while(slow){ // if (fast){ // fast = fast.next; // if (fast){ // fast = fast.next; // } // else{ // return slow; // } // } // else{ // return slow; // } // slow = slow.next; // } // return head; //官方答案:簡潔明了 let slow = fast = head; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; }; //測試 var obj = new ListNode(1), temp = obj; for (let i = 0; i < 6; i++){ temp.next = new ListNode(2+i); temp = temp.next; } console.log(obj); console.log("獲取中間節點:") console.log(middleNode(obj)); obj = new ListNode(90), temp = obj; for (let i = 0; i < 5; i++){ temp.next = new ListNode(91+i); temp = temp.next; } console.log(obj); console.log("獲取中間節點:") console.log(middleNode(obj));
View Code
參考Demo地址:https://github.com/xiaotanit/Tan_DataStruct
【精選推薦文章】
如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!
想要讓你的商品在網路上成為最夯、最多人討論的話題?
網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線
不管是台北網頁設計公司、台中網頁設計公司,全省皆有專員為您服務
想知道最厲害的台北網頁設計公司推薦、台中網頁設計公司推薦專業設計師"嚨底家"!!