如果讀到本文的你剛好是在校學子，不妨擴散給你的同學們，希望能在讀書的時候，不光學會會考，也盡量嘗試學著去用！

啥是鏈表？

鏈表是計算機科學中一種鏈式線性表，數據域為節(jié)點的一部分，每個節(jié)點都指向下一個節(jié)點，從而在邏輯上形成一個鏈。

線性表 vs 非線性表

什么樣的表是線性表？什么樣的表又是非線性表呢？既然有線性表就必然有非線性表！

線性表：

• 邏輯存儲角度：這里線性是指邏輯上的線性，除了首位元素，其他元素從邏輯上是一對一邏輯上連起來的
• 訪問遍歷角度：訪問元素是朝著邏輯上一個方向即可遍歷訪問所有元素

那么概括起來說就是一種數據元素按順序或線性排列的數據結構，其中元素與它的上一個和下一個相鄰，稱為線性數據結構。在線性數據結構中，只涉及單層數據。因此，只能在一次運行中遍歷所有元素。由于計算機內存以線性方式排列，因此線性數據結構易于實現。那么滿足上面這樣特性的，常見的數組、隊列、棧、鏈表即是線性表。

非線性表：

數據元素不是按邏輯順序或線性排列的數據結構稱為非線性數據結構。在非線性數據結構中，不涉及單個級別。因此不能在朝一個邏輯方向遍歷所有元素。與線性數據結構相比，非線性數據結構不容易實現。與線性數據結構相比，它能有效地利用計算機內存，在邏輯上一對多或者多對多的關系，比如樹、圖。

如何鏈？

Linked list（鏈表），從語義上理解，首先這玩意兒是一個表(list),是怎樣的一個表呢？數據節(jié)點鏈接(Linked)起來的表！

怎么鏈起來的呢？

邏輯上鏈起來的，這里有兩種辦法：

• 動態(tài)存儲方法：動態(tài)申請節(jié)點內存，然后利用節(jié)點中的指針指向下一個節(jié)點，實現鏈。優(yōu)點是存儲節(jié)點數理論上無限制，不需要提前分配內存，僅受限于物理可用內存。但不易于調試。
• 靜態(tài)存儲方法：比如用數組實現。這種方法比較易于調試，缺點是不能動態(tài)分配節(jié)點，需要提前分配內存，存儲節(jié)點有限。

對于動態(tài)存儲方法而言，易于理解，一想到鏈表很多盆友都立馬想到，設計一個節(jié)點，沒增加一個鏈節(jié)點，動態(tài)申請節(jié)點大小內存，再把節(jié)點插入進鏈表即可。對于靜態(tài)方法，可能常常覺得并沒啥用。事實上呢卻不然。比如前面我寫過一篇RT-Thread的小堆管理器的實現，即是采用了靜態(tài)存儲方法實現了鏈表。

可參閱：

實用算法解讀之RT-Thread鏈表堆管理器

為啥要鏈表？

探究計算機先輩為啥要發(fā)明這樣一種數據結構呢？不妨拿最為普通的數組與鏈表做些對比，數組在存儲信息的角度與鏈表從作用角度最為類型的一種線性數據，但是數組具有以下限制：

• 數組的大小是固定的：因此必須提前知道元素數量的上限。過小則應用時可能不夠，過大則易浪費。
• 數組中插入新元素非常昂貴，因為必須為新元素創(chuàng)建空間，并且必須移動現有所有元素。CPU忙忙碌碌干了一堆無聊的搬運工工作。

而動態(tài)存儲實現的鏈表則很好解決了這些缺陷：

• 動態(tài)申請、動態(tài)刪除，高效利用內存，不易浪費
• 非常易于插入刪除某一個元素

任何事物都具有兩面性，不可能全是優(yōu)點而無缺點，鏈表也一樣：

• 不允許隨機訪問。必須從第一個節(jié)點開始順序訪問元素。因此無法使用其默認實現對鏈接列表進行有效的二進制搜索。
• 鏈表的每個節(jié)點都需要指向下一節(jié)點的指針的額外存儲空間開銷。
• 不適合緩存。由于數組元素是連續(xù)的位置，因此存在引用位置，可以實現緩存。而動態(tài)存儲形式鏈表則地址是不連續(xù)的。

對于應用而言，必然是根據待解決的問題的特點進而選擇合適的數據結構存儲方式，不是說鏈表就高大上，從而鄙視最為普通的數組！

談談節(jié)點

實際應用中的數據節(jié)點，可能是一個基本類型數據，也可能是一個結構體，泛言之是一個廣義抽象數據類型，比如：

typedef struct _T_ELEMENT{
    int cmd;
    float value;
    int status;
}T_ELEMENT;
struct Node { 
    T_ELEMENT data; 
    struct Node* next; 
}; 

如果你剛好在學習鏈表，準備用C語言擼一遍代碼，建議用typedef定義一下抽象數據結構為節(jié)點數據域，這樣代碼將很容易變成一個可實用的輪子。

有哪些鏈表形式？

單向鏈表

單鏈表包含兩個域：

• 數據信息域，存儲有用信息。
• next指針域，“next”字段指向節(jié)點行中的下一個節(jié)點。

鏈表最基本的結構是在每個節(jié)點保存有用數據及下一個節(jié)點的地址，在最后一個節(jié)點保存一個特殊的結束標記，另外在一個固定的位置保存指向首節(jié)點的指針，應用中有時候也會儲存指向最后一個節(jié)點的指針。一般查找一個節(jié)點的時候需要從第一個節(jié)點開始每次訪問下一個節(jié)點，一直訪問到需要的位置。但是也可以提前把一個節(jié)點的位置另外保存起來，然后直接訪問?？梢栽趩捂湵砩蠄?zhí)行的操作包括插入、刪除和遍歷。

雙向鏈表

與單向鏈表相比，雙向鏈表多了一個指向前一節(jié)點的指針：

雙向鏈表也叫雙鏈表。雙向鏈表中不僅有指向后一個節(jié)點的指針，還有指向前一個節(jié)點的指針。這樣可以從任何一個節(jié)點訪問前一個節(jié)點，當然也可以訪問后一個節(jié)點，以至整個鏈表。一般是在需要大批量的另外儲存數據在鏈表中的位置的時候用。雙向鏈表也可以配合下面的其他鏈表的擴展使用。這樣做好處顯而易見，可以從任意節(jié)點遍歷整個鏈表，但是需要額外為每個節(jié)點申請一個指針的存儲空間開銷。

循環(huán)鏈表

循環(huán)鏈表中, 首節(jié)點和末節(jié)點被鏈接在一起。這種數據結構在單向和雙向鏈表中都可以實現。要遍歷一個循環(huán)鏈表，可以從任意一個節(jié)點沿著列表的任一方向直到返回開始的節(jié)點。循環(huán)鏈表可以被視為“無頭無尾”。這種結構利于節(jié)約內存空間。

單向循環(huán)鏈表：

雙向循環(huán)鏈表：

循環(huán)鏈表中第一個節(jié)點的前一個節(jié)點就是最后一個節(jié)點，反之亦然。循環(huán)鏈表的無邊界