目錄
一、時空複雜度
二、資料結構分類圖
三、細分資料結構
1. 數組
2. 連結清單
3. 棧
4. 隊列
5. 散清單
6. 跳表
7. 樹
8. 圖
一、時空複雜度
小結：通常所說的時空複雜度分析其實是描述程式運作過程中所需要的時間與額外空間的一種度量方式并非真實所需要的時間與空間，是以也稱為漸近時間複雜度或漸近空間複雜度。
二、資料結構分類圖
總結： 通過上圖可以知道資料的以下幾個特點
- 資料結構的實體存儲方式通常隻有在記憶體空間中順序存儲或鍊式存儲兩種方式，而這兩種方式對應的資料結構分别為數組與連結清單。在一些資料中還看到實體結構中有散列存儲方式，其實仔細分析會發現散列存儲其實也是基于鍊式存儲與順序存儲的一種存儲方式。
- 資料結構中像棧、隊列、哈希表、跳表、圖、樹等都是通過數組或連結清單這兩種基本資料結構所衍生而來。例如哈希表通過數組+連結清單或者數組+連結清單+紅黑樹所衍生而來。
三、細分資料結構
1. 數組
概念：通過連續的記憶體空間來存儲一組相同類型的資料。
特點：數組最大的殺手锏是随機讀取。代價是需要預先配置設定連續的存儲空間與犧牲插入、删除操作的效率。
适用場景：讀多寫少。通過數組下标讀取時間複雜度O(1)，插入或删除操作為了保持記憶體空間的連續性需要移動資料，故時間複雜度為O(n)。
順序存儲如下圖紅色部分所示：
2. 連結清單
概念：通過鍊式存儲方式組織資料存儲于記憶體中的一種線性表資料結構。
特點：通過指針的方式靈活地在記憶體中組織資料，其與數組最大的差別是不需要預先在記憶體中開辟整塊連續的記憶體空間進行存儲，這個特點也使得連結清單在無需複制資料的情況下支援自動擴容。代價是讀隻能是周遊的方式進行讀取。
常見的連結清單有：單連結清單、雙連結清單、循環單連結清單、循環雙連結清單。
适用場景：讀少寫多。連結清單讀需要周遊，時間複雜度為O(n)，更新因為不需要移動資料隻需要更新對應節點的指向指針，時間複雜度為O(1)。
鍊式存儲如下所示：
3. 棧
概念：棧是一種邏輯結構，隻支援FILO。
特點：隻有簡單的入棧Push操作與出棧Pop操作。由于棧的入棧操作與出棧操作都是沒有産生資料的移動，是以其時間複雜度都為O(1)。
類别：通過數組實作的棧稱為順序棧，連結清單實作的稱為連結清單棧。
适用場景：
- 1. 不想對外暴露過多操作能力的場景
- 2. 實作浏覽器的前進與後退
- 3. 棧在函數調用中的應用
4. 隊列
概念：隊列是一種先進先出的線性結構;
特點：隻有簡單的入隊 enqueue()與出隊 dequeue()操作。由于隊列的入隊操作與出隊操作都是沒有産生資料的移動，是以其時間複雜度都為O(1)。
類别：通過數組實作的隊列叫順序隊列，通過連結清單實作的隊列叫鍊式隊列。
适用場景：
1. 有限資源的配置設定政策：通俗地來說對于大部分資源有限的場景，當沒有空閑資源時，基本上都可以通過“隊列”這種資料結構來實作。
2. 類似“生産者與消費者”的模式，如消息隊列，對應的執行個體有KafKa。
5. 散清單
概念：散清單（Hash table，也叫哈希表），是存儲Key-Value映射的集合。
特點：可根據鍵(key)實作近O(1)的時間内對記憶體中資料進行讀寫的資料結構。散清單支援随機通路用的正是數組通過下标來随機通路資料的特性，可以說散清單就是數組的一個擴充。
組織資料：數組+連結清單或數組+連結清單+平衡樹。
沖突解決：開放尋址或連結清單法。HashMap使用的是連結清單法，以及在JDK1.8後通過位運算優化了動态擴容copy資料這個缺點。
适合場景：
- 1. 拼寫檢查器：如word文檔中拼寫錯誤提示功能。
- 2. 實作LRU緩存淘汰算法，如java中 LinkedHashMap。
6. 跳表
概念：跳表（Skip List）也稱跳躍表，是一種基于在有序連結清單上挑選關鍵點來建立多層索引的動态資料結構。
特點：思想上通過空間換取時間；查找方式與效果類似數組的二分查找。
原理：跳表實質就是一種可進行二分查找的有序連結清單。
時空複雜性分析：額外建立多層索引空間複雜度為O(n); 查找或更新時間複雜度為O(logn)，相對于有序數組其插入或删除不需要移動資料，故在寫方面時間複雜度好過有序數組的O(n)。
适用場景
- Leveldb，一個google實作的非常高效的kv資料庫；
- Redis SortedSet，Redis 通過跳表實作有序集合；
- 可以替代部分需要用平衡樹實作的場景。
- Java 容器對應的 ConcurrentSkipListMap
7. 樹
概念：由n（n>=1）個有限結點組成一個具有層次關系的集合。
特點：最大的特點是一種支援快速查找、删除、插入的動态資料結構。
常用的存儲方式：基于指針的連結清單式存儲，還有一種就是基于數組的順序存儲。
适合場景：
幾乎很多底層設計結構都有樹的存在，如：Mysql 資料庫索引通過B+樹存儲，HashMap 通過紅黑樹。
8. 圖
概念：圖(Graph )是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為: G (V,E )，其中，G表示一個圖,，V是圖G中頂點的集合，E是圖G中邊的集合。
存儲方式：通常有兩種方式分别為鄰接距陣與連結清單式存儲。
适合場景
1.幾乎所有難以通過線性表解決的問題如果可以轉換成圖，便可用圖現成的一些算法快速解決。
2.存儲微信或微網誌的好友關系。
3. 圖還可以應用在一些導航圖或城市規劃等形成的權重圖；
4. 做為一些圖資料庫的底層思想存在。
注：了解更多資料結構知識