1
ArrayList 與 LinkedList 的插入資料大比拚 (blog.jiebu-lang.com)
Thinker 積分 1 編輯於

沒考慮資料大小。array 的問題在 memory copy.如果考慮每個 element 是 128 bytes或更大,情況就不同。

jameslong 積分 0

請問可以舉例嗎?因為文章說明僅用數字進行舉例,還是每個block 大小不一時的memory copyc 會呈現出來結果也不同?

Thinker 積分 2

Linked list 的時間是隨距離兩端的長度而線性成長。而 array 則是隨和尾端的距離線性成長。兩者都線性時,快慢的差別在 coefficient。list 的 coefficient 是讀pointer 的 cost ,array 則是 copy 的 cost。讀pointer 的cost 是固定的,但 copy 卻會隨資料而變。

但,也可在 array 裡放pointet,讓 copy cost 最小化。

but but,一般會把 search 和 insert 分開討論。這篇文章實際上是 search+insert 的結果。先 search/index 到特定 element,然後insert在前面。實際使用 linked list 時,都是 push head or tail,或用其他方法快速找到插入的位置。如 cache or hash table...

jameslong 積分 0

感謝,我再來消化一下