電腦科學 ^ IT人生 ^ 公益課程

#10 資料結構 List

List 一般稱為 Linked List,這樣稱呼是因為在 List 裡面的每個元素都是一個連結連到下一個元素,這也稱為單向的 Linked List,如下圖所示:


這種單向的 List 應用在許多的情況下,例如作業系統的檔案寫入到硬碟時所採用的方式就是這樣單向 List 的概念.每個 List 都是由一個或多個元素所組成,而每個元素都有相同的資料結構,以上圖為例,元素裡包含了一個 decimal 和一個 pointer,這個指標所代表的是下一個元素的記憶體位址.所以,如果你要找 List 裡一共有多少元素時,就必須要從第一個元素一直移動到最後一個元素才能得知這個 List 一共有多少的元素.如果要尋找 List 中是不是有某一個元存在,唯一的方法也是得從第一個元素開始,然後沿著 pointer 到下一個元素一直找到最後.以上的動作若用 Big O 來表達都是 O(n),其中 n 是元素的個數.

顯然跟 Array 比起來,List 在數元素的個數和尋找元素都慢了許多,但 List 也有其優點,由於 List 裡的元素之間是透過 pointer 來指向下一個元素的位址,所以下一個元素的位址可以隨意變更.也就是說當你想要插入或刪除一個元素到 List,這動作就變得相當有簡單.


上圖就是一個刪除元素的結果,只要把 pointer 指向到下下一個元素時,略過中間那一個元素就可以了,最後記得把中間元素從記憶體中釋放即可.其程式碼看起來如下:

nextNode = currentNode.next;
currentNode.next = currentNode.next.next;
free(nextNode);

如果新加入一個元素的話,其程式碼看起來如下:

ListNode newNode = new ListNode();
newNode.next = currentNode.next;
currentNode.next = newNode;

以上兩段程式碼中的 next 就是 pointer 所指向下一個元素的記憶體位址.由於 List 中的元素在實體的記憶體或硬碟空間中不需要相鄰在一起,因此讓插入元素和刪除元素的動作變得簡單.

Share: