資料結構筆記：陣列與列表

Published in

Dublin so code

6 min readJun 23, 2020

AC 演算法專攻班進入最後一週，心得滿滿，很感謝這次免費的課程讓我能夠真正了解演算法的用法以及如何解題，對我來說非常重要，希望接下來還能花更多時間進步。

資料結構必須了解三大部分：
1. 結構：許多資料結構在語言中不一定內建，需要自行撰寫，了解如何寫資料結構相當重要
2. 特性：此資料結構的優點缺點，什麼時候要使用？為什麼不使用其他資料結構？
3. 方法：哪些經常會使用的 API 可以自己實作或是語言內建，並且了解方法的時間與空間複雜度

陣列 Array

結構：
大部分語言內建，字串也是一種陣列。
特性：
以用 array[index] 來找出資料，O (1)。
方法：
Insert, Get, Delete, Size 都是常見 API，需要知道 Insert 資料到 Array 的 first index 要先複製一個 length + 1 的 Array ，再將每個 element 往後移一個 index，因此時間複雜度是 O(n)，空間複雜度是 O(1) ，搜尋、Delete的時間複雜度都是 O(n) ，大部分語言內建 array 的 size，不用逐一數長度，時間複雜度是 O (1)，如果資料已排序，則支援二分搜尋，時間複雜度 O(log n)。

結構：
藉由指標得到下一塊記憶體。
特性：
搜尋的時間複雜度是 O(N) ，知道正確記憶體位置，插入與刪除的時間複雜度是 O(1) 。
深究串列，其實串列是用陣列實作。一步一步釐清：

上圖：藉由指標得到下一塊記憶體。
中圖：指標是一個變數，儲存記憶體位址。
下圖：電腦記憶體是一條很長的陣列，串列其實是散落在陣列裡面。另外還需要一個變數記錄串列的開頭，不過這邊沒畫上去。

方法：
InsertAtEnd, InsertAtFirst, Delete, DeleteAtHead, Search 都是常見的 API， Search 時間複雜度是 O(n)，需要逐一搜尋 node 的 value。InsertAtFirst 時間複雜度 O(1) ，先 new 一個 node 再將 pointer 指向原先 List 的第一個 node。InsertAtEnd 時間複雜度 O(n)，需要先找到最後一個 node 再將此 node 的 pointer 指向 new node，如果預先設定 node.last 的 API 則時間複雜度為 O(1)，但需要消耗空間。Delete 特定 node ，時間複雜度 O(n)，需要先搜尋。DeleteAtHead 時間複雜度是 O(n)，需要使用遞迴從頭把 List 逐一刪除。

Array 與 Linked List 比較

Array

優點：

random access：只要利用index即可在O(11)時間對Array的資料做存取。
較Linked list為節省記憶體空間：因為Linked list需要多一個pointer來記錄下一個node的記憶體位置。
假設node之data項目為1byte的char，但是pointer項目卻要4bytes，這樣的資料結構就多花了4倍的記憶體空間在與真正要處理的資料無關的部分上，是個沒有效率的做法。

缺點：

新增/刪除資料很麻煩：若要在第一個位置新增資料，就需要O(N)時間把矩陣中所有元素往後移動。同理，若要刪除第一個位置的資料，也需要O(N)時間把矩陣中剩餘的元素往前移動。
若資料數量時常在改變，要時常調整矩陣的大小，會花費O(N)的時間在搬動資料(把資料從舊的矩陣移動到新的矩陣)。

適用時機：

希望能夠快速存取資料。
已知欲處理的資料數量，便能確認矩陣的大小。
要求記憶體空間的使用越少越好。

Linked list

優點：

新增/刪除資料較Array簡單，只要對O(1)個node(所有與欲新增/刪除的node有pointer相連的node)調整pointer即可，不需要如同Array般搬動其餘元素。
若是在Linked list的「開頭」新增node，只要O(1)。
若要刪除特定node，或者在特定位置新增node，有可能需要先執行O(N)的「搜尋」。
Linked list的資料數量可以是動態的，不像Array會有resize的問題。

缺點：

因為Linked list沒有index，若要找到特定node，需要從頭(ListNode *first)開始找起，搜尋的時間複雜度為O(N)。
需要額外的記憶體空間來儲存pointer。