連結清單和數組是資料類型中兩個重要又常用的基礎資料類型，數組是連續存儲在記憶體中的資料結構，是以它的優勢是可以通過下标迅速的找到元素的位置，而它的缺點則是在插入和删除元素時會導緻大量元素的被迫移動，為了解決和平衡此問題于是就有了連結清單這種資料類型。
連結清單和數組可以形成有效的互補，這樣我們就可以根據不同的業務場景選擇對應的資料類型了。那麼，本文我們就來重點介紹學習一下連結清單，一是因為它非常重要，二是因為面試面試必考，先來看本文的大綱：
看過某些抗日神劇我們都知道，某些秘密組織為了防止組織的成員被“一窩端”，通常會采用上下級單線聯系的方式來保護其他成員，而這種“行為”則是連結清單的主要特征。
本文已收錄至 Github《小白學算法》系列：https://github.com/vipstone/algorith
連結清單（Linked List）是一種常見的基礎資料結構，是一種線性表，但是并不會按線性的順序存儲資料，而是在每一個節點裡存到下一個節點的指針（Pointer）。
連結清單是由資料域和指針域兩部分組成的，它的組成結構如下：
由于連結清單無需按順序存儲，是以連結清單在插入的時可以達到 O(1) 的複雜度，比順序表快得多，但是查找一個節點或者通路特定編号的節點則需要 O(n) 的時間，而順序表插入和查詢的時間複雜度分别是 O(log n) 和 O(1)。
使用連結清單結構可以克服數組連結清單需要預先知道資料大小的缺點，連結清單結構可以充分利用計算機記憶體空間，實作靈活的記憶體動态管理。但是連結清單失去了數組随機讀取的優點，同時連結清單由于增加了節點的指針域，空間開銷比較大。
連結清單通常會分為以下三類：
單向連結清單
雙向連結清單
循環連結清單
單循連結清單
雙循環連結清單
連結清單中最簡單的一種是單向連結清單，或叫單連結清單，它包含兩個域，一個資料域和一個指針域，指針域用于指向下一個節點，而最後一個節點則指向一個空值，如下圖所示：
單連結清單的周遊方向單一，隻能從鍊頭一直周遊到鍊尾。它的缺點是當要查詢某一個節點的前一個節點時，隻能再次從頭進行周遊查詢，是以效率比較低，而雙向連結清單的出現恰好解決了這個問題。
接下來，我們用代碼來實作一下單向連結清單的節點：
雙向連結清單也叫雙面連結清單，它的每個節點由三部分組成：prev 指針指向前置節點，此節點的資料和 next 指針指向後置節點，如下圖所示：
接下來，我們用代碼來實作一下雙向連結清單的節點：
循環連結清單又分為單循環連結清單和雙循環連結清單，也就是将單向連結清單或雙向連結清單的首尾節點進行連接配接，這樣就實作了單循環連結清單或雙循環連結清單了，如下圖所示：
學習了連結清單的基礎知識之後，我們來思考一個問題：Java 中的連結清單 LinkedList 是屬于哪種類型的連結清單呢？單向連結清單還是雙向連結清單？
要回答這個問題，首先我們要來看 JDK 中的源碼，如下所示：
從上述節點 <code>Node</code> 的定義可以看出：<code>LinkedList</code> 其實是一個雙向連結清單，因為它定義了兩個指針 <code>next</code> 和 <code>prev</code> 分别用來指向自己的下一個和上一個節點。
<code>LinkedList</code> 的設計還是很巧妙的，了解了它的實作代碼之後，下面我們來看看它是如何使用的？或者說它的常用方法有哪些。
接下來我們來示範一下增加方法的使用：
以上代碼的執行結果為：
[頭部添加, Java, 中文, 社群, 尾部添加]
出來以上的 3 個增加方法之外，<code>LinkedList</code> 還包含了其他的添加方法，如下所示：
add(int index, E element)：向指定位置插入元素；
offer(E e)：向連結清單末尾添加元素，傳回是否成功；
offerFirst(E e)：頭部插入元素，傳回是否成功；
offerLast(E e)：尾部插入元素，傳回是否成功。
它們的差別主要展現在以下兩點：
offer 方法屬于 Deque 接口，add 方法屬于 Collection 的接口；
當隊列添加失敗時，如果使用 add 方法會報錯，而 offer 方法會傳回 false。
删除功能的示範代碼如下：
[中間]
除了以上删除方法之外，更多的删除方法如下所示：
clear()：清空連結清單；
removeFirst()：删除并傳回第一個元素；
removeLast()：删除并傳回最後一個元素；
remove(Object o)：删除某一進制素，傳回是否成功；
remove(int index)：删除指定位置的元素；
poll()：删除并傳回第一個元素；
remove()：删除并傳回第一個元素。
修改方法的示範代碼如下：
[Java, MySQL, Oracle]
查詢方法的示範代碼如下：
DB Java MySQL --- peek() ---
<code>LinkedList</code> 的周遊方法包含以下三種。
周遊方法一：
周遊方法二：
周遊方法三：
接下來我們用連結清單來實作一個先進先出的“隊列”，實作代碼如下：
以上程式的執行結果如下：
中文 社群
然後我們用連結清單來實作一個後進先出的“棧”，實作代碼如下：
連結清單作為一種基本的實體結構，常被用來建構許多其它的邏輯結構，如堆棧、隊列都可以基于連結清單實作。
所謂的實體結構是指可以将資料存儲在實體空間中，比如數組和連結清單都屬于實體資料結構；而邏輯結構則是用于描述資料間的邏輯關系的，它可以由多種不同的實體結構來實作，比如隊列和棧都屬于邏輯結構。
連結清單最常見的筆試題就是連結清單的反轉了，之前的文章《連結清單反轉的兩種實作方法，後一種擊敗了100%的使用者！》我們提供了 2 種連結清單反轉的方法，而本文我們再來擴充一下，提供 3 種連結清單反轉的方法。
我們先用圖解的方式來示範一下，使用棧實作連結清單反轉的具體過程，如下圖所示。
全部入棧：
因為棧是先進後出的資料結構，是以它的執行過程如下圖所示：
最終的執行結果如下圖所示：
實作代碼如下所示：
LeetCode 驗證結果如下圖所示：
可以看出使用棧的方式來實作連結清單的反轉執行的效率比較低。
同樣的，我們先用圖解的方式來示範一下，此方法實作的具體過程，如下圖所示。
可以看出這種實作方法在執行效率方面已經滿足我們的需求了，性能還是很高的。
我們也可以通過循環的方式來實作連結清單反轉，隻是這種方法無需重複調用自身方法，隻需要一個循環就搞定了，實作代碼如下：
從上述圖檔可以看出，使用此方法在時間複雜度和空間複雜度上都是目前的最優解，比之前的兩種方法更加理想。
本文我們講了連結清單的定義，它是由資料域和指針域兩部分組成的。連結清單可分為：單向連結清單、雙向連結清單和循環連結清單，其中循環連結清單又可以分為單循連結清單和雙循環連結清單。通過 JDK 的源碼可知，Java 中的 <code>LinkedList</code> 其實是雙向連結清單，我們可以使用它來實作隊列或者棧，最後我們講了反轉連結清單的 3 種實作方法，希望本文的内容對你有幫助。
如果覺得有用請各位老爺多多點贊和分享，原創不易，謝謝您了！
關注下面二維碼，訂閱更多精彩内容。
關注公衆号（加好友）：
作者：
王磊的部落格
出處：
http://vipstone.cnblogs.com/