鏈結串列(linked list)是由一連串的結構(由 struct 所建立的節點)所構成，每一個節點中都含有兩筆資料，分別為節點的內容和下一個節點的記憶體地址。
ADT可拆分為兩個部分，分別為資料結構，以及對於這一些資料結構的操作的規範。而ADT所表示的就是資料結構加上對於資料結構操作所形成的集合，例如我們會將堆疊(stack)稱做為一個資料結構，其中我們可以針對stack進行以下操作，分別為推入push，彈出pop，檢視最頂端的資料peek，而這一些操作，我們會有對應的規範。
ADT負責對於每一個操作進行規範，而並非如何時做出這一些操作。對於這些操作的實作方面是直接在主程式內進行實作，將每一個操作寫成函式，後續要重覆進行這些操作只需要透過呼叫這一些函式即可完成。
在前面我們儲存多筆數據時我們此用了陣列(array)進行儲存，而陣列的特點在於資料和資料之間是連續記憶體分布的，也因為這這個特性我們可以使用指標的偏移(offset)，或是直接查詢的方式找到陣列中的某一個數值，也可以透過這樣的方式得知整個陣列的長度，最後一個數值減去第一個數值，算初期記憶體偏移即可求出陣列的長度，而這些是陣列的優點
而陣列的缺點在於當我們要插入或是刪除數值時，我們需要移動陣列所有的元素來進行插入，而這麼做是十分低效率的
而這裡要介紹的鏈接串列，是由一連串在記憶體中不連續的結構所組成。每一個結構包含結構中的值和指向下一個結構的指標。
他的優點即是方便我們進行資料的插入與刪除，只要改變每一個節點中，指向的下一個節點可以完成插入，不需要移動整個串列就可以實現，避免刪除和插入所需耗費的線性時間。
而鏈結串列的缺點即是他無法直接查詢串列中的數值，我們也無法透過指標的偏移來查詢陣列中的元素，因為不連續記憶體分布的特性，我們必須將一個連接串列由頭走到尾才能夠找到我們想要尋找的數值，而得到鏈接串列的長度也是如此。
以C語言為例，一般來說會將含是ㄓ也就是.h檔案中，具體節點(Node)的宣告則放在.c檔案中，下面示範為鏈結串列的ADT。
#ifndef _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
#endif /* _List_H */
/*放入主程式中*/
struct Node
{
ElementType Element;
Position Next;
};
為了建立一個鏈結串列，我們首先要先建立鏈結列中的節點，而這裡我們每一個節點中包含節點中的數值和下一個節點的記憶體地址，使用結構宣告如下。
struct node{
int value;
struct node *next;
};
說明:成員next指向一個型別為node型別的指標。
我們回憶一下，指標變數就是儲存另外某個數據所在的記憶體的變數，因此，如果P被宣告成一個指向結構變數的指標，那麼P變數中的數值就是記憶體中的地址，在這個地址中可以找到結構變數。
這裡我們完成了鏈結串列節點的宣告，再來我們可以開始建立鏈結串列了，我們宣告第一個節點名稱為head來表示鏈結串列中的第一個節點。
struct head* first = NULL;
這裡把head的指向設為空指標表示鏈結串列初始為空。
下圖為鏈結串列加上指標的示意圖
在建立鏈結串列時，需要一個一個的建立節點，並把每一個節點和鏈結串列進行連結，而通常建立節點需要做三件事情
- 分配記憶體空間給節點
- 把數據儲存到節點中
- 把節點串連到鏈結串列上
為了建立節點，我們需要宣告一個臨時使用的變數指向建立的節點，直到該點連接到鏈結串列上
struct node *new_node
我們可以使用malloc得到記憶體空間，並將malloc回傳的指標儲存在next_node中，而現在next_node即指向到一塊由malloc所要求到的記憶體空間，並且這一個記憶體空間剛好可以放下一個node的大小
new_node = malloc(sizeof(node) * 1);
sizeof為該型別所佔的記憶體大小，而不是該指標所指向型別所佔的記憶體大小，所以是sizeof(node)，而不是sizeof(new_node)
接下來把數據儲存到新的節點中
new_node->value = 10;
或是
(*new_node).value = 10;
這裡使用括號的原因為 . (結構成員運算子)的優先順序大於 * (結構指標運算子)
接著，將new_node所指向的下一個節點設為NULL，避免不當操作導致記憶體溢位的問題發生
new_node->next = NULL;
我們可以使用結構指標運算子來存取結構中的成員，利用指標存取結構是一種非常普遍的做法，以至於後來C語言針對這個做法提供了一種特殊的運算符，稱為結構指標運算子，由一個減號 - 和一個 > 所構成，於是構成了上面所介紹的這種寫法
new_node->value = 10;
先對new_node進行間接尋址，然後再選擇成員value
int IsEmpty(struct node* head)
{
return head->next == NULL;
}
如果為真則回傳1，表示true。
int IsLast(struct node* p)
{
return p->next == NULL;
}
如果為真則回傳1，表示true。
在搜尋鏈結串列時，我們只要將一個指到鏈結串列頭的指標傳入函式，在函式內使用next走訪整個鏈結串列即可，時間複雜度為一個線性時間，跟隨著鏈結串列的長度而決定。
我們上面建立了一個鏈結串列，我們可能會遇到需要搜尋鏈結串列上某一個節點的情況。雖然使用while迴圈可以用來搜尋鏈結串列，但一般來說使用for迴圈居多，對於有計數(counting)操作時，習慣使用for迴圈，且使用for迴圈也有利於我們對鏈結串列進行其他操作，下面是一種搜尋鏈結串列的常見方法，使用了指標p來追蹤'目前'的節點。
for(NODE* p = first; p != NULL; p = p->next)
p = p->next即是移動到下一個節點。
下面我們建立一個名稱為search_list的函式，這個函數為了找到某一個整數n而遍歷整個鏈結串列，如果找到整數n，則回傳整數n所在的節點的指標，否則，回傳空指標，範例如下
struct node* search_list(struct node* head, int n)
{
struct node* p;
for(p = head; p != NULL; p = p->next)
{
if(p->value == n)
{
return p;
}
}
return NULL;
}
而下面是在不使用指標p，直接使用head進行搜尋
struct node* search_list(struct node* head, int n)
{
for(;head != NULL; head = head->next)
{
if(head->value == n)
{
return head;
}
}
return NULL;
}
這裡可以這樣使用是因為傳入函式的head是原始鏈結串列指標的複製品，所以在函式內改變他不會造成影響。
而使用while迴圈實做搜尋鏈結串列的方式可以使用下面程式進行表示
LIST-SEARCH(L.k)
x = L.head
while X != NULL and x.key != k
x = x.next
return x
struct node* search_list(struct node* L, int val)
{
struct node* p = L;
while (p != NULL && p->value != val)
{
p = p->next;
}
return p;
}
我們宣告一個指向節點(結構)的指標變數p，使用p用來遍歷整個鏈結串列，當p找到我們要尋找的數值存在的節點(第一次出現的數字，有可能後面也有節點是我們要找的數字)，那麼回傳該節點的指標。
我們在先前提到過，要刪除陣列中的數據是一件非常麻煩的事情，而在鏈結串列中卻是一件十分容易的事情，而刪除節點就如同建立節點依樣需要三個步驟
- 定位要刪除的節點
- 改變前一個節點，使他繞過刪除的節點
- 呼叫free函式釋放刪除的節點所佔用的記憶體空間
如果第一步我們使用搜尋鏈結串列的方法進行實作，那麼將會在指標指向要刪除的節點時停止搜尋，我們就無法執行第二步，改變前一個節點了，針對這個問題，有一種解決方法。
我們使用指標追蹤來實現，具體如下
在第一步搜尋整個鏈結串列時，保留一個指向前一個節點的指標(previous)，還有指向目前節點的指標(currrent)。如果list指向到要搜尋的鏈結串列的頭，並且n是要刪除的整數，那麼下面的迴圈就可以實現第一步
for(cur = list, prev = NULL; cur != NULL && cur->value != n; prev = cur, cur = cur->next)
到這裡我們也可以看出一件事情，也就是使用for迴圈的方便之處，直接在迴圈敘述中執行想要的操作，當循環停止時，cur指向要刪除的節點，而prev指向前一個節點，下面會演示整個流程
假設有一鏈結串列，含有30,40,20,10
假設我們想要刪除的整數為20，那麼目標就是刪除第三個節點，在執行完cur = list, prev= NULL之後，cur指向鏈結串列中第一個節點
接著進入for迴圈的條件判斷，cur目前正指向節點30，因此cur != NULL成立，cur->value != n，這裡cur指向節點的值為30，但目標為20，因此條件成立。兩個條件皆成立，執行prev = cur, cur = cur->next後，我們會看到指標prev追蹤在cur的後方。
再次進入for迴圈中的條件判斷，cur目前正指向節點40。因此cur != NULL成立，cur->value != n，這裡cur指向節點的值為40，但目標為20，因此條件成立。兩個條件皆成立，執行prev = cur, cur = cur->next
再次進入for迴圈中的條件判斷，cur目前正指向節點20，因此cur != NULL成立，cur->val != n，這裡cur指向的節點值為20，目標為20，此條件不成立。兩者條件需要皆成立才會執行for迴圈的動作，因此for迴圈終止。接下來，根據步驟2，改變前一個節點，使他繞過刪除的節點，為以下操作
prev->next = cur->next使前一個節點中的指標指向了目前指標後面的節點
接著進行步驟3，釋放目前節點(指向要刪除的節點)的記憶體空間free(cur);
而下面的函式所使用的策略就如同上面所演示，在給定指向鏈結串鍊的指標，和要刪除的整數n，delete_from_list就會刪除含有n的第一個節點(有可能很多節點都含有整數n)。如果沒有結點包含整數n，則函式甚麼都不做，無論哪一種情況，皆會回傳指向鏈結串列的指標。
struct node* delete_from_list(struct node* list, int n)
{
struct node *cur, *prev;
for(cur = list, prev = NULL; cur != NULL && cur->value != n; prev = cur, cur = cur->next);
if(cur == NULL)
{
return list;
}
if(prev == NULL)
{
list = list->next;
}
else
{
prev->next = cur->next;
}
free(cur);
return list;
}
另一種作法為使用搜尋結點的函式，可以將刪除節點的函式寫得更加簡化，同樣的，傳入的鏈結串列第一個節點為空結點。
void list_delete(NODE *L, int val)
{
NODE *target = search_list(L, val);
NODE *temp = NULL;
for (temp = L; temp->next != target; temp = temp->next);
temp->next = target->next;
free(target);
}
參考資料: 大話數據結構，C语言程序设计现代方法第2版，Introduction of algorithms 3rd，圖片源於網路
iThome鐵人賽
看影片追技術