ArrayList 與 LinkedList 的插入資料大比拚
(blog.jiebu-lang.com)
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...
這是文章的子討論串,你可以回到上層查看所有討論和文章