摘要：單鏈表與雙向鏈表單鏈表是表示一系列節點的數據結構，其中每個節點指向列表中的下一個節點。且分別稱為該結點的左子樹與右子樹。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

1. 什么是數據結構？

數據結構是在計算機中組織和存儲數據的一種特殊方式，使得數據可以高效地被訪問和修改。更確切地說，數據結構是數據值的集合，表示數據之間的關系，也包括了作用在數據上的函數或操作。

1.1 為什么我們需要數據結構？

數據是計算機科學當中最關鍵的實體，而數據結構則可以將數據以某種組織形式存儲，因此，數據結構的價值不言而喻。

無論你以何種方式解決何種問題，你都需要處理數據——無論是涉及員工薪水、股票價格、購物清單，還是只是簡單的電話簿問題。

數據需要根據不同的場景，按照特定的格式進行存儲。有很多數據結構能夠滿足以不同格式存儲數據的需求。

1.2 八大常見的數據結構

數組：Array

堆棧：Stack

隊列：Queue

鏈表：Linked Lists

樹：Trees

圖：Graphs

字典樹：Trie

散列表（哈希表）：Hash Tables

在較高的層次上，基本上有三種類型的數據結構:

堆棧和隊列是類似于數組的結構，僅在項目的插入和刪除方式上有所不同。

鏈表，樹，和圖 結構的節點是引用到其他節點。

散列表依賴于散列函數來保存和定位數據。

在復雜性方面：

堆棧和隊列是最簡單的，并且可以從中構建鏈表。

樹和圖 是最復雜的，因為它們擴展了鏈表的概念。

散列表和字典樹 需要利用這些數據結構來可靠地執行。

就效率而已：

鏈表是記錄和存儲數據的最佳選擇

而哈希表和字典樹 在搜索和檢索數據方面效果最佳。

2. 數組 - 知識補充

數組是最簡單的數據結構，這里就不講過多了。 貼一張每個函數都運行10,000次迭代：

10,000個隨機密鑰在10,000個對象的數組中查找的執行效率對比圖：

[
  {
    id: "key0",
    content: "I ate pizza 0 times"
  },
  {
    id: "key1",
    content: "I ate pizza 1 times"
  },
  {
    id: "key2",
    content: "I ate pizza 2 times"
  },
  ...
]

["key284", "key958", "key23", "key625", "key83", "key9", ... ]

2.1 for... in為何這么慢？

for... in語法令人難以置信的緩慢。在測試中就已經比正常情況下慢近9倍的循環。

這是因為for ... in語法是第一個能夠迭代對象鍵的JavaScript語句。

循環對象鍵（{}）與在數組（[]）上進行循環不同，

因為引擎會執行一些額外的工作來跟蹤已經迭代的屬性。

3. 堆棧：Stack

瀏覽器歷史記錄

撤消操作

遞歸以及其它。

三句話解釋堆棧：

兩個原則操作：push和pop。Push 將元素添加到數組的頂部，而Pop將它們從同一位置刪除。

遵循"Last In，First Out"，即：LIFO，后進先出。

沒了。

3.1 堆棧的實現。

請注意，下方例子中，我們可以顛倒堆棧的順序：底部變為頂部，頂部變為底部。

因此，我們可以分別使用數組unshift和shift方法代替push和pop。

class Stack {
    constructor(...items) {
        this.reverse = false;
        this.stack = [...items];
    }

    push(...items) {
        return this.reverse
            ");
4. 隊列：Queue
在計算機科學中，一個隊列(queue)是一種特殊類型的抽象數據類型或集合。集合中的實體按順序保存。

而在前端開發中，最著名的隊列使用當屬瀏覽器/NodeJs中 關于宏任務與微任務，任務隊列的知識。這里就不再贅述了。

在后端領域，用得最廣泛的就是消息隊列：Message queue：如RabbitMQ、ActiveMQ等。
以編程思想而言，Queue可以用兩句話描述：

只是具有兩個主要操作的數組：unshift和pop。
遵循"Fist In，first out"即：FIFO，先進先出。


4.1 隊列的實現
請注意，下方例子中，我們可以顛倒堆隊列的順序。
因此，我們可以分別使用數組unshift和shift方法代替push和pop。
class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ");
5. 鏈表：Linked Lists
與數組一樣，鏈表是按順序存儲數據元素。
鏈表不是保留索引，而是指向其他元素。

第一個節點稱為頭部(head)，而最后一個節點稱為尾部(tail)。

單鏈表與雙向鏈表：

單鏈表是表示一系列節點的數據結構，其中每個節點指向列表中的下一個節點。
鏈表通常需要遍歷整個操作列表，因此性能較差。
提高鏈表性能的一種方法是在每個節點上添加指向列表中上一個節點的第二個指針。
雙向鏈表具有指向其前后元素的節點。

鏈表的優點：

鏈接具有常量時間 插入和刪除，因為我們可以只更改指針。
與數組一樣，鏈表可以作為堆棧運行。

鏈表的應用場景：
鏈接列表在客戶端和服務器上都很有用。

在客戶端上，像Redux就以鏈表方式構建其中的邏輯。
React 核心算法 React Fiber的實現就是鏈表。





React Fiber之前的Stack Reconciler，是自頂向下的遞歸mount/update，無法中斷(持續占用主線程)，這樣主線程上的布局、動畫等周期性任務以及交互響應就無法立即得到處理，影響體驗。




React Fiber解決過去Reconciler存在的問題的思路是把渲染/更新過程(遞歸diff)拆分成一系列小任務，每次檢查樹上的一小部分，做完看是否還有時間繼續下一個任務，有的話繼續，沒有的話把自己掛起，主線程不忙的時候再繼續。


在服務器上，像Express這樣的Web框架也以類似的方式構建其中間件邏輯。當請求被接收時，它從一個中間件管道輸送到下一個，直到響應被發出。

5.1 單鏈表實現
單鏈表的操作核心有：

push（value） - 在鏈表的末尾/頭部添加一個節點
pop（） - 從鏈表的末尾/頭部刪除一個節點
get（index） - 返回指定索引處的節點
delete（index） - 刪除指定索引處的節點
isEmpty（） - 根據列表長度返回true或false
print（） - 返回鏈表的可見表示

class Node {
  constructor(data) {
    this.data = data
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    // 長度非必要
    this.length = 0
  }
  push(data) {
    // 創建一個新節點
    const node = new Node(data)
    // 檢查頭部是否為空
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
    // 先檢查鏈表是否為空
    if(this.isEmpty()) {
      return null
    } 
    // 如果長度為1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate
    
    while (currentNode) {
      if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }
    
    penultimate.next = null
    this.tail = penultimate
    this.length --
    return node
  }
  
  get(index){
    // 處理邊界條件
    if (index === 0) {
      return this.head
    }
    if (index < 0 || index > this.length) {
      return null
    }
    
    let currentNode = this.head
    let i = 0
    while(i < index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode
    
  }
  delete(index){
    let currentNode = this.head
    
    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--
      
      return deletedNode
    }
    
    if (index < 0 || index > this.length) {
      return null
    }
    
    let i = 0
    let previous
    
    while(i < index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }
  
  isEmpty() {
    return this.length === 0
  }
  print() {
    const list = []
    let currentNode = this.head
    while(currentNode){
      list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join(" => ")
  }
}
測試一下：
const l = new LinkedList()

// 添加節點
const values = ["A", "B", "C"]
values.forEach(value => l.push(value))

console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())

5.2 雙向鏈表實現
1. 雙向鏈表的設計
類似于單鏈表，雙向鏈表由一系列節點組成。每個節點包含一些數據以及指向列表中下一個節點的指針和指向前一個節點的指針。這是JavaScript中的簡單表示：
class Node {
    constructor(data) {
        // data 包含鏈表項應存儲的值
        this.data = data;
        // next 是指向列表中下一項的指針
        this.next = null;
        // prev 是指向列表中上一項的指針
        this.prev = null;
    }
}

還是敲一遍吧：

class DoublyLinkedList {
    constructor() {
    	this.head = null;
        this.tail = null;
    }
    // 各種操作方法
    // ...
}
2. 雙向鏈表的操作方法


Append & AppendAt: 在鏈表的尾部/ 指定位置添加節點

append( item ) {
  let node = new Node( item );
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node
  }
}

appendAt( pos, item ) {
   let current = this.head;
   let counter = 1;
   let node = new Node( item );
   if( pos == 0 ) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } else {
     while(current) {
      current = current.next;
      if( counter == pos ) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}


Remove & RemoveAt: 在鏈表的尾部/ 指定位置刪除節點

remove( item ) {
  let current = this.head;
  while( current ) {
    if( current.data === item ) {
      if( current == this.head && current == this.tail ) {
        this.head = null;
        this.tail = null;
      } else if ( current == this.head ) {
        this.head = this.head.next
        this.head.prev = null
      } else if ( current == this.tail ) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

removeAt( pos ) {
  let current = this.head;
  let counter = 1;
  if( pos == 0 ) {
   this.head = this.head.next;
   this.head.prev = null;
  } else {
   while( current ) {
    current = current.next
    if ( current == this.tail ) {
     this.tail = this.tail.prev;
     this.tail.next = null;
    } else if( counter == pos ) {
     current.prev.next = current.next;
     current.next.prev = current.prev;
     break;
    }
    counter++;
   }
  }
}


Reverse: 翻轉雙向鏈表

reverse(){
  let current = this.head;
  let prev = null;
  while( current ){
   let next = current.next
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}



Swap：兩節點間交換。

swap( nodeOne, nodeTwo ) {
   let current = this.head;
   let counter = 0;
   let firstNode;
   while( current !== null ) {
     if( counter == nodeOne ){
       firstNode = current;
     } else if( counter == nodeTwo ) {
       let temp = current.data;
       current.data = firstNode.data;
       firstNode.data = temp;
     }
     current = current.next;
     counter++;
   }
   return true
}


IsEmpty & Length：查詢是否為空或長度。

length() {
  let current = this.head;
  let counter = 0;
  while( current !== null ) {
   counter++
   current = current.next
  }
  return counter;
}
isEmpty() {
  return this.length() < 1
}


Traverse: 遍歷鏈表

traverse( fn ) {
   let current = this.head;
   while( current !== null ) {
    fn(current)
    current = current.next;
   }
   return true;
}

每一項都加10

Search：查找節點的索引。

search( item ) {
  let current = this.head;
  let counter = 0;
  while( current ) {
    if( current.data == item ) {
     return counter
    }
    current = current.next
    counter++
  }
  return false;
}

6. 樹：Tree
計算機中經常用到的一種非線性的數據結構——樹（Tree），由于其存儲的所有元素之間具有明顯的層次特性，因此常被用來存儲具有層級關系的數據，比如文件系統中的文件；也會被用來存儲有序列表等。

在樹結構中，每一個結點只有一個父結點，若一個結點無父節點，則稱為樹的根結點，簡稱樹的根（root）。
每一個結點可以有多個子結點。
沒有子結點的結點稱為葉子結點。
一個結點所擁有的子結點的個數稱為該結點的度。
所有結點中最大的度稱為樹的度。樹的最大層次稱為樹的深度。

6.1 樹的分類
常見的樹分類如下，其中我們掌握二叉搜索樹即可。

二叉樹：Binary Search Tree
AVL樹：AVL Tree
紅黑樹：Red-Black Tree
線段樹： Segment Tree - with min/max/sum range queries examples
芬威克樹：Fenwick Tree (Binary Indexed Tree)

6.2 樹的應用

DOM樹。每個網頁都有一個樹數據結構。


2. Vue和React的Virtual DOM也是樹。

6.3 二叉樹：Binary Search Tree

二叉樹是一種特殊的樹，它的子節點個數不超過兩個。
且分別稱為該結點的左子樹（left subtree）與右子樹（right subtree）。
二叉樹常被用作二叉查找樹和二叉搜索樹、或是二叉排序樹（BST）。


6.4 二叉樹的遍歷
按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次，這個操作被稱為樹的遍歷，是對樹的一種最基本的運算。
由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。
按照根節點訪問的順序不同，二叉樹的遍歷分為以下三種：前序遍歷，中序遍歷，后序遍歷；
前序遍歷：Pre-Order
根節點->左子樹->右子樹


中序遍歷：In-Order
左子樹->根節點->右子樹


后序遍歷：Post-Order
左子樹->右子樹->根節點


因此我們可以得之上面二叉樹的遍歷結果如下：

前序遍歷：ABDEFGC
中序遍歷：DEBGFAC
后序遍歷：EDGFBCA

6.5 二叉樹的實現
class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = data
  } 
} 

class BST {
    constructor() {
        this.root = null
    }
    // 二叉樹的各種操作
    // insert(value) {...}
    // insertNode(root, newNode) {...}
    // ...
1. insertNode& insert：插入新子節點/節點
  insertNode(root, newNode) {
    if (newNode.value < root.value) {
      // 先執行無左節點操作
      (!root.left) ");
2. removeNode& remove：移除子節點/節點
  removeNode(root, value) {
    if (!root) {
      return null
    }
    
    // 從該值小于根節點開始判斷
    if (value < root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 如果沒有左右節點
      if (!root.left && !root.right) {
        root = null
        return root
      }
      
      // 存在左節點
      if (root.left) {
        root = root.left
        return root
      // 存在右節點
      } else if (root.right) {
        root = root.right
        return root
      }
      
      // 獲取正確子節點的最小值以確保我們有有效的替換
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      // 確保刪除已替換的節點
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }
  
remove(value) {
    if (!this.root) {
      return "Tree is empty!"
    } else {
      this.removeNode(this.root, value)
    }
}
  
3. findMinNode:獲取子節點的最小值
findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}
4. searchNode & search：查找子節點/節點
searchNode(root, value) {
    if (!root) {
      return null
    }
    
    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    }
    
    return root
}

search(value) {
    if (!this.root) {
      return "Tree is empty"
    } else {
      return Boolean(this.searchNode(this.root, value))
    }
}

Pre-Order：前序遍歷

preOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }

In-Order：中序遍歷

inOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }

Post-Order：后序遍歷

postOrder(root) {
    if (!root) {
      return "Tree is empty"
    } else {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}
7. 圖：Graph
圖是由具有邊的節點集合組成的數據結構。圖可以是定向的或不定向的。
圖的介紹普及，找了一圈文章，還是這篇最佳：
Graphs—-A Visual Introduction for Beginners


7.1 圖的應用
在以下場景中，你都使用到了圖：

使用搜索服務，如Google，百度。
使用LBS地圖服務，如高德，谷歌地圖。
使用社交媒體網站，如微博，Facebook。


圖用于不同的行業和領域：

GPS系統和谷歌地圖使用圖表來查找從一個目的地到另一個目的地的最短路徑。
社交網絡使用圖表來表示用戶之間的連接。
Google搜索算法使用圖 來確定搜索結果的相關性。
運營研究是一個使用圖 來尋找降低運輸和交付貨物和服務成本的最佳途徑的領域。
甚至化學使用圖 來表示分子！

圖，可以說是應用最廣泛的數據結構之一，真實場景中處處有圖。
7.2 圖的構成
圖表用于表示，查找，分析和優化元素（房屋，機場，位置，用戶，文章等）之間的連接。

1. 圖的基本元素

節點：Node，比如地鐵站中某個站/多個村莊中的某個村莊/互聯網中的某臺主機/人際關系中的人.
邊：Edge，比如地鐵站中兩個站點之間的直接連線, 就是一個邊。


2. 符號和術語


|V|=圖中頂點（節點）的總數。


|E|=圖中的連接總數（邊）。


在下面的示例中
|V| = 6 
|E| = 7 

3. 有向圖與無向圖
圖根據其邊（連接）的特征進行分類。
1. 有向圖
在有向圖中，邊具有方向。它們從一個節點轉到另一個節點，并且無法通過該邊返回到初始節點。
如下圖所示，邊（連接）現在具有指向特定方向的箭頭。 將這些邊視為單行道。您可以向一個方向前進并到達目的地，但是你無法通過同一條街道返回，因此您需要找到另一條路徑。

有向圖
2. 無向圖
在這種類型的圖中，邊是無向的（它們沒有特定的方向）。將無向邊視為雙向街道。您可以從一個節點轉到另一個節點并返回相同的“路徑”。

4. 加權圖
在加權圖中，每條邊都有一個與之相關的值（稱為權重）。該值用于表示它們連接的節點之間的某種可量化關系。例如：

權重可以表示距離，時間，社交網絡中兩個用戶之間共享的連接數。
或者可以用于描述您正在使用的上下文中的節點之間的連接的任何內容。


著名的Dijkstra算法，就是使用這些權重通過查找網絡中節點之間的最短或最優的路徑來優化路由。
5. 稀疏圖與密集圖
當圖中的邊數接近最大邊數時，圖是密集的。

密集圖
當圖中的邊數明顯少于最大邊數時，圖是稀疏的。

稀疏圖
6. 循環
如果你按照圖中的一系列連接，可能會找到一條路徑，將你帶回到同一節點。這就像“走在圈子里”，就像你在城市周圍開車一樣，你走的路可以帶你回到你的初始位置。