一银觅、定義
1.需要明確幾個概念：線性表（順序表, list, linear list）, 數(shù)組(array)，鏈表(linked-list)。
2.線性表：在中文里江掩，線性表也叫作順序表再悼。在英文中核畴，它稱為list, linear list等。它是最基礎(chǔ)冲九、最簡單谤草、最常用的一種基本數(shù)據(jù)結(jié)構(gòu)跟束，線性表總存儲的每個數(shù)據(jù)稱為一個元素，各個元素及其索引是一一對應(yīng)的關(guān)系丑孩。線性表有兩種存儲方式：順序存儲方式和鏈?zhǔn)酱鎯Ψ绞健?br>
3.數(shù)組(array)：數(shù)組就是線性表的順序存儲方式冀宴。數(shù)組的內(nèi)存是連續(xù)分配的，并且是靜態(tài)分配的温学，即在使用數(shù)組之前需要分配固定大小的空間略贮。可以通過索引直接得到數(shù)組中的而元素仗岖，即獲取數(shù)組中元素的時間復(fù)雜度為O(1)逃延。
4.鏈表(linked-list)：鏈表就是線性表的鏈?zhǔn)酱鎯Ψ绞健ｆ湵淼膬?nèi)存是不連續(xù)的轧拄，前一個元素存儲地址的下一個地址中存儲的不一定是下一個元素揽祥。鏈表通過一個指向下一個元素地址的引用將鏈表中的元素串起來。
鏈表分為單向鏈表(Singly linked lis)檩电、雙向鏈表(Doubly linked list)拄丰、循環(huán)鏈表(Circular Linked list)。
二俐末、單向鏈表
1.單向鏈表是最簡單的鏈表形式愈案。我們將鏈表中最基本的數(shù)據(jù)稱為節(jié)點(node)，每一個節(jié)點包含了數(shù)據(jù)塊和指向下一個節(jié)點的指針鹅搪。
2.插入
在鏈表中插入一個新的元素有兩種方式：后插和前插站绪。后插就是每次在鏈表的末尾插入新元素，前插就是在鏈表的頭插入新元素丽柿。
后插法比較符合平常的思維方式恢准，并且保證插入數(shù)據(jù)的先后順序。但是由于只保存了頭結(jié)點甫题，所以每次插入新元素必須重新遍歷到鏈表末尾馁筐。為了解決這個問題，考慮增加一個尾指針坠非，指向鏈表的最后一個節(jié)點敏沉。
由于前插法是在頭部插入新元素，那么每次增加新元素可以直接通過頭指針?biāo)饕茁耄堑玫降脑仨樞蚺c插入順序相反
2.刪除
由于單向鏈表只存儲了頭指針盟迟，所以刪除單向鏈表中的元素時，需要找到目標(biāo)節(jié)點的前驅(qū)節(jié)點潦闲。
三攒菠、雙向鏈表
1.顧名思義，雙向鏈表就是有兩個方向的鏈表歉闰。同單向鏈表不同辖众，在雙向鏈表中每一個節(jié)點不僅存儲指向下一個節(jié)點的指針卓起，而且存儲指向前一個節(jié)點的指針。通過這種方式凹炸，能夠通過在O(1)時間內(nèi)通過目的節(jié)點直接找到前驅(qū)節(jié)點戏阅，但是同時會增加大量的指針存儲空間。
2.插入
在雙向鏈表中插入新元素的操作跟在單向鏈表中插入新元素的操作類似啤它。
3.刪除
由于雙向鏈表中每個節(jié)點記錄了它的前驅(qū)結(jié)點饲握，所以不需要像單向鏈表中一樣索引目的節(jié)點的前驅(qū)節(jié)點，而是可以通過目標(biāo)節(jié)點直接獲得蚕键。
在雙向鏈表中救欧，第一個節(jié)點的前驅(qū)節(jié)點不是頭結(jié)點，而是指向一個空指針锣光。同樣的笆怠，最后一個節(jié)點的后驅(qū)指向了一個空指針。
四誊爹、循環(huán)鏈表
1.循環(huán)鏈表與雙向鏈表相似蹬刷，不同的地方在于：在鏈表的尾部增加一個指向頭結(jié)點的指針，頭結(jié)點也增加一個指向尾節(jié)點的指針频丘，以及第一個節(jié)點指向頭節(jié)點的指針办成，從而更方便索引鏈表元素。
2.插入搂漠、刪除
循環(huán)鏈表的插入和刪除操作與雙向鏈表的實現(xiàn)方式一樣迂卢。
