Object & Array & Linked List BigO
Array
- Insert插入(push) → O(1)
- Insert插入(shift) → O(n)
- Remove移除(pop) → O(1)
- Remove移出(unshift) → O(n)
- Searching查詢 → O(n)
- Accessing(arr[6]) → O(1)
Object
- Insert插入 → O(1)
- Remove移除 → O(1)
- Searching查詢 → O(1)
- Accessing → O(1)
Linked List
- Insert插入(push) → O(n)無尾針,O(1)有尾針
- Insert插入(shift) → O(1)
- Remove移除(pop) → O(n)
- Remove移出(unshift) → O(1)
- Searching查詢 → O(n)
Array
優點 :
- 資料存取查詢 by random access：在array中只需要利用index即可對特定位置的資料作存取與查詢，此動作之時間複雜度為O(1)。
- 較linked list節省記憶體空間：linked list需要額外的記憶體空間來儲存指到下一個node的pointer。例如: node的data element為4bytes的
int，但是pointer element也需要4bytes空間來儲存下個node的記憶體位置，這樣就多費了1倍的記憶體空間在儲存非真正要處理的資料上，較無效率。
缺點：
- 沒有像linked list 能動態新增和刪除元素的資料結構特性 : array 的元素在記憶體中是連續儲存的，而linked list的元素為非連續儲存的。所以假設要新增array的第1個位置的元素，則須將第2~last位置的元素一一往後搬動，時間複雜度為O(N)。同理，若要刪除第1個位置的資料，也需O(N)時間把array中剩餘的元素一一往前搬動。
- 若資料數量時常在改變，要時常調整array的大小，需花費O(N)時間在搬動資料from old-array to new-array上。
— 使用時機 :
- 希望能夠快速存取查詢資料，時間複雜度只有O(1)。
Linked list
優點 :
- 增加or刪除資料較array簡單，只要對O(1)個node(所有與欲新增/刪除的node有pointer相連的node)調整pointer指向的node即可，不需要像array搬動一堆其餘元素。若是在linked list的head新增node，只需O(1)的時間複雜度。若想在特定位置新增or刪除node，會需要先作O(N)搜尋到特定node後，再作新增or刪除node的動作。
- Linked list的資料數量可以是動態的，不像array會有amortization的resize問題。
缺點 :
- 因為linked list沒有index，若要存取查詢(access)特定node的資料，可能會需要從頭開始找，故access的搜尋時間複雜度為O(N)。
- 需要額外的記憶體空間來儲存指到下一個node的pointer。
—使用時機 :
- 無法預期資料數量時，使用linked list就沒有resize的問題。
