鍊表
概述
鍊表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鍊表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。
使用鍊表結構可以克服數組鍊表需要預先知道數據大小的缺點，鍊表結構可以充分利用計算機記憶體空間，實現靈活的記憶體動態管理。但是鍊表失去了數組隨機讀取的優點，同時鍊表由於增加了結點的指針域，空間開銷比較大。
在計算機科學中，鍊表作為一種基礎的數據結構可以用來生成其它類型的數據結構。鍊表通常由一連串節點組成，每個節點包含任意的實例數據（data fields）和一或兩個用來指向上一個/或下一個節點的位置的連結（"links"）。鍊表最明顯的好處就是，常規數組排列關聯項目的方式可能不同於這些數據項目在記憶體或磁碟上順序，數據的訪問往往要在不同的排列順序中轉換。而鍊表是一種自我指示數據類型，因為它包含指向另一個相同類型的數據的指針（連結）。鍊表允許插入和移除表上任意位置上的節點，但是不允許隨機存取。鍊表有很多種不同的類型：單向鍊表，雙向鍊表以及循環鍊表。
存儲結構
鍊表中的節點不需要以特定的方式存儲，但是集中存儲也是可以的，主要分下面這幾種具體的存儲方法：
共用存儲空間
鍊表的節點和其它的數據共用存儲空間，優點是可以存儲無限多的內容（不過要處理器支持這個大小，並且存儲空間足夠的情況下），不需要提前分配記憶體；缺點是由於內容分散，有時候可能不方便調試。
獨立存儲空間
一個鍊表或者多個鍊表使用獨立的存儲空間，一般用數組或者類似結構實現，優點是可以自動獲得一個附加數據：唯一的編號，並且方便調試；缺點是不能動態的分配記憶體。當然，另外的在上面加一層塊狀鍊表用來分配記憶體也是可以的，這樣就解決了這個問題。這種方法有時候被叫做數組模擬鍊表，但是事實上只是用表示在數組中的位置的下標索引代替了指向記憶體地址的指針，這種下標索引其實也是邏輯上的指針，整個結構還是鍊表，並不算是被模擬的（但是可以說成是用數組實現的鍊表）。
鏈式存儲結構
鏈式存儲結構中每個結點除了包含信息域之外，還至少包含 一個指針域。鏈式存儲結構是用指針來體現數據元素之間的邏輯關係的。利用這種結構，各個數據元素的存儲單元不再要求是連續的，即可以把邏輯上相鄰的兩個元素存放在物理上不相鄰的存儲單元中，還可以線上性編址的存儲器中表示非線性關係的結點。
鏈式存儲結構的主要特點為：
結點中除包含保存數據元素的自身信息的信息域外，還有表示數據元素之間的連結信息的指針域，因此比順序存儲結構的存儲密度低，存儲空間的利用率也較低。
邏輯上相鄰的數據元素在物理上不一定相鄰，可用於存儲線性表、樹、圖等多種邏輯結構。
插入、刪除操作比較靈活，不必移動數據元素，只要改變結點中的指針域的值即可。
串的鏈式存儲
鏈串
用單鍊表方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串鏈串的結構類型定義 ：
typedef struct node{
char data;
struct node *next;
}LinkStrNode; //結點類型
typedef LinkStrNode *LinkString; //LinkString為鏈串類型
LinkString S; //S是鏈串的頭指針
注意：①鏈串和單鍊表的差異僅在於其結點數據域為單個字元：
②一個鏈串由頭指針唯一確定。
鏈串的結點大小
通常，將結點數據域存放的字元個數定義為結點的大小。結點的大小的值越大，存儲密度越高。
可以採取以下措施
①為了提高存儲密度，可使每個結點存放多個字元。
②當結點大小大於1時，串的長度不一定正好是結點大小的整數倍，因此要用特殊字元來填充最後一個結點，以表示串的終結。
③雖然提高結點的大小使得存儲密度增大，但是做插入、刪除運算時，可能會引起大量字元的移動，給運算帶來不便。
