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

兩者主要差異

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

  1. Array是index based的結構,LinkedList則是Reference based。
  2. Array會存在sequential memory locations,LinkedList則是sequence of the elements,每一個element都會link下一個element。
  3. Array裡面會儲存同樣結構的資料,可以是Primitive Data Type或是Object Data Type,LinkedList裡面每個儲存的Object都會包含Data與Link。
  4. Array可以先宣告要多大的空間,LinkedList則不受限。
  5. 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:

  1. Linear Search, O(n)
  2. Binary Search, O(log(n))

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

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

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

記憶體使用

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

複雜度分析

  1. 浪費空間 (wasted space)
    Array:O(1)
    LinkedList:O(n)
    補充:Array的資料儲存較集中,LinkedList儲存較分散。

  2. 存取資料
    Array:O(1)
    LinkedList:O(n)
    補充:Array通常因為這個原因,而被大家採用。
    Array存取資料為Random Access,LinkedList必須從頭開始找。
    Array回傳只需要data[index]即可

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

1
2
3
4
public E get(int index) {
checkBoundExclusive(index);
return data[index];
}

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

1
2
3
4
public T get(int index) {
checkBoundsExclusive(index);
return getEntry(index).data;
}
  1. 中間插入/刪除資料
    Array:O(n)
    LinkedList:O(n)
    補充:LinkedList通常因為這個原因,而被大家採用。
    Array每次要插入元素,必須要複製一次陣列。
    這邊以Java的ArrayList程式碼為例:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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程式碼為例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);
}
  1. 開頭插入/刪除資料
    Array:O(n)
    LinkedList:O(1)
    補充:
    Array由於儲存位置無法更動,因此需要另外複製一份來存放資料。
    這邊以Java的ArrayList程式碼為例,可看出新增方式:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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程式碼為例,可看出新增開頭的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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++;
}
  1. 結尾插入/刪除資料
    Array:O(1)
    LinkedList:O(n)
    補充:
    Array只需要將capacity加1,並且新增資料即可。
    這邊以Java的ArrayList程式碼為例,可看出新增方式:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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程式碼為例,可看出新增開頭的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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++;
}

結論

根據資料結構的特性,使用時機也不同
Array:

  1. 已知資料需要多大的空間儲存。
  2. 希望快速存取資料。
  3. 節省記憶體空間。

LinkedList:

  1. 資料大小不確定。
  2. 需要時常新增刪除資料。
  3. 不在乎存取資料的速度。

補充:
Doubly LinkedList可解決部分LinkedList先天上的不足。
至於是解決什麼地方,就當作是大家的回家作業吧!

參考資料

  1. ArrayList
  2. LinkedList