鏈表(Linked List)?線性結(jié)構(gòu)

鏈表與數(shù)組看起來非常像，但是內(nèi)存分配方式、內(nèi)部結(jié)構(gòu)和插入刪除操作方式都不一樣。鏈表是一系列節(jié)點(diǎn)組成的鏈，每一個(gè)節(jié)點(diǎn)保存了數(shù)據(jù)以及指向下一個(gè)節(jié)點(diǎn)的指針。鏈表頭指針指向第一個(gè)節(jié)點(diǎn)，如果鏈表為空，則頭指針為空或者為 null。鏈表可以用來實(shí)現(xiàn)文件系統(tǒng)、哈希表和鄰接表。

在 Java 中創(chuàng)建鏈表的過程和創(chuàng)建數(shù)組的過程不同，不會(huì)先劃出一塊連續(xù)的內(nèi)存。因?yàn)殒湵碇械臄?shù)據(jù)并不是連續(xù)的，鏈表在存儲(chǔ)數(shù)據(jù)的內(nèi)存中有兩塊區(qū)域，一塊區(qū)域用來存儲(chǔ)數(shù)據(jù)，一塊區(qū)域用來記錄下一個(gè)數(shù)據(jù)保存在哪里(指向下一個(gè)數(shù)據(jù)的指針)。當(dāng)有數(shù)據(jù)進(jìn)入鏈表時(shí)候，會(huì)根據(jù)指針找到下一個(gè)存儲(chǔ)數(shù)據(jù)的位置，然后把數(shù)據(jù)保存起來，然后再指向下一個(gè)存儲(chǔ)數(shù)據(jù)的位置。這樣鏈表就把一些碎片空間利用起來了，雖然鏈表是線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)。

由于鏈表是以這種方式保存數(shù)據(jù)，所以鏈表在插入和刪除時(shí)比較容易，讀取數(shù)據(jù)時(shí)比較麻煩。舉個(gè)例子：一個(gè)鏈表中0->1->2->3->4這五個(gè)內(nèi)存地址中都存了數(shù)據(jù)，現(xiàn)在需要往2中插入一條數(shù)據(jù)，那么只需要更改1號(hào)和2號(hào)中記錄下一個(gè)數(shù)據(jù)的位置就行了，對(duì)其他數(shù)據(jù)沒有影響。刪除一條數(shù)據(jù)與插入類似，很高效。但是如果是想要在鏈表其中取出一條數(shù)據(jù)，就需要從0號(hào)開始一個(gè)一個(gè)的找，直到找到想要的那條數(shù)據(jù)為止。