什么是數(shù)據(jù)結構？

數(shù)據(jù)結構就是計算機存儲和組織數(shù)據(jù)的方式

• 基本用途：組織數(shù)據(jù)
• 常見操作：插入、刪除、排序、搜索、遍歷等
• 不同的數(shù)據(jù)結構，適合解決不同的問題

每種結構要了解什么知識點

• 用途與定義 eg. HashSet可以用來查看
• 常見功能及復雜度 eg. BST查找元素復雜度O(log(N))
• 實現(xiàn)原理 e.g. HashMap的沖突解決策略: Linear Probing / Separate Chaining
• 注意事項 e.g. 翻轉(zhuǎn)鏈表(Iterative/Recursive)
• 語言細節(jié) e.g. Java中heap是用什么class實現(xiàn)的?

Big O

一種算法有多“快”?
某種數(shù)據(jù)結構或算法所支持的操作,有其時間、空間上的“效率 “。我們用時間/空間復雜度這個概念來衡量它。
時間復雜度,是指算法運行時間與輸入數(shù)據(jù)量的函數(shù)關系,常用 大寫字母O表示,讀作Big Oh。
類似地,空間復雜度,是指算法運行空間與輸入數(shù)據(jù)量的函數(shù)關 系。
復雜度不僅有Big O一種表達方式,Big O最常見。 詳參《算法導論》

常見時間復雜度種類

1. O(1) 表明算法運行時間不隨輸入數(shù)據(jù)量增長而變化,一直保持恒定。 e.g. HashSet/HashMap的contains(E elem)方法
2. O(N)
   表明算法運行時間與輸入數(shù)據(jù)量增長呈線性相關。 e.g. Unordered Array的查找。
3. O(logN)
   表明算法運行時間與輸入數(shù)據(jù)量增長呈對數(shù)關系:k^x = N。
   e.g. Heap的pop操作。該復雜度常見于平衡的樹結構操作或二分查找,即“一次去掉一半“。
4. O(N^2) 表明算法運行時間與輸入數(shù)據(jù)量增長呈平方(Quadratic)關系。 e.g. for...for...; Bubble Sort
   5. O(NlogN)
   通常出現(xiàn)于O(log N)操作執(zhí)行了N次,或O(N)操作執(zhí)行了log N次。 e.g. HeapSort, MergeSort
5. O(2^N)
   較低效,應當盡力避免。
   e.g. 斐波那契數(shù)列的遞歸實現(xiàn)。

public int Fibonacci(n) {
    if (n == 1 || n == 2)
        return 1;
    if (n > 2)
return Fibonacci(n-1) + Fibonacci(n-2);
}

7. O(N!) 比指數(shù)時間更低效,應當避免。 e.g. Permutation

Big O 注意事項

1. BigO表示函數(shù)關系,是相對量,不是絕對量
   e.g. 時間復雜度數(shù)量級小,不等于絕對速度在任何情況下都更快,只表明運行時間隨
   輸入數(shù)據(jù)量的變化速度較慢或不變。
2. 只取變化量最大的關系,省略其他
   e.g. O(N^2 + 2*N)等同于O(N^2)
3. 通常取最壞情況
   e.g. 假設在隊列頭部插入,而非中部或尾部
   e.g. 平均情況? “一般是在哪里插入”
4. O(N!)比指數(shù)復雜度更低效

線性結構

Array

數(shù)組是一種按照線性的順序來組織固定數(shù)量 (fixed amount)的數(shù)據(jù)的數(shù)據(jù)結構。
數(shù)組所儲存的單個數(shù)據(jù)稱為數(shù)組的元素（element）
Java中,Array只能裝一種元素,但可以是primary type,也可以 是object。
注意事項：

1. Fixed size, not dynamic
   注意防止溢出
2. No holes：無洞性
   刪除后必須把后面的元素向前移，插入同理
   復雜度
   | Tables | Are | Cool |
   | ------------- |:-------------:| -----:|
   | col 3 is | right-aligned | $1600 |
   | col 2 is | centered | $12 |
   | zebra stripes | are neat | $1 |

ArrayList

Dynamic array 既能完成數(shù)組線性儲存、管理、常數(shù)時間 內(nèi)定位數(shù)據(jù)的功能,又可以自動調(diào)整數(shù)組長度。
Java中,這一功能由ArrayList來實現(xiàn)。

復雜度

復雜度同Array，不同點是支持動態(tài)插入刪除

擴容公式

New Capacity = max(新arraylist的最小長度,原 arraylist的size * 2)

LinkedList

只要有插入/刪除點的引用(指針),即可實現(xiàn)O(1)插入/刪除

復雜度

經(jīng)典題目：翻轉(zhuǎn)鏈表

public ListNode reverseList(ListNode head) {
     if (head == null || head.next == null) return head;
     ListNode prev = null, cur = head;
     ListNode next;
     while (cur != null) {
          next = cur.next;
          cur.next = prev;
          prev = cur;
          cur = next; }
     return prev;
}

Java鏈表為雙向鏈表，實現(xiàn)類？

Stack

棧（Stack）是一種以O(1)復雜度實現(xiàn)LIFO(Last In First Out)功能的線性數(shù)據(jù)結構

Queue

隊列（Queue）是一種以O(1)復雜度實現(xiàn)LIFO(First In Last Out)功能的線性數(shù)據(jù)結構

Java中，Queue是一個接口,有多種實現(xiàn)。 常用的初始化方式:
1.LinkedList
2.PriorityQueue(見Heap)

經(jīng)典題目

1.用Stack實現(xiàn)Queue
2.用Queue實現(xiàn)Stack

Tree

樹是節(jié)點(node)的集合。這些節(jié)點用父子關系來儲存元素，其中：根節(jié)點沒有父節(jié)點,其他節(jié)點有且只有一個父節(jié)點。
樹的結構越接近一個鏈條，各操作就越接近線性結構，就失去了樹結構的優(yōu)勢。
常見二叉樹:二叉搜索樹(Binary Search Tree，BST) 常見多叉樹:字典樹(Trie Tree，通常為26叉樹）

二叉搜索樹(Binary Search Tree)

二叉搜索樹是一種二叉樹,能夠按順序組織元素。 滿足以下條件:

1. 每一個節(jié)點的左子樹中的元素,比這個節(jié)點的 元素小,或與它相等。
2. 每一個節(jié)點的右子樹中的元素,比這個節(jié)點的 元素大,或與它相等。
   進行In-Order Traversal時,順序從小到大。
   BST適合用來對元素排序,或維護元素順序。 大多數(shù)關于樹的常見面試題目與二叉搜索樹有關。

二叉搜索樹可分為平衡樹(Balanced Tree)與非平衡樹。 “平衡”指樹形相對“扁平”。如AVL樹:父節(jié)點的左右子樹均為平衡樹,且高度 之差<=1。
“自平衡樹”:時刻維持樹的平衡。不同自平衡樹有不同的自平衡策略。AVL是一種常見的自平衡二叉查找樹，當AVL檢測到不平衡的狀況出現(xiàn)，它會旋轉(zhuǎn)樹節(jié)點，使得樹重新平衡。
為何要區(qū)分平衡樹與非平衡樹? 為保證插入、刪除、搜索的最壞時間復雜度不高于O(log N)
AVL平衡二叉樹,插入、刪除、搜索時間復雜度為O(logN)，遍歷為O(N)
樹的遍歷：
1.Depth-First Search
1.Breath-First Search
二叉樹題目總結

AVL tree VS Red-Black Tree
The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree.
Red-Black Tree

Graph

“圖”(Graph):節(jié)點的集合 + 連接這些節(jié)點的邊的集合。 在圖論中,樹(Tree)是一種無向圖(Undirected Graph),其中任意兩個頂點間存在唯一一條路徑?；蛘哒f,只要沒有環(huán)(cycle)的連通圖(亦即沒有島island)就是樹。

Heap

Heap是一種邏輯結構為樹形，物理結構為線性的數(shù)據(jù)結構,它的主要功能是維護及提供最小或最大元素(依此分為最小堆和最大堆)。

• 近完全的樹形結構(almost complete Tree):除最后一層外,每層都維持“滿節(jié) 點”狀態(tài)。添加元素時,從左到右依次添 加。
• 根節(jié)點存放最小(或最大)元素。

• 對每個節(jié)點而言,其子節(jié)點的元素值都比自己小(或大)。

  
  
  image.png

物理結構

為什么說Heap的物理結構是線性的？

image.png

[0,99,13,81,1,12,78]
1.對于任意一個index為k的節(jié)點:

• 其父節(jié)點的index:k/2
• 其左孩子的index:2*k
• 其右孩子的index:2*k+1
  2.index為0的位置要空出來

建堆

逐個offer法 O(NlogN)
逐層掃描法 O(N)

重點

1. 用途是維護和提供最大最小值,但不負責完整排序。
2. 物理線性,邏輯樹形(近完全樹)。
3. 兩個操作:彈出最值和加入新元素,復
   雜度都是O(log N)。
4. 建堆時間可以優(yōu)化到O(N)。
5. 非葉節(jié)點index:1 - n/2。
6. Java中可直接調(diào)用PriorityQueue類使用其功能。

Set/Map

沖突問題（Collision）

不同的key形成了同一個hash碼
為何會有沖突問題

• 哈希函數(shù)的特性。e.g.“均勻哈希函數(shù)”(Uniform Hash function)
• 存儲位置比較少
  沖突問題如何解決?

1. Separate Chaining（鏈接法）

• 以每個bucket內(nèi)的Entry object為head node,將不同的entry連綴起來形成 LinkedList。（即每個bucket是一個鏈表，可以動態(tài)增刪）
• 插入時,查找一遍已存在的LinkedList,如果有相同的key則更新其value;如果沒有, 則插入到bucket首位。
• 刪除、查找時同理。

2. Linear Probing（線性探查）

定義

Map是一種為“Key-value pair” 提供存儲、查找、替換、遍歷等功能的數(shù)據(jù)結構。

實現(xiàn)方式

Map interface

• HashMap is implemented as a hash table, and there is no ordering on keys or values.
• TreeMap is implemented based on red-black tree structure, and it is ordered by the key.
• LinkedHashMap preserves the insertion order
• Hashtable is synchronized, in contrast to HashMap. It has an overhead for synchronization.
• This is the reason that HashMap should be used if the program is thread-safe.

參考：四種基本實現(xiàn)
根據(jù)常見實現(xiàn)方式可以分為: HashMap, TreeMap, LinkedHashMap

• LinkeHashMap: HashMap + LinkedList, 可以保存輸入的順序
  Application: LRU Cache
• TreeMap：HashMap + 紅黑樹(自平衡的BST)，可以針對可排序的key進行排序，key為自定義對象是必須實現(xiàn)Comparable接口
• HashTable：The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. HashTable的所有接口都是synchronized
• HashMap提供了最快的查找技術，也沒有按照任何明顯的順序來保存元素。TreeMap按照比較結果的升序保存鍵，而LinkedHashMap則按照插入順序保存鍵，同時還保留了HashMap的查詢速度。
  如果Map的key是自定義對象，需要自己實現(xiàn)equals() 和 hashCode()，否則會使用默認的equals() 和 hashCode()

The default hashCode() method gives distinct integers for distinct objects, and the equals() method only returns true when two references refer to the same object.

Set(集合)

主要用途: 查找(查重)

實現(xiàn)方式

根據(jù)實現(xiàn)方式也分為: HashSet, TreeSet，LinkedHashSet
HashSet提供了最快的查找技術，存儲的順序沒有實際的意義。TreeMap按照比較結果的升序保存對象，而LinkedHashMap則按照插入順序保存對象。
底層結構:

1. 用一個HashMap來實現(xiàn),但value部 分用dummy object,只保留key
2. 存儲和查找原理與HashMap完全一致
3. 如果重復,和HashMap一樣會替換,但因為value都是dummy