什么是數(shù)據(jù)結(jié)構(gòu)翰蠢？

數(shù)據(jù)結(jié)構(gòu)就是計(jì)算機(jī)存儲(chǔ)和組織數(shù)據(jù)的方式

• 基本用途：組織數(shù)據(jù)
• 常見操作：插入屎篱、刪除服赎、排序、搜索交播、遍歷等
• 不同的數(shù)據(jù)結(jié)構(gòu)重虑，適合解決不同的問題

每種結(jié)構(gòu)要了解什么知識(shí)點(diǎn)

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

Big O

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

常見時(shí)間復(fù)雜度種類

1. O(1) 表明算法運(yùn)行時(shí)間不隨輸入數(shù)據(jù)量增長(zhǎng)而變化,一直保持恒定乏梁。 e.g. HashSet/HashMap的contains(E elem)方法
2. O(N)
   表明算法運(yùn)行時(shí)間與輸入數(shù)據(jù)量增長(zhǎng)呈線性相關(guān)次洼。 e.g. Unordered Array的查找。
3. O(logN)
   表明算法運(yùn)行時(shí)間與輸入數(shù)據(jù)量增長(zhǎng)呈對(duì)數(shù)關(guān)系:k^x = N遇骑。
   e.g. Heap的pop操作卖毁。該復(fù)雜度常見于平衡的樹結(jié)構(gòu)操作或二分查找,即“一次去掉一半“。
4. O(N^2) 表明算法運(yùn)行時(shí)間與輸入數(shù)據(jù)量增長(zhǎng)呈平方(Quadratic)關(guān)系。 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)
   較低效,應(yīng)當(dāng)盡力避免炭剪。
   e.g. 斐波那契數(shù)列的遞歸實(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ù)時(shí)間更低效,應(yīng)當(dāng)避免翔脱。 e.g. Permutation

Big O 注意事項(xiàng)

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

線性結(jié)構(gòu)

Array

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

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

ArrayList

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

復(fù)雜度

復(fù)雜度同Array亮蛔，不同點(diǎn)是支持動(dòng)態(tài)插入刪除

擴(kuò)容公式

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

LinkedList

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

復(fù)雜度

經(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鏈表為雙向鏈表痴施，實(shí)現(xiàn)類？

Stack

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

Queue

隊(duì)列（Queue）是一種以O(shè)(1)復(fù)雜度實(shí)現(xiàn)LIFO(First In Last Out)功能的線性數(shù)據(jù)結(jié)構(gòu)

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

經(jīng)典題目

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

Tree

樹是節(jié)點(diǎn)(node)的集合。這些節(jié)點(diǎn)用父子關(guān)系來儲(chǔ)存元素梯嗽，其中：根節(jié)點(diǎn)沒有父節(jié)點(diǎn),其他節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)齿尽。
樹的結(jié)構(gòu)越接近一個(gè)鏈條，各操作就越接近線性結(jié)構(gòu)灯节，就失去了樹結(jié)構(gòu)的優(yōu)勢(shì)循头。
常見二叉樹:二叉搜索樹(Binary Search Tree，BST) 常見多叉樹:字典樹(Trie Tree炎疆，通常為26叉樹）

二叉搜索樹(Binary Search Tree)

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

1. 每一個(gè)節(jié)點(diǎn)的左子樹中的元素,比這個(gè)節(jié)點(diǎn)的 元素小,或與它相等。
2. 每一個(gè)節(jié)點(diǎn)的右子樹中的元素,比這個(gè)節(jié)點(diǎn)的 元素大,或與它相等形入。
   進(jìn)行In-Order Traversal時(shí),順序從小到大全跨。
   BST適合用來對(duì)元素排序,或維護(hù)元素順序。 大多數(shù)關(guān)于樹的常見面試題目與二叉搜索樹有關(guān)亿遂。

二叉搜索樹可分為平衡樹(Balanced Tree)與非平衡樹浓若。 “平衡”指樹形相對(duì)“扁平”。如AVL樹:父節(jié)點(diǎn)的左右子樹均為平衡樹,且高度 之差<=1蛇数。
“自平衡樹”:時(shí)刻維持樹的平衡挪钓。不同自平衡樹有不同的自平衡策略。AVL是一種常見的自平衡二叉查找樹耳舅，當(dāng)AVL檢測(cè)到不平衡的狀況出現(xiàn)碌上，它會(huì)旋轉(zhuǎn)樹節(jié)點(diǎn)，使得樹重新平衡。
為何要區(qū)分平衡樹與非平衡樹? 為保證插入馏予、刪除天梧、搜索的最壞時(shí)間復(fù)雜度不高于O(log N)
AVL平衡二叉樹,插入、刪除霞丧、搜索時(shí)間復(fù)雜度為O(logN)呢岗，遍歷為O(N)
樹的遍歷：
1.Depth-First Search
1.Breath-First Search
二叉樹題目總結(jié)

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é)點(diǎn)的集合 + 連接這些節(jié)點(diǎn)的邊的集合。 在圖論中,樹(Tree)是一種無向圖(Undirected Graph),其中任意兩個(gè)頂點(diǎn)間存在唯一一條路徑蚯妇》罅牵或者說,只要沒有環(huán)(cycle)的連通圖(亦即沒有島island)就是樹。

Heap

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

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

• 對(duì)每個(gè)節(jié)點(diǎn)而言,其子節(jié)點(diǎn)的元素值都比自己小(或大)。

  
  
  image.png

物理結(jié)構(gòu)

為什么說Heap的物理結(jié)構(gòu)是線性的务漩？

image.png

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

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

建堆

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

重點(diǎn)

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

Set/Map

沖突問題（Collision）

不同的key形成了同一個(gè)hash碼
為何會(huì)有沖突問題

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

1. Separate Chaining（鏈接法）

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

2. Linear Probing（線性探查）

定義

Map是一種為“Key-value pair” 提供存儲(chǔ)祥楣、查找、替換汉柒、遍歷等功能的數(shù)據(jù)結(jié)構(gòu)误褪。

實(shí)現(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.

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

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

主要用途: 查找(查重)

實(shí)現(xiàn)方式

根據(jù)實(shí)現(xiàn)方式也分為: HashSet, TreeSet，LinkedHashSet
HashSet提供了最快的查找技術(shù)问裕，存儲(chǔ)的順序沒有實(shí)際的意義逮壁。TreeMap按照比較結(jié)果的升序保存對(duì)象，而LinkedHashMap則按照插入順序保存對(duì)象粮宛。
底層結(jié)構(gòu):

1. 用一個(gè)HashMap來實(shí)現(xiàn),但value部 分用dummy object,只保留key
2. 存儲(chǔ)和查找原理與HashMap完全一致
3. 如果重復(fù),和HashMap一樣會(huì)替換,但因?yàn)関alue都是dummy