談Array與LinkedList的特性

講到常用的資料結構，一定會想到Array和LinkedList，但是一旦被問到他們的差別或是實際如何去應用時，很多人便會無法以實際的例子來詮釋，特別是在面試的時候。

兩者主要差異

以下是我整理出比較常見的差異

Array是index based的結構，LinkedList則是Reference based。
Array會存在sequential memory locations，LinkedList則是sequence of the elements，每一個element都會link下一個element。
Array裡面會儲存同樣結構的資料，可以是Primitive Data Type或是Object Data Type，LinkedList裡面每個儲存的Object都會包含Data與Link。
Array可以先宣告要多大的空間，LinkedList則不受限。
Array存取資料需要index，LinkedList需要從頭開始尋找資料。
但是上面列出來的差異都是大家很常見的，所以下面做更完整的整理。

儲存結構

Array：Random Access即是隨機存取，又被大家稱為直接存取。

techdifferences.com LinkedList：Sequencial Access則是需要循序走訪才能到達指定的目標。 ![](https://miro.medium.com/max/1200/0*Fz4zsgT2tAyabVnX.jpg) 舉例：這樣聽可能不太直接了解，要舉例生活例子的話，LinkedList就像以前的傳統捲動式卡帶，想要聽某一首歌必須要從頭拉到指定的曲目。Array就像是現今的CD，直接選曲目就可以馬上聽到想聽的歌曲。 ![](https://miro.medium.com/max/1400/0*KeLzA1_FsPmZIXaX) By Christoph Roser at AllAboutLean.com under the free CC-BY-SA 4.0 license.

儲存方式

Array：在compile的時候，便分配好空間，因此是固定的
LinkedList：在run time的時候分配空間，因此是彈性的
結論：因為儲存結構的關係，會因一開始的需求而決定使用哪個。

儲存順序

Array：在記憶體儲存是連續的
LinkedList：隨機儲存位置
結論：因為儲存結構的關係，造成走訪或存取的速度截然不同。

走訪方式

Array：O(1), 直接存取或隨機存取
LinkedList：O(n), 每次存取資料都需要循序走訪
結論：雖然Array較LinkedList的速度快，但是使用上比較沒有那麼彈性。

搜尋方式

Array：

Linear Search, O(n)
Binary Search, O(log(n))

LinkedList：Linear Search, O(n)
補充：為什麼LinkedList不太適合用 Binary Search？因為要使用Binary Search最好符合以下條件：

已經排序好
取得元素必須要constant time

所以很顯然的，LinkedList光是第二點就不適合使用，如果每次取得資料又要花一次線性時間去走訪，那為何不直接用Linear Search。

記憶體使用

Array：少量
LinkedList：大量
結論：Array節省記憶體使用空間，LinkedList需要儲存pointer，所以需要較大的空間。

複雜度分析

浪費空間 (wasted space)
Array：O(1)
LinkedList：O(n)
補充：Array的資料儲存較集中，LinkedList儲存較分散。
存取資料
Array：O(1)
LinkedList：O(n)
補充：Array通常因為這個原因，而被大家採用。
Array存取資料為Random Access，LinkedList必須從頭開始找。
Array回傳只需要data[index]即可

這邊以Java的ArrayList程式碼為例：

public E get(int index) {
    checkBoundExclusive(index);
    return data[index];
}

LinkedList回傳需要再get一次資料，因此需要耗費走訪的時間
這邊以Java的LinkedList程式碼為例：

public T get(int index) {
    checkBoundsExclusive(index);
    return getEntry(index).data;
}

中間插入/刪除資料
Array：O(n)
LinkedList：O(n)
補充：LinkedList通常因為這個原因，而被大家採用。
Array每次要插入元素，必須要複製一次陣列。
這邊以Java的ArrayList程式碼為例：

public void add(int index, E e) {
     checkBoundInclusive(index);
     modCount++;
     if (size == data.length)
       ensureCapacity(size + 1);
     if (index != size)
       System.arraycopy(data, index, data, index + 1, size - index);
     data[index] = e;
     size++;
}

這邊容易被大家忽略的是，很多人以為LinkedList插入的複雜度是O(1)，但是其實是O(n)，為什麼呢？因為對LinkedList來說，他要插入只需要花O(1)這點沒有問題，但是要尋找插入點，還是必須要從開頭開始去走訪到指定的位置，這點非常重要。
這邊以Java的LinkedList程式碼為例：

public void add(int index, T o) {
     checkBoundsInclusive(index);
     Entry<T> e = new Entry<T>(o);
 
     if (index < size)
       {
         modCount++;
         Entry<T> after = getEntry(index);
         e.next = after;
         e.previous = after.previous;
         if (after.previous == null)
           first = e;
         else
           after.previous.next = e;
         after.previous = e;
         size++;
       }
     else
       addLastEntry(e);
}

開頭插入/刪除資料
Array：O(n)
LinkedList：O(1)
補充：
Array由於儲存位置無法更動，因此需要另外複製一份來存放資料。
這邊以Java的ArrayList程式碼為例，可看出新增方式：

public void add(int index, E e) {
     checkBoundInclusive(index);
     modCount++;
     if (size == data.length)
       ensureCapacity(size + 1);
     if (index != size)
       System.arraycopy(data, index, data, index + 1, size - index);
     data[index] = e;
     size++;
}

LinkedList只有儲存開頭的位置，所以可以輕鬆新增刪除。
這邊以Java的LinkedList程式碼為例，可看出新增開頭的方式：

public void addFirst(T o) {
     Entry<T> e = new Entry(o);
 
     modCount++;
     if (size == 0)
       first = last = e;
     else
       {
         e.next = first;
         first.previous = e;
         first = e;
       }
     size++;
}

結尾插入/刪除資料
Array：O(1)
LinkedList：O(n)
補充：
Array只需要將capacity加1，並且新增資料即可。
這邊以Java的ArrayList程式碼為例，可看出新增方式：

public void add(int index, E e) {
     checkBoundInclusive(index);
     modCount++;
     if (size == data.length)
       ensureCapacity(size + 1);
     if (index != size)
       System.arraycopy(data, index, data, index + 1, size - index);
     data[index] = e;
     size++;
}

LinkedList只有儲存開頭的位置，所以要從頭開始走訪到結尾才可以新增刪除資料。
這邊以Java的LinkedList程式碼為例，可看出新增開頭的方式：

public void addLast(T o) {
     addLastEntry(new Entry<T>(o));
}
 
/**
* Inserts an element at the end of the list.
*
* @param e the entry to add
*/
private void addLastEntry(Entry<T> e) {
     modCount++;
     if (size == 0)
       first = last = e;
     else
       {
         e.previous = last;
         last.next = e;
         last = e;
       }
     size++;
}