列表的鏈接列表或數組實現的優點和缺點

列表的鏈接列表實現具有優於基於數組的實現和副作用的優點是什麼？列表的鏈接列表或數組實現的優點和缺點

對於初學者，我知道鏈表使用了比數組多的空間，因爲它必須使用額外的4個字節的空間來存放對下一個節點的引用，並且數組不需要這樣做。所以陣列使用更少的空間。

優點linked-list在數組上的實現是數組在初始化時具有固定的大小，並且您必須編寫代碼來增加數組的大小，因此與鏈接列表實現相比可能是不利的。

對於其他優勢缺點的任何想法？

http://stackoverflow.com/questions/393556/when-to-use-a-linked-list-over-an-array-array-list –

對於數組，如果有索引（恆定時間複雜度O（1）），則可以訪問任何元素。但是對於一個列表，儘管有索引（時間複雜度爲O（n）），但您必須逐個訪問才能訪問。有關列表，插入和刪除元素需要一個固定時間（O（1））。但對於數組，插入和刪除需要O（n）時間。

對於排序，列表實現比數組實現要好。

2013-10-07 07:04:22 SRF

我喜歡你的答案，因爲你做了更徹底的分析列表的2個實現之間的比較。推薦的SO帖子在數組和鏈接列表之間進行了更多的比較，這與我的直接問題略有不同。 – user2838559

回答