鏈結串列

Linked List

https://en.wikipedia.org/wiki/File:Singly-linked-list.svg

結構

Linked list在操作上的彈性讓他可以被用來實現多種資料結構，像是先前提過的stack, queue或是tree都可以。

Note: 前面stack與queue在範例當中都是使用array來實作，這邊則是直接用pointer來指向下個節點(node)。

因為鏈結串列是由許多結構相同的節點(node)串在一起形成的，因此我們在宣告時只要定義好一個節點就可以了，其結構包含:

1. data: 可以根據需求是任意的資料型態。
2. *next: 資料型態為node，因為next指向下一個節點，而節點的資料型態為node。在宣告時注意必須要遞迴宣告(也就是*next的型態必須和node相同)

操作

在結構的操作上可以把資料存進串列裡，也可以將資料取出。需要特別注意的是，在操作時每個節點的位址(address)都必須有人指著，以避免記憶體流失(memory leakage)，因為單向的串列只能由前一個節點指向後一個節點，因此一旦串列中斷就無法再找回該節點所在的記憶體位址。

Note: 這部份似乎就沒有特定的稱呼 add, new, insert, delete, free, remove都有，這邊用的是insert跟 free。

• insert: 新增一個節點至串列當中，可以根據需求調整函式將新的節點加在串列中的任意位置。

https://en.wikipedia.org/wiki/File:CPT-LinkedLists-addingnode.svg

• free: 也可以視需求移除串列中的任意位置。

https://en.wikipedia.org/wiki/File:CPT-LinkedLists-deletingnode.svg

Note: 因為 insert跟 free都可以使用在串列中的任何位置，所以會有很多種寫法。由於單向串列的特性通常會寫成 insert_after與 free_after較為通用。

https://en.wikipedia.org/wiki/File:Circularly-linked-list.svg

範例

以下為C語言實作的linked list以及相關函式的宣告範例。