【資料結構】各種資料結構的簡單特點

                                          各種資料結構的簡單特點

1、清單

包括

（1）數組

【1】會在記憶體中開辟一個連續的記憶體空間

【2】随機通路的效率比連結清單高。數組隻要給定下标，則可以直接定位到該下标所對應的元素，而連結清單每次都是從頭節點開始周遊。

【3】對元素的增删操作的效率比連結清單低。這裡說的是從數組的中間插入或删除一個元素，并且數組中元素很多，實驗證明，在數組頭部或結尾增加或删除一個元素的效率和連結清單差不多。

為什麼？

比如，每次對數組中間某一個元素進行删除的操作，則此元素後面的所有元素都得往前面移動，耗費大量的時間和性能。

而對連結清單中間某一個元素進行删除的操作，隻需将此節點的指針與前驅結點和後繼節點斷開即可，元素并沒有發生移動。

這個特點，可以解釋ArrayList與LinkedList之間的差別

（2）連結清單

【1】通過一個個指針将節點串起來

【2】對于元素的随機通路，需要使用計數器來通路指定的元素，并且隻能從頭節點開始通路，每通路一個節點，計數器加1，直到給定的“下标”，此操作很耗時，時間複雜度為O(N)

【3】增加元素和删除元素的效率很高

（3）隊列

【1】不支援随機通路

【2】先進先出

【3】線程池中的線程就是從任務隊列中取出任務

（4）棧

【1】不支援随機通路

【2】後進先出

2、樹

（1）二叉樹

【1】每個節點最多隻有兩個子節點

（2）搜尋樹

【1】二分查找，數組對半分的路徑就是一個搜尋樹

【2】不一定是二叉樹

（3）堆/優先隊列

【1】按照順序pop出元素

【2】優先隊列中，以最小堆為例，樹或子樹根結點都是所在樹或子樹中最小的元素

3、棧、隊列、優先隊列中的元素彈出順序

例 push(1)   push(3)   push(2)  pop()    pop()   pop()

（1）棧 

彈出順序為 2，3，1   【後進先出】

（2）隊列

彈出順序為 1，3，2   【先進先出】

（2）優先隊列

彈出順序為 1，2，3   【從小到大，具有順序性】

4、Map<K,V>和Set<K>接口

（1） HashMap/HashSet

【1】都基于哈希表的實作

【2】每個Object都有一個哈希值，上面兩者實作類都基于這個哈希值

HashSet如何區分待插入元素重複？

先得到這個元素的hashCode，若HashSet中不存在此hashCode對應的元素，則直接将此元素插入到HashSet中

若HashSet中存在此hashCode對應的元素，将這些元素拿出來與待插入元素進行equals判斷，若全相等，則不插入，否則插入

（2）TreeMap/TreeSet 

【1】K必須實作Comparable接口

【2】K被放入樹中

5、圖

（1）無向圖

【1】每個節點都沒有方向，邊上可能有權重

（2）有向圖

【1】每個節點是有方向的的

（3）有向無環圖

【1】可以描述任務之間的關系