ArrayList 與 LinkedList 的插入資料大比拚
(blog.jiebu-lang.com)
沒考慮資料大小。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...