1.2 鏈表

鏈表（Linked list）是一種物理存儲單元上非連續的數據結構，數據元素的邏輯順序是通過鏈表中的指針實現的。由于不必按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，但鏈表查找的時候由于不能通過索引查找，所以查找的時間復雜度是O(n)。常見的鏈表有單向鏈表、雙向鏈表，以及環形鏈表。

1. 單向鏈表

單向鏈表是一種最簡單的鏈表，一般只包含存儲的數據和指針（注意這里的指針并不是C語言中的地址指針，它是下一個節點的引用），每個指針指向下一個節點，最后一個節點的指針指向空，如圖1-10所示。

2. 雙向鏈表

雙向鏈表的每個節點都有兩個指針，一個指向前一個節點，一個指向后一個節點，頭節點的前一個節點為空，尾節點的后一個節點也為空，如圖1-11所示，在Java中可以參考LinkedList。

3. 環形鏈表

環形鏈表是一種首尾相連的鏈表，環形鏈表分為單向環形鏈表和雙向環形鏈表。在Java中可以參考LinkedHashMap。

4. 鏈表和數組的區別

?數組靜態分配內存，鏈表動態分配內存；

?數組在內存中連續，鏈表不連續；

?數組利用下標訪問，時間復雜度為O(1)，鏈表訪問元素時間復雜度為O(n)；

?數組插入或刪除元素的時間復雜度為O(n)，鏈表插入或刪除的時間復雜度為O(1)，前提是要知道插入和刪除的位置。

5. 跳表

鏈表雖然插入和刪除效率比較高，但也有缺點，即使鏈表節點是有序的，還是需要從前往后一個個查找，這樣顯然很慢，這個時候我們可以使用跳表，跳表就是多層鏈表，最下面一層是原始鏈表，從下往上節點個數逐漸減少，如圖1-12所示。

查詢的時候先從最上面一層索引開始查，如果查找值在兩個節點之間，就到下一級索引繼續查，比如要查找8，查找過程如圖1-13所示，在圖中已經用粗線標出。