1、單鏈表
傳送1
2、雙鏈表
3、循環(huán)鏈表
4、靜態(tài)鏈表
5、順序表和鏈表的比較
????1)在存取方式上：順序表可以順序存取也可以隨機(jī)存取，而鏈表只能從表頭順序存取元素
????2)在邏輯結(jié)構(gòu)和物理結(jié)構(gòu)上：順序存儲需要邏輯物理都相鄰，而鏈?zhǔn)酱鎯t不要求
????3)在查找刪除插入操作上：在按值查找，順序表無序的情況下，兩者時間復(fù)雜度都為O(n)，在有序的情況下，可采用折半則時間復(fù)雜度為O(log2n).
對于按序號查找，順序表可以直達(dá)，而鏈表則需要遍歷為O(n)順序表的插入刪除操作,平均需要移動一半的元素，而鏈表則是只需要修改相關(guān)的指針域。
? ? 4）在空間分配方面：順序存儲不夠靈活，而鏈?zhǔn)酱鎯t是需要才申請分配。
通過對它們的討論可知它們各有優(yōu)缺點(diǎn)，順序存儲有三個優(yōu)點(diǎn)：
(1) 方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。
(2) 不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。
(3) 順序表具有按元素序號隨機(jī)訪問的特點(diǎn)。
但它也有兩個缺點(diǎn)：
(1) 在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。
(2) 需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。
鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。在實際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：
１．基于存儲的考慮
順序表的存儲空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲規(guī)模，也就是說事先對＂MAXSIZE＂要有合適的設(shè)定，過大造成浪費(fèi)，過小造成溢出?？梢妼€性表的長度或存儲規(guī)模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低，存儲密度是指一個結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲單元和整個結(jié)點(diǎn)所占的存儲單元之比。顯然鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度是小于１的。
２．基于運(yùn)算的考慮
在順序表中按序號訪問ai的時間性能時O(1)，而鏈表中按序號訪問的時間性能O(n)，所以如果經(jīng)常做的運(yùn)算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時平均移動表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大且表較長時，這一點(diǎn)是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優(yōu)于前者。
３．基于環(huán)境的考慮
順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個因素。
總之，兩中存儲結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通常“較穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯Α?/p>
注：
單鏈表中增加頭結(jié)點(diǎn)的目的是為了方便運(yùn)算
在一個長度為N的帶頭節(jié)點(diǎn)的單鏈表h上，設(shè)有為指針R，則執(zhí)行刪除最后一個元素的操作與表長有關(guān)，因為，需要修改上一個結(jié)點(diǎn)的指針域，所以需要遍歷整個鏈表
