【從蛋殼到滿天飛】JS 資料結構解析和演算法實現-連結串列

摘要： 【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap...

【從蛋殼到滿天飛】JS 資料結構解析和演算法實現，全部文章大概的內容如下： Arrays(陣列)、Stacks(棧)、Queues(佇列)、LinkedList(連結串列)、Recursion(遞迴思想)、BinarySearchTree(二分搜尋樹)、Set(集合)、Map(對映)、Heap(堆)、PriorityQueue(優先佇列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(並查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(雜湊表)

原始碼有三個：ES6（單個單個的 class 型別的 js 檔案） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部原始碼已上傳 github，點選我吧 ，光看文章能夠掌握兩成，動手敲程式碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對資料結構想了解並且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加原始碼，時間跨度也算將近半年時間了，希望對想學習資料結構的人或者正在學習資料結構的人群有幫助。

連結串列

1. 連結串列是最基礎的動態資料結構
2. 連結串列是非常重要的線性資料結構
   1. 以下三種，底層都是依託靜態陣列，靠 resize 解決固定容量問題。
   2. 動態陣列：所謂動態，是從使用者的角度上來看的。
   3. 棧
   4. 佇列
3. 連結串列是真正的動態資料結構
   1. 它是資料結構中的一個重點，
   2. 也有可能是一個難點，
   3. 它是最簡單的一種動態資料結構，
   4. 其它更高階的動態資料結構有 二分搜尋樹、Trie、
   5. 平衡二叉樹、AVL、紅黑樹等等，
   6. 熟悉了最簡單的動態資料結構，
   7. 那麼對於更高階的也會比較容易掌握了。
4. 對於連結串列來說它涉及到了計算機領域一個非常重要的概念
   1. 更深入的理解引用（或者指標），
   2. 這個概念和記憶體相關，
   3. 在 JS 裡面不需要手動的管理記憶體，
   4. 但是對連結串列這種資料結構更加深入的理解，
   5. 可以讓你對 引用、指標甚至計算機系統中
   6. 和記憶體管理相關很多話題有更加深入的認識。
5. 連結串列本身也是有它非常清晰的遞迴結構的，
   1. 只不過由於連結串列這種資料結構它本身是一種線性的資料結構，
   2. 所以依然可以非常容易的使用迴圈的方式來對連結串列進行操作，
   3. 但是連結串列本身由於它天生也是具有這種遞迴結構的性質，
   4. 所以它也能讓你更加深入的理解遞迴機制相應的這種資料結構，
   5. 在學習更加複雜的資料結構的時候，
   6. 對遞迴這種邏輯機制深入的理解是必不可缺的。
6. 連結串列這種資料結構本身就具有功能性
   1. 它可以用來組成更加複雜的資料結構，
   2. 比如 圖結構、hash 表、棧(連結串列版)、佇列(連結串列版)，
   3. 所以他可以輔助組成其它資料結構。

什麼是連結串列

1. 資料儲存在“節點”（Node）中
   1. 把資料存在一種單獨的結構中，
   2. 這個結構通常管它叫做節點，
   3. 對於連結串列節點來說他通常只有兩部分，
   4. 一部分就是儲存真正的資料，
   5. 另一部分儲存的是當前節點的下一個節點，
   6. 連結串列其實就像一個火車，每一個節點都是一節車廂，
   7. 在車廂中儲存資料，而車廂和車廂之間還會進行連線，
   8. 以使得這些資料是整合在一起的，
   9. 這樣使用者可以方便的在所有的這些資料上進行查詢等等其它的操作，
   10. 資料與資料之間連線就是用下面的這個 next 來完成的

   class Node {
   e; //Element
   next; //Node
   }
   複製程式碼

2. 連結串列的優點
   1. 真正的動態，不需要處理固定容量的問題，
   2. 它不像靜態陣列那樣一下子 new 出來一片空間，
   3. 也根本不需要考慮這個空間是不是不夠用，
   4. 也根本不用去考慮這個空間是不是開多了。
3. 對於連結串列來說，你需要多少個數據。
   1. 你就可以生成多少個節點，
   2. 把它們掛接起來了，這就是所謂的動態。
4. 連結串列的缺點

   O(1)
   

陣列和連結串列的對比

1. 陣列

   scores[2]
   

2. 連結串列

   1. 連結串列不適合用於索引有語意的情況。
   2. 最大的優點：動態儲存。

3. 對比

   1. 陣列也可以沒有語意，並不是所有的時候索引是有語意的，
   2. 也並不是所有有語意的這樣的一個標誌就適合做索引，如身份證號，
   3. 將一個靜態陣列改變為一個動態陣列，
   4. 就是在應付不方便使用索引的時候有關資料儲存的問題，
   5. 對於這樣的儲存資料的需求使用連結串列是更合適的，
   6. 因為連結串列最大的優點是動態儲存。

4. 要清楚什麼時候使用陣列這樣的靜態資料結構，

   1. 什麼時候使用連結串列這類的動態資料結構。

5. 簡單的程式碼示例MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   class MyLinkedList {
   constructor() {}
   }
   複製程式碼

在連結串列中進行新增、插入操作

1. 連結串列是通過節點來裝載元素

   MyLinkedList
   

2. 給自定義陣列新增元素是從陣列尾部開始新增，
   1. 給連結串列新增元素是從陣列頭部開始新增，
   2. 因為自定義陣列有維護一個 size，
   3. 這個 size 指向的是下一個待新增元素的位置，
   4. 所以你直接將 size 做索引直接賦值即可，
   5. 有 size 這個變數在跟蹤陣列的尾巴，
   6. 而對於連結串列來說 有設定一個連結串列的頭這樣的一個變數，
   7. 也就是說有一個變數在跟蹤連結串列的頭，
   8. 並沒有一個變數去跟蹤連結串列的尾巴，
   9. 所以在連結串列頭部新增元素是非常方便。
3. 新增操作原理

   node.next = head
   head = node
   

4. 在連結串列頭部新增元素非常簡單，
   1. 只需要建立節點，讓節點的 next 指向 head，
   2. 然後讓 head 重新指向這個節點，也就是讓 head 變成新的元素，
   3. 因為連結串列是從頭部新增元素的。
5. 在連結串列中間新增元素，

   node.next = prev.next
   prev.next = node
   

6. 在連結串列的操作中很多時候順序非常重要，
   1. 如在連結串列中插入一個元素，在指定的元素後面插入一個元素，
   2. 並且不影響整個連結串列結構，和在連結串列中間新增元素一樣，
   3. 把原本的node.next = prev.next 和prev.next = node
   4. 的順序變一下，prev.next = node 在前，
   5. node.next = prev.next 在後，這樣一來邏輯就不成立了，
   6. 連結串列不僅斷開了，而且新節點的 next 指向的是自己，死迴圈了，
   7. 所以一樣的程式碼，順序顛倒了，得到的結果就是錯誤的。
7. 在連結串列的 index(0-based)位置新增元素 e
   1. 通過索引來操作連結串列，在連結串列中不是一個常用的操作，
   2. 因為在選擇使用連結串列的時候通常就選擇不使用索引了，
   3. 但是這個需求在面試等一些考題中出現的概率很大，
   4. 所以他的主要作用更多的是一個練習。

學習方式

1. 如果剛接觸連結串列，對連結串列不熟悉，
   1. 然後很多這種操作在腦子裡不能非常快的反應出來，
   2. 不清楚他的意義是什麼，那你可以使用紙筆來稍微畫一下，
   3. 每一步程式邏輯的執行意味著當前這個連結串列變成了什麼樣子，
   4. 這個過程能夠幫助你更加深入的理解程式，
   5. 包括在除錯的時候來看你的程式到底為什麼出了錯誤時，
   6. 非常非常有幫助的，不要犯懶，為了更加深入的理解你的程式，
   7. 不能只盯著你的程式碼去想，一定要寫寫畫畫，
   8. 必要的時候甚至根據你的程式進行具體的除錯，
   9. 這些都是非常重要非常有幫助的。

程式碼示例(class: MyLinkedList)

1. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.head = null;
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSise() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   let node = new MyLinkedListNode(element, null);
   node.next = this.head;
   this.head = node;
   this.size++;
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   if (index === 0) {
   this.addFirst(element);
   } else {
   // 第一個prev就是head
   let prev = this.head;
   
   // 變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 1; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   }
   複製程式碼

給連結串列設立虛擬頭節點

1. 在連結串列中進行指定索引處插入元素時
   1. 對連結串列頭插入元素與對連結串列其它位置插入元素的邏輯有區別，
   2. 所以就導致每次操作都需要對索引進行判斷，
   3. 如果你是在索引 0 的位置插入元素，那麼就沒有 prev(前一個元素),
   4. 自然就不可以使用node.next = prev.next 和prev.next = node 了，
   5. 那時候你可以直接使用node.next = head 和head = node ，
   6. 不過已經有了向連結串列頭新增元素的方法了，
   7. 所以向頭部插入元素時根本就不需要這麼做，
   8. 這時候可以通過給連結串列設立虛擬頭節點來解決這個問題。
2. 為什麼對連結串列頭插入元素那麼特殊？
   1. 因為插入元素時，必需要找到該索引位置的節點之前的一個節點(prev)，
   2. 而連結串列頭(head)之前並沒有任何節點，所以邏輯上就會特殊一些。
   3. 不過在連結串列的具體實現中有一個非常常用的技巧，
   4. 可以把連結串列頭的這種特殊的操作與其它的操作一起統一起來，
   5. 其實這個方法的想法很簡單，既然它沒有連結串列頭之前的節點，
   6. 那就自己造一個連結串列頭之前的節點，
   7. 這個連結串列頭之前的節點不會用來儲存任何元素，儲存的資料為空，
   8. 這個空節點就稱之為整個連結串列頭的 head，也可以叫它 dummyHead，
   9. 因為它就是一個假的 head，它也是為連結串列設立的虛擬頭節點，
   10. 這樣一來 連結串列的第一個元素就是 dummyHead 的 next 所對應的那個節點，
   11. 因為 dummyHead 這個位置的元素是根本不存在的，
   12. 對使用者來講也是根本沒有意義的，
   13. 這只是為了編寫邏輯方便而出現的一個虛擬的頭節點，
   14. 所以一個這樣的內部機制對使用者來說也是不可見的，
   15. 使用者不知道連結串列中有沒有虛擬的頭節點，
   16. 這和自定義的迴圈佇列有點像，自定義迴圈佇列中有一個不可用的空間，
   17. 有意識地去浪費一個空間，為了編寫邏輯更加的方便，
   18. 從而也讓效能在整體上得到了提升。
3. 有了 dummyHead 之後就不需要處理頭節點這個特殊的操作
   1. 因為當你在頭部插入元素時，可以這樣
   2. node.next = dummyHead.next 、dummyHead.next = node ，
   3. 這樣你就解決了每次插入時都要進行一次邏輯判斷了，
   4. 這樣一來就說明了連結串列中所有的節點都有前一個節點了，
   5. 在初始的時候 dummyHead 指向的是索引為 0 的元素前一個位置的節點。
4. 連結串列操作的實際原理

   node.next = head.next;head = node;
   node.next = dummyHead.next; dummyHead.next = node;
   dummyHead.next
   

程式碼示例(class: MyLinkedList)

1. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.dummyHead = new MyLinkedListNode(null, null);
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSise() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   // let node = new MyLinkedListNode(element, null);
   // node.next = this.head;
   // this.head = node;
   // this.size ++;
   
   // 改用虛擬頭節點
   insert(0, element);
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   // 第一個prev就是dummyHead
   let prev = this.dummyHead;
   // 之前變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
   // （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為連結串列中的實際節點），
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 0; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   }
   複製程式碼

在連結串列中進行遍歷、查詢、修改操作

1. 如果要找指定索引元素的前一個節點

   dummyHead
   dummyHead.next
   

程式碼示例(class: MyLinkedList, class: Main)

1. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.dummyHead = new MyLinkedListNode(null, null);
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSize() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   // let node = new MyLinkedListNode(element, null);
   // node.next = this.head;
   // this.head = node;
   // this.size ++;
   
   // 改用虛擬頭節點
   this.insert(0, element);
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   // 第一個prev就是dummyHead
   let prev = this.dummyHead;
   // 之前變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
   // （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為連結串列中的實際節點），
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 0; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   
   // 獲取指定索引位置的元素
   get(index) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 如果你要找指定索引節點的前一個節點 就使用dummyHead
   // 如果你要找到指定索引節點 就使用dummyHead.next
   // 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
   // dummyHead.next才是真正被記錄的第一個節點。
   let node = this.dummyHead.next;
   for (var i = 0; i < index; i++) {
   node = node.next;
   }
   
   return node.element;
   }
   
   // 獲取頭節點的元素
   getFirst() {
   return this.get(0);
   }
   
   // 獲取尾節點的元素
   getLast() {
   return this.get(this.size - 1);
   }
   
   // 設定指定索引位置的元素值
   set(index, element) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 從第一個真正被記錄的節點開始，從0開始
   let node = this.dummyHead.next;
   
   // 索引為 0 時，實際上切換到的節點 它的索引為 1
   // i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
   for (let i = 0; i < index; i++) {
   // 每一次切換 都只是改變引用
   // 不的在連結串列中找下一個節點
   node = node.next;
   }
   
   node.element = element;
   }
   
   // 所有節點中是否有包含該元素
   contains(element) {
   let node = this.dummyHead;
   
   while (node.next !== null) {
   if (node.next.element === element) return true;
   // 不停的向下切換
   node = node.next;
   }
   
   return false;
   }
   
   // 輸出連結串列中的資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedList: size = ${this.size}，\n`;
   arrInfo += `data = front[`;
   let node = this.dummyHead.next;
   while (node.next !== null) {
   arrInfo += `${node.element}->`;
   node = node.next;
   }
   arrInfo += 'NULL] tail';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

2. Main

   class Main {
   constructor () {
   /this.alterLine("MyLinkedList Area");
   let mylinkedList = new MyLinkedList();
   
   for (let i = 1; i <= 5 ; i++) {
   mylinkedList.addFirst(i);
   console.log(mylinkedList.toString());
   }
   mylinkedList.insert(2, 88888);
   console.log(mylinkedList.toString());
   }
   
   // 將內容顯示在頁面上
   show (content) {
   document.body.innerHTML += `${content}<br /><br />`;
   }
   
   // 展示分割線
   alterLine (title) {
   let line = `--------------------${title}----------------------`
   console.log(line);
   document.body.innerHTML += `${line}<br /><br />`;
   }
   }
   複製程式碼

在連結串列中進行刪除操作

1. 連結串列元素的刪除

   prev.next = delNode.next
   delNode.next = null
   delNode = delNode.next
   

程式碼示例(class: MyLinkedList, class: Main)

1. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.dummyHead = new MyLinkedListNode(null, null);
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSize() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   // let node = new MyLinkedListNode(element, null);
   // node.next = this.head;
   // this.head = node;
   // this.size ++;
   
   // 改用虛擬頭節點
   this.insert(0, element);
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   // 第一個prev就是dummyHead
   let prev = this.dummyHead;
   // 之前變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
   // （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為連結串列中的實際節點），
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 0; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   
   // 獲取指定索引位置的元素
   get(index) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 如果你要找指定索引節點的前一個節點 就使用dummyHead
   // 如果你要找到指定索引節點 就使用dummyHead.next
   // 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
   // dummyHead.next才是真正被記錄的第一個節點。
   let node = this.dummyHead.next;
   for (var i = 0; i < index; i++) {
   node = node.next;
   }
   
   return node.element;
   }
   
   // 獲取頭節點的元素
   getFirst() {
   return this.get(0);
   }
   
   // 獲取尾節點的元素
   getLast() {
   return this.get(this.size - 1);
   }
   
   // 設定指定索引位置的元素值
   set(index, element) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 從第一個真正被記錄的節點開始，從0開始
   let node = this.dummyHead.next;
   
   // 索引為 0 時，實際上切換到的節點 它的索引為 1
   // i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
   for (let i = 0; i < index; i++) {
   // 每一次切換 都只是改變引用
   // 不的在連結串列中找下一個節點
   node = node.next;
   }
   
   node.element = element;
   }
   
   // 所有節點中是否有包含該元素
   contains(element) {
   let node = this.dummyHead;
   
   while (node.next !== null) {
   if (node.next.element === element) return true;
   // 不停的向下切換
   node = node.next;
   }
   
   return false;
   }
   
   // 刪除指定索引位置的節點
   remove(index) {
   // 驗證索引的合法性
   if (index < 0 || index >= this.size) {
   throw new Error('remove error. index < 0 or index > this.size');
   }
   
   let node = this.dummyHead;
   for (let i = 0; i < index; i++) {
   node = node.next;
   }
   
   // 待刪除的節點
   let delNode = node.next;
   // 給待刪除那個節點的前一個的節點的next引用替換為
   // 但刪除的這個節點的next
   node.next = delNode.next;
   // 或者這樣也行
   // node.next = node.next.next;
   
   // 臨時儲存待刪除的那個節點裡的元素
   let element = delNode.element;
   // 清空 待刪除的節點
   delNode = null;
   this.size--;
   
   return element;
   }
   
   // 擴充套件：移除連結串列頭的元素
   removeFirst() {
   return this.remove(0);
   }
   
   // 擴充套件：移除連結串列尾部的元素
   removeLast() {
   return this.remove(this.size - 1);
   }
   
   // 輸出連結串列中的資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedList: size = ${this.size}，\n`;
   arrInfo += `data = front[`;
   let node = this.dummyHead.next;
   while (node.next !== null) {
   arrInfo += `${node.element}->`;
   node = node.next;
   }
   arrInfo += 'NULL] tail';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

2. Main

   class Main {
   constructor() {
   this.alterLine('MyLinkedList Area');
   let mylinkedList = new MyLinkedList();
   
   for (let i = 1; i <= 5; i++) {
   mylinkedList.addFirst(i);
   console.log(mylinkedList.toString());
   }
   mylinkedList.insert(2, 88888);
   console.log(mylinkedList.toString());
   
   mylinkedList.remove(2);
   console.log(mylinkedList.toString());
   
   mylinkedList.removeFirst();
   console.log(mylinkedList.toString());
   
   mylinkedList.removeLast();
   console.log(mylinkedList.toString());
   }
   
   // 將內容顯示在頁面上
   show(content) {
   document.body.innerHTML += `${content}<br /><br />`;
   }
   
   // 展示分割線
   alterLine(title) {
   let line = `--------------------${title}----------------------`;
   console.log(line);
   document.body.innerHTML += `${line}<br /><br />`;
   }
   }
   複製程式碼

連結串列的時間複雜度分析

1. 增：O(n) ：在只對連結串列頭進行操作時為O(1)
2. 刪：O(n) ：在只對連結串列頭進行操作時為O(1)
3. 改：O(n)
4. 查：O(n) ：只查連結串列頭的元素時為O(1)
5. 連結串列增刪改查的時間複雜度
   1. 整體上要比陣列增刪改查的時間複雜度要差，
   2. 因為陣列有一個優勢，
   3. 你有索引的話你就可以快速訪問，
   4. 而連結串列沒有這樣的優勢
   5. 但是連結串列的優勢是，
   6. 如果你只對連結串列頭進行增刪的操作，
   7. 那麼它的時間複雜度是 O(1)級別的，
   8. 而且它整體是動態的，所以不會大量的浪費記憶體空間。 6.連結串列適合做的事情
   9. 不去修改、也不去查任意的元素，
   10. 就算查，也只能查連結串列頭的元素，
   11. 查的時候，只有那樣才是 O(1)級別的時間複雜度，
   12. 並且增加刪除的時候只對連結串列頭進行操作，
   13. 只有在這種時候才會和陣列整體的時間複雜度是一樣的，
   14. 不過連結串列整體是動態的，不會去大量的浪費記憶體空間，
   15. 所以它具有一定的優勢。
6. 連結串列還有諸多的改進的方式
   1. 所以應用連結串列在一些情況下仍然是有它的優勢的，
   2. 最最重要的是 連結串列本身是一種最最基礎的動態資料結構，
   3. 對這種動態資料結構要深刻的理解和掌握，
   4. 對於學習更重要的動態資料結構是有巨大的幫助，
   5. 比如說二叉樹、平衡二叉樹、AVL、紅黑樹等等。

### 新增操作 O(n)

1. addLast(e) ：O(n)
   1. 會從頭遍歷到尾，
   2. 找到最後一個節點之後才能新增元素
2. addFirst(e) ：O(1)
   1. 直接從頭部新增元素
3. insert(index, e) ：O(n/2) = O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 檢索到合適的位置才會新增這個元素。

刪除操作 O(n)

1. removeLast() ：O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 找到最後一個節點後才會刪除
2. removeFirst() ：O(1)
   1. 直接從頭部刪除這個節點
3. remove(index) ：O(n/2) = O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 檢索到合適的位置才會移除這個元素

修改操作 O(n)

1. set(index, e) ：O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 找到了合適位置的節點後，
   3. 才會修改元素

查詢操作 O(n)

1. get(index) ：O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 找到了合適位置的節點後，
   3. 返回這個元素。
2. contains(e) ：O(n)
   1. 會去遍歷連結串列中每一個節點，
   2. 返回 是否有相同元素的 bool 值。
3. find(e) ：O(n)
   1. 這個方法對連結串列來說是沒有用的，
   2. 就算你拿到了那個索引你也不能快速訪問。

使用連結串列來實現棧

1. 對連結串列進行新增操作時

   O(n)
   O(1)
   

2. 對連結串列進行刪除操作時

   O(n)
   O(1)
   

3. 對連結串列進行查詢操作時

   O(n)
   O(1)
   

4. 這些特性很符合棧的需求
   1. 棧是後進先出的，並且棧只查棧頂的元素，
   2. 所以可以使用連結串列來實現棧這樣的資料結構。

連結串列實現的棧

1. MyLinkedListStack 的介面。

   void push(E e)
   E pop()
   E peek()
   int getSize()
   boolean isEmpty()
   

程式碼示例

1. (class: MyLinkedList,class: MyLinkedListStack, class: Main)

2. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.dummyHead = new MyLinkedListNode(null, null);
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSize() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   // let node = new MyLinkedListNode(element, null);
   // node.next = this.head;
   // this.head = node;
   // this.size ++;
   
   // 改用虛擬頭節點
   this.insert(0, element);
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   // 第一個prev就是dummyHead
   let prev = this.dummyHead;
   // 之前變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
   // （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為連結串列中的實際節點），
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 0; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   
   // 獲取指定索引位置的元素
   get(index) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 如果你要找指定索引節點的前一個節點 就使用dummyHead
   // 如果你要找到指定索引節點 就使用dummyHead.next
   // 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
   // dummyHead.next才是真正被記錄的第一個節點。
   let node = this.dummyHead.next;
   for (var i = 0; i < index; i++) {
   node = node.next;
   }
   
   return node.element;
   }
   
   // 獲取頭節點的元素
   getFirst() {
   return this.get(0);
   }
   
   // 獲取尾節點的元素
   getLast() {
   return this.get(this.size - 1);
   }
   
   // 設定指定索引位置的元素值
   set(index, element) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 從第一個真正被記錄的節點開始，從0開始
   let node = this.dummyHead.next;
   
   // 索引為 0 時，實際上切換到的節點 它的索引為 1
   // i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
   for (let i = 0; i < index; i++) {
   // 每一次切換 都只是改變引用
   // 不的在連結串列中找下一個節點
   node = node.next;
   }
   
   node.element = element;
   }
   
   // 所有節點中是否有包含該元素
   contains(element) {
   let node = this.dummyHead;
   
   while (node.next !== null) {
   if (node.next.element === element) return true;
   // 不停的向下切換
   node = node.next;
   }
   
   return false;
   }
   
   // 刪除指定索引位置的節點
   remove(index) {
   // 驗證索引的合法性
   if (index < 0 || index >= this.size) {
   throw new Error('remove error. index < 0 or index > this.size');
   }
   
   let node = this.dummyHead;
   for (let i = 0; i < index; i++) {
   node = node.next;
   }
   
   // 待刪除的節點
   let delNode = node.next;
   // 給待刪除那個節點的前一個的節點的next引用替換為
   // 但刪除的這個節點的next
   node.next = delNode.next;
   // 或者這樣也行
   // node.next = node.next.next;
   
   // 臨時儲存待刪除的那個節點裡的元素
   let element = delNode.element;
   // 清空 待刪除的節點
   delNode = null;
   this.size--;
   
   return element;
   }
   
   // 擴充套件：移除連結串列頭的元素
   removeFirst() {
   return this.remove(0);
   }
   
   // 擴充套件：移除連結串列尾部的元素
   removeLast() {
   return this.remove(this.size - 1);
   }
   
   // 輸出連結串列中的資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedList: size = ${this.size}，\n`;
   arrInfo += `data = front[`;
   let node = this.dummyHead.next;
   while (node.next !== null) {
   arrInfo += `${node.element}->`;
   node = node.next;
   }
   arrInfo += 'NULL] tail';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

3. MyLinkedListStack

   class MyLinkedListStack {
   constructor() {
   this.myLinkedList = new MyLinkedList();
   }
   
   // 入棧
   push(element) {
   this.myLinkedList.addFirst(element);
   }
   
   // 出棧
   pop() {
   return this.myLinkedList.removeFirst();
   }
   
   // 檢視棧頂元素
   peek() {
   return this.myLinkedList.getFirst();
   }
   
   // 檢視棧中實際元素的個數
   getSize() {
   return this.myLinkedList.getSize();
   }
   
   // 判斷棧是否為空
   isEmpty() {
   return this.myLinkedList.isEmpty();
   }
   
   // 輸出棧中資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
   arrInfo += `data = stack top [`;
   let node = this.myLinkedList.dummyHead.next;
   for (var i = 1; i < this.getSize(); i++) {
   arrInfo += `${node.element},`;
   node = node.next;
   }
   if (!this.isEmpty()) {
   arrInfo += `${node.element}`;
   }
   arrInfo += ']';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

4. Main

   class Main {
   constructor() {
   this.alterLine('MyLinkedListStack Area');
   let myLinkedListStack = new MyLinkedListStack();
   for (let i = 1; i <= 5; i++) {
   myLinkedListStack.push(i);
   console.log(myLinkedListStack.toString());
   }
   
   console.log(myLinkedListStack.peek());
   this.show(myLinkedListStack.peek());
   
   for (let i = 0; i < 5; i++) {
   console.log(myLinkedListStack.toString());
   myLinkedListStack.pop();
   }
   }
   
   // 將內容顯示在頁面上
   show(content) {
   document.body.innerHTML += `${content}<br /><br />`;
   }
   
   // 展示分割線
   alterLine(title) {
   let line = `--------------------${title}----------------------`;
   console.log(line);
   document.body.innerHTML += `${line}<br /><br />`;
   }
   }
   
   window.onload = function() {
   // 執行主函式
   new Main();
   };
   複製程式碼

自定義陣列棧對比自定義連結串列棧

1. 自定義陣列棧與自定義連結串列棧的效能相差很少

   O(1)
   

程式碼示例

1. (class: MyLinkedList, class: MyLinkedListStack, class: MyArray, class: MyStack, class: Main)

2. MyLinkedList

   class MyLinkedListNode {
   constructor(element = null, next = null) {
   this.element = element;
   this.next = next;
   }
   
   // toString 2018-10-20-jwl
   toString() {
   return this.element.toString();
   }
   }
   
   class MyLinkedList {
   constructor() {
   this.dummyHead = new MyLinkedListNode(null, null);
   this.size = 0;
   }
   
   // 獲取連結串列中實際的節點個數
   getSize() {
   return this.size;
   }
   
   // 判斷連結串列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 在連結串列頭新增節點
   addFirst(element) {
   // let node = new MyLinkedListNode(element, null);
   // node.next = this.head;
   // this.head = node;
   // this.size ++;
   
   // 改用虛擬頭節點
   this.insert(0, element);
   }
   
   // 在連結串列指定索引處插入節點
   insert(index, element) {
   if (index < 0 || index > this.size) {
   throw new Error('add error. index < 0 or index > size');
   }
   
   // 第一個prev就是dummyHead
   let prev = this.dummyHead;
   // 之前變數i(索引)之所以要從 1 開始，因為索引為0的那個節點就是head，迴圈就不需要從0開始了，
   // 現在索引之所以要從 0 開始， 因為初始化時 多增加了一個虛擬的頭節點
   // （因為這個索引為0的節點並不是dummyHead，dummyHead這個節點並不記錄為連結串列中的實際節點），
   // 小於index是因為要找到指定索引位置的前一個節點
   // 迴圈是因為 要繼續找到指定索引處的節點的前一個節點
   for (var i = 0; i < index; i++) {
   // 不停的切換引用，直到找到對應索引處節點的下一個節點
   prev = prev.next;
   }
   
   let node = new MyLinkedListNode(element, null);
   node.next = prev.next;
   prev.next = node;
   this.size++;
   }
   
   // 擴充套件：在連結串列最後一個節點的位置新增節點
   addLast(element) {
   this.insert(this.size, element);
   }
   
   // 獲取指定索引位置的元素
   get(index) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 如果你要找指定索引節點的前一個節點 就使用dummyHead
   // 如果你要找到指定索引節點 就使用dummyHead.next
   // 因為duumyHead並不是第一個節點，因為它是一個虛擬節點，
   // dummyHead.next才是真正被記錄的第一個節點。
   let node = this.dummyHead.next;
   for (var i = 0; i < index; i++) {
   node = node.next;
   }
   
   return node.element;
   }
   
   // 獲取頭節點的元素
   getFirst() {
   return this.get(0);
   }
   
   // 獲取尾節點的元素
   getLast() {
   return this.get(this.size - 1);
   }
   
   // 設定指定索引位置的元素值
   set(index, element) {
   // 判斷索引合法性
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size');
   }
   
   // 從第一個真正被記錄的節點開始，從0開始
   let node = this.dummyHead.next;
   
   // 索引為 0 時，實際上切換到的節點 它的索引為 1
   // i < index ，當索引為 index-1 時， 實際上切換到的節點 它的索引為index
   for (let i = 0; i < index; i++) {
   // 每一次切換 都只是改變引用
   // 不的在連結串列中找下一個節點
   node = node.next;
   }
   
   node.element = element;
   }
   
   // 所有節點中是否有包含該元素
   contains(element) {
   let node = this.dummyHead;
   
   while (node.next !== null) {
   if (node.next.element === element) return true;
   // 不停的向下切換
   node = node.next;
   }
   
   return false;
   }
   
   // 刪除指定索引位置的節點
   remove(index) {
   // 驗證索引的合法性
   if (index < 0 || index >= this.size) {
   throw new Error('remove error. index < 0 or index > this.size');
   }
   
   let node = this.dummyHead;
   for (let i = 0; i < index; i++) {
   node = node.next;
   }
   
   // 待刪除的節點
   let delNode = node.next;
   // 給待刪除那個節點的前一個的節點的next引用替換為
   // 但刪除的這個節點的next
   node.next = delNode.next;
   // 或者這樣也行
   // node.next = node.next.next;
   
   // 臨時儲存待刪除的那個節點裡的元素
   let element = delNode.element;
   // 清空 待刪除的節點
   delNode = null;
   this.size--;
   
   return element;
   }
   
   // 擴充套件：移除連結串列頭的元素
   removeFirst() {
   return this.remove(0);
   }
   
   // 擴充套件：移除連結串列尾部的元素
   removeLast() {
   return this.remove(this.size - 1);
   }
   
   // 輸出連結串列中的資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedList: size = ${this.size}，\n`;
   arrInfo += `data = front[`;
   let node = this.dummyHead.next;
   while (node.next !== null) {
   arrInfo += `${node.element}->`;
   node = node.next;
   }
   arrInfo += 'NULL] tail';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

3. MyLinkedListStack

   class MyLinkedListStack {
   constructor() {
   this.myLinkedList = new MyLinkedList();
   }
   
   // 入棧
   push(element) {
   this.myLinkedList.addFirst(element);
   }
   
   // 出棧
   pop() {
   return this.myLinkedList.removeFirst();
   }
   
   // 檢視棧頂元素
   peek() {
   return this.myLinkedList.getFirst();
   }
   
   // 檢視棧中實際元素的個數
   getSize() {
   return this.myLinkedList.getSize();
   }
   
   // 判斷棧是否為空
   isEmpty() {
   return this.myLinkedList.isEmpty();
   }
   
   // 輸出棧中資訊
   // @Override toString 2018-10-21-jwl
   toString() {
   let arrInfo = `LinkedListStack: size = ${this.getSize()}，\n`;
   arrInfo += `data = stack top [`;
   let node = this.myLinkedList.dummyHead.next;
   for (var i = 1; i < this.getSize(); i++) {
   arrInfo += `${node.element},`;
   node = node.next;
   }
   if (!this.isEmpty()) {
   arrInfo += `${node.element}`;
   }
   arrInfo += ']';
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

4. MyArray

   class MyArray {
   // 建構函式，傳入陣列的容量capacity構造Array 預設陣列的容量capacity=10
   constructor(capacity = 10) {
   this.data = new Array(capacity);
   this.size = 0;
   }
   
   // 獲取陣列中的元素實際個數
   getSize() {
   return this.size;
   }
   
   // 獲取陣列的容量
   getCapacity() {
   return this.data.length;
   }
   
   // 判斷陣列是否為空
   isEmpty() {
   return this.size === 0;
   }
   
   // 給陣列擴容
   resize(capacity) {
   let newArray = new Array(capacity);
   for (var i = 0; i < this.size; i++) {
   newArray[i] = this.data[i];
   }
   
   // let index = this.size - 1;
   // while (index > -1) {
   //newArray[index] = this.data[index];
   //index --;
   // }
   
   this.data = newArray;
   }
   
   // 在指定索引處插入元素
   insert(index, element) {
   // 先判斷陣列是否已滿
   if (this.size == this.getCapacity()) {
   // throw new Error("add error. Array is full.");
   this.resize(this.size * 2);
   }
   
   // 然後判斷索引是否符合要求
   if (index < 0 || index > this.size) {
   throw new Error(
   'insert error. requireindex < 0 or index > size.'
   );
   }
   
   // 最後 將指定索引處騰出來
   // 從指定索引處開始，所有陣列元素全部往後移動一位
   // 從後往前移動
   for (let i = this.size - 1; i >= index; i--) {
   this.data[i + 1] = this.data[i];
   }
   
   // 在指定索引處插入元素
   this.data[index] = element;
   // 維護一下size
   this.size++;
   }
   
   // 擴充套件 在陣列最前面插入一個元素
   unshift(element) {
   this.insert(0, element);
   }
   
   // 擴充套件 在陣列最後面插入一個元素
   push(element) {
   this.insert(this.size, element);
   }
   
   // 其實在陣列中新增元素 就相當於在陣列最後面插入一個元素
   add(element) {
   if (this.size == this.getCapacity()) {
   // throw new Error("add error. Array is full.");
   this.resize(this.size * 2);
   }
   
   // size其實指向的是 當前陣列最後一個元素的 後一個位置的索引。
   this.data[this.size] = element;
   // 維護size
   this.size++;
   }
   
   // get
   get(index) {
   // 不能訪問沒有存放元素的位置
   if (index < 0 || index >= this.size) {
   throw new Error('get error. index < 0 or index >= size.');
   }
   return this.data[index];
   }
   
   // 擴充套件： 獲取陣列中第一個元素
   getFirst() {
   return this.get(0);
   }
   
   // 擴充套件： 獲取陣列中最後一個元素
   getLast() {
   return this.get(this.size - 1);
   }
   
   // set
   set(index, newElement) {
   // 不能修改沒有存放元素的位置
   if (index < 0 || index >= this.size) {
   throw new Error('set error. index < 0 or index >= size.');
   }
   this.data[index] = newElement;
   }
   
   // contain
   contain(element) {
   for (var i = 0; i < this.size; i++) {
   if (this.data[i] === element) {
   return true;
   }
   }
   return false;
   }
   
   // find
   find(element) {
   for (var i = 0; i < this.size; i++) {
   if (this.data[i] === element) {
   return i;
   }
   }
   return -1;
   }
   
   // findAll
   findAll(element) {
   // 建立一個自定義陣列來存取這些 元素的索引
   let myarray = new MyArray(this.size);
   
   for (var i = 0; i < this.size; i++) {
   if (this.data[i] === element) {
   myarray.push(i);
   }
   }
   
   // 返回這個自定義陣列
   return myarray;
   }
   
   // 刪除指定索引處的元素
   remove(index) {
   // 索引合法性驗證
   if (index < 0 || index >= this.size) {
   throw new Error('remove error. index < 0 or index >= size.');
   }
   
   // 暫存即將要被刪除的元素
   let element = this.data[index];
   
   // 後面的元素覆蓋前面的元素
   for (let i = index; i < this.size - 1; i++) {
   this.data[i] = this.data[i + 1];
   }
   
   this.size--;
   this.data[this.size] = null;
   
   // 如果size 為容量的四分之一時 就可以縮容了
   // 防止複雜度震盪
   if (Math.floor(this.getCapacity() / 4) === this.size) {
   // 縮容一半
   this.resize(Math.floor(this.getCapacity() / 2));
   }
   
   return element;
   }
   
   // 擴充套件：刪除陣列中第一個元素
   shift() {
   return this.remove(0);
   }
   
   // 擴充套件： 刪除陣列中最後一個元素
   pop() {
   return this.remove(this.size - 1);
   }
   
   // 擴充套件： 根據元素來進行刪除
   removeElement(element) {
   let index = this.find(element);
   if (index !== -1) {
   this.remove(index);
   }
   }
   
   // 擴充套件： 根據元素來刪除所有元素
   removeAllElement(element) {
   let index = this.find(element);
   while (index != -1) {
   this.remove(index);
   index = this.find(element);
   }
   
   // let indexArray = this.findAll(element);
   // let cur, index = 0;
   // for (var i = 0; i < indexArray.getSize(); i++) {
   //// 每刪除一個元素 原陣列中就少一個元素，
   //// 索引陣列中的索引值是按照大小順序排列的，
   //// 所以 這個cur記錄的是 原陣列元素索引的偏移量
   //// 只有這樣才能夠正確的刪除元素。
   //index = indexArray.get(i) - cur++;
   //this.remove(index);
   // }
   }
   
   // @Override toString 2018-10-17-jwl
   toString() {
   let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
   arrInfo += `data = [`;
   for (var i = 0; i < this.size - 1; i++) {
   arrInfo += `${this.data[i]}, `;
   }
   if (!this.isEmpty()) {
   arrInfo += `${this.data[this.size - 1]}`;
   }
   arrInfo += `]`;
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

5. MyStack

   class MyStack {
   constructor(capacity = 10) {
   this.myArray = new MyArray(capacity);
   }
   
   // 入棧
   push(element) {
   this.myArray.push(element);
   }
   
   // 出棧
   pop() {
   return this.myArray.pop();
   }
   
   // 檢視棧頂的元素
   peek() {
   return this.myArray.getLast();
   }
   
   // 棧中實際元素的個數
   getSize() {
   return this.myArray.getSize();
   }
   
   // 棧是否為空
   isEmpty() {
   return this.myArray.isEmpty();
   }
   
   // 檢視棧的容量
   getCapacity() {
   return this.myArray.getCapacity();
   }
   
   // @Override toString 2018-10-20-jwl
   toString() {
   let arrInfo = `Stack: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
   arrInfo += `data = [`;
   for (var i = 0; i < this.myArray.size - 1; i++) {
   arrInfo += `${this.myArray.data[i]}, `;
   }
   if (!this.isEmpty()) {
   arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
   }
   arrInfo += `] stack top is right!`;
   
   // 在頁面上展示
   document.body.innerHTML += `${arrInfo}<br /><br /> `;
   
   return arrInfo;
   }
   }
   複製程式碼

6. Main

   class Main {
   constructor() {
   this.alterLine('Stacks Comparison Area');
   let myStack = new MyStack();
   let myLinkedListStack = new MyLinkedListStack();
   let performanceTest = new PerformanceTest();
   
   let myStackInfo = performanceTest.testStack(myStack, 100000);
   let myLinkedListStackInfo = performanceTest.testStack(
   myLinkedListStack,
   100000
   );
   
   this.alterLine('MyStack Area');
   console.log(myStackInfo);
   this.show(myStackInfo);
   
   this.alterLine('MyLinkedListStack Area');
   console.log(myLinkedListStackInfo);
   this.show(myLinkedListStackInfo);
   }
   
   // 將內容顯示在頁面上
   show(content) {
   document.body.innerHTML += `${content}<br /><br />`;
   }
   
   // 展示分割線
   alterLine(title) {
   let line = `--------------------${title}----------------------`;
   console.log(line);
   document.body.innerHTML += `${line}<br /><br />`;
   }
   }
   class Student {
   constructor(studentName, studentScore) {
   this.name = studentName;
   this.score = studentScore;
   }
   
   toString() {
   let studentInfo = `Student(name: ${this.name}, score: ${this.score})`;
   return studentInfo;
   }
   }
   
   window.onload = function() {
   // 執行主函式
   new Main();
   };
   複製程式碼

使用連結串列來實現佇列

1. 對連結串列進行新增操作時

   O(n)
   O(1)
   O(n)
   

2. 對連結串列進行刪除操作時

   O(n)
   O(1)
   O(n)
   

3. 對連結串列進行查詢操作時

   O(n)
   O(1)
   O(n)
   

4. 佇列中的操作

   O(n)
   

5. 改進連結串列

   O(1)
   

6. 連結串列中不再有插入的功能所以不需要 dummyHead
   1. 但是由於沒有 dummyHead，所以需要注意連結串列為空的情況。
7. 讓自定義動態陣列佇列與自定義連結串列佇列進行對比
   1. 自定義動態陣列佇列的效能最差
   2. 自定義動態陣列迴圈佇列與自定義連結串列佇列的效能相近。
8. 與連結串列相關的有一個非常重要的內容
   1. 就是遞迴，因為連結串列本身具有天然的遞迴性質，
   2. 同時它又是一種非常簡單的資料結構，
   3. 所以連結串列是一種非常好的
   4. 研究學習遞迴的邏輯機制的的資料結構。