線性表按存儲(chǔ)方式分為順序表和鏈表兩種，其中鏈表又分為單鏈表，循環(huán)鏈表，雙鏈表，雙向循環(huán)鏈表。
順序表
順序表采用順序存儲(chǔ)結(jié)構(gòu)，用一段連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，對(duì)于非空的順序表，其有著以下特性：
存在唯?一的?一個(gè)被稱作”第?一個(gè)”的數(shù)據(jù)元素;
存在唯?一的?一個(gè)被稱作”最后?一個(gè)"的數(shù)據(jù)元素；
除了了第?一個(gè)之外,結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素均有?一個(gè)前驅(qū)；
除了了最后?一個(gè)之外,結(jié)構(gòu)中的每個(gè)數(shù)據(jù)元素都有?一個(gè)后繼。
在使用時(shí)類(lèi)似與OC中的數(shù)組，可以用下標(biāo)來(lái)操作。
順序表的創(chuàng)建
插入
取值和遍歷
刪除和清空
鏈表
鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的元素。相比于順序表，鏈表不需要預(yù)先分配內(nèi)存空間，其中一個(gè)個(gè)元素是一個(gè)個(gè)結(jié)點(diǎn)。
結(jié)點(diǎn)
鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。在我看來(lái)就是前面是數(shù)據(jù)，后面是指向鏈表中下一個(gè)結(jié)點(diǎn)的指針。
單鏈表
單鏈表分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種，不管有無(wú)頭結(jié)點(diǎn)，頭指針都指向鏈表的第一個(gè)節(jié)點(diǎn)（有頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)，沒(méi)有則指向首元結(jié)點(diǎn)），其邏輯狀態(tài)如下圖所示：
后續(xù)代碼是帶頭結(jié)點(diǎn)的，使用頭結(jié)點(diǎn)的原因有兩個(gè)：1.便于首元結(jié)點(diǎn)的處理，不需要再額外區(qū)分；2.便于空表和非空表的統(tǒng)一處理。
單鏈表的創(chuàng)建
插入
取值和遍歷
刪除和清空
不同與順序表的是，單鏈表清空和刪除時(shí)需要釋放對(duì)應(yīng)內(nèi)存空間。
頭插法和尾插法創(chuàng)建單鏈表
面試經(jīng)常問(wèn)的應(yīng)該就是頭插法了。
單向循環(huán)鏈表
為了對(duì)比，下面的單向循環(huán)鏈表沒(méi)有加頭結(jié)點(diǎn)，所以在使用時(shí)需要判斷是否是首元結(jié)點(diǎn)。
創(chuàng)建
遍歷
插入
刪除
查詢
雙向鏈表
雙向鏈表結(jié)點(diǎn)和邏輯狀態(tài)
對(duì)比單向鏈表，也就是結(jié)點(diǎn)中多了個(gè)指向前一個(gè)結(jié)點(diǎn)的指針prior。所以雙向鏈表可以由一個(gè)結(jié)點(diǎn)找到前一個(gè)結(jié)點(diǎn)，而單鏈表只能找到后續(xù)結(jié)點(diǎn)。也是因?yàn)檫@點(diǎn)，雙向鏈表可以直接找到對(duì)應(yīng)結(jié)點(diǎn)進(jìn)行操作，而不是找到對(duì)應(yīng)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)（如下面的刪除指定元素）。
創(chuàng)建
插入
刪除
雙向循環(huán)鏈表
相比于雙向鏈表，雙向循環(huán)鏈表頭尾相連，所以處理時(shí)需要注意修改頭結(jié)點(diǎn)的prior以及最后一個(gè)結(jié)點(diǎn)的next。
創(chuàng)建
插入
刪除
總結(jié)：
1）當(dāng)線性表需要頻繁查找，較少插入和刪除時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)。若需要頻繁插入和刪除，宜采用鏈表。（ps：鏈表刪除和插入時(shí)間復(fù)雜度是O(1)，指的是查找后，順序表插入和刪除則需要移動(dòng)空間。）
2）當(dāng)線性表的元素個(gè)數(shù)變化較大或不確定時(shí)，最好用鏈表，這樣不需要考慮存儲(chǔ)空間大小問(wèn)題。當(dāng)事先知道線性表的大小長(zhǎng)度，用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高一些。
參考資料：
