? ? ? ?數(shù)組是編程語言中提供的很有用的數(shù)據(jù)結(jié)構(gòu)。但它有至少2個局限（1）若改變數(shù)組的大小，就要新建一個數(shù)據(jù)，并需要從原數(shù)組中復制所有的數(shù)據(jù)到新數(shù)組中（2） 數(shù)組中在內(nèi)存中是依次連續(xù)存儲的，這意味著插入一條數(shù)據(jù)，要移動數(shù)組中的其他數(shù)據(jù)。這一局限可以通過鏈式結(jié)構(gòu)解決。鏈式結(jié)構(gòu)是存儲數(shù)據(jù)的節(jié)點以及指向其他節(jié)點的鏈指針的集合

? ?鏈表的定義：如果一個節(jié)點包含指向另一個節(jié)點的數(shù)據(jù)域，那么多個節(jié)點可以串在一起，僅僅用一個節(jié)點就可以訪問整個節(jié)點序列，這樣一個節(jié)點就是最常用的鏈表。其數(shù)據(jù)結(jié)構(gòu)是由節(jié)點組成，每一個節(jié)點保存一些信息和指向表中另一個節(jié)點的引用

如果每個節(jié)點僅包含其后節(jié)點的一個引用，則該表為單向鏈表

我們用單鏈表演示一個實例：

創(chuàng)建了一個單鏈表的節(jié)點

刪除尾部的節(jié)點

我們看這個方法會發(fā)現(xiàn)，我們無法立即找到tail的前驅(qū)節(jié)點，只能通過遍歷的方法來尋找，這會嚴重妨礙處理鏈表的速度。為了避免這個問題，我們使每一個節(jié)點，有兩個引用域，一個指向前驅(qū)節(jié)點，一個指向后繼節(jié)點。這種類型的節(jié)點成為雙向鏈表

java中LinkedList使用的就是雙向鏈表，我們打開LinkedList的源碼看一下

第一句就表明了LinkedList是實現(xiàn)List接口的雙向鏈表