【數據結構】鏈表（linked list）

一、鏈表的介紹

二、單鏈表

1. 單鏈表的初始化

2. 單鏈表的插入

（1）動態申請一個節點

（2）頭插法

（3）尾插法

（4）按照位置來插入

（5）在地址之前插入

（6）在地址之后插入

3. 單鏈表的建立

（1）頭插法建立單鏈表

（2）尾插法建立單鏈表

4. 單鏈表的刪除

（1）頭刪

（2）尾刪

（3）按位置刪

（4）刪除當前地址的結點

（5）刪除當前地址之后的結點

5. 單鏈表的查找

（1）查找結點地址

（2）單鏈表的按位查找

（3）單鏈表的按值查找

6、單鏈表的銷毀

三、雙鏈表

1. 申請新結點

2. 初始化

3. 雙鏈表的插入

4. 雙鏈表的建立

4. 雙鏈表的刪除

5. 雙鏈表的打印

6. 雙鏈表的銷毀

四、總結

一、鏈表的介紹

????????我們知道線性表的順序存儲結構稱為順序表，那么線性表的鏈接存儲結構則稱為鏈表。鏈表是一種物理存儲結構上非連續、非順序的存儲結構，它可以用任意存儲單元存放線性表的元素，在寫存儲單元可以連續，也可以不連續，甚至可以零散分布在內存中的任意位置。二為了表示元素之間的邏輯關系，每個存儲單元在存儲數據元素的同時，還必須存儲官該元素的后繼元素地址信息，所以數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。

鏈表結構示意圖：

鏈表的分類：

實際中鏈表的結構非常多樣，但總體上可以分為6種基礎鏈表結構，它們可以相互可以組成共8種鏈表：

按方向：

按有無頭結點（也叫做有無哨兵結點）：

按循環：

結構最簡單的? 是無頭的單向非循環單鏈表；
結構最復雜的? 是有頭的雙向循環鏈表。

????????而下面要詳細介紹的是無頭的單向非循環單鏈表。因為無頭的單向非循環單鏈表結構比較簡單，但一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。實際應用得比較多，比如一些OJ題。

? ? ? ? 也要介紹有頭的雙向循環鏈表，因為這種鏈表一般會用在單獨存儲數據。而實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表。這個結構雖然結構復雜，但也有許多優勢，比較好實現。

二、單鏈表

下面的單鏈表是指無頭的單向非循環單鏈表。

????????單鏈表是通過一個一個的結點來存儲數據的，每個結點結構只含有一個數據域和一個指針域，數據域用來存儲數據，指針域用來存儲下一個結點的地址。

下面是單鏈表結點的定義：

typedef int DataType;
typedef struct ListNode
{DataType data;//數據域struct ListNode* next;//指針域
}Node;

結構示意圖：

1. 單鏈表的初始化

這種無頭的單向非循環單鏈表的初始化比較簡單，只需要生成一個空的結點指針即可以了。即：

SListNode* first = NULL;

2. 單鏈表的插入

單鏈表的插入有多種方法：頭插法、尾插法、中間插。其中中間插入又包含了可以按照位置（所在的次序）來插入和按照結點地址（指針）來插入兩種情況。

（1）動態申請一個節點

想要插入，就必須要先申請一個新的結點，用來存放要插入的值。加入要插入一個值為x的數據，那么現在就需要申請一個單鏈表結點，其中的數據域用來存放值x，指針域先置空。則C語言實現如下：

//動態申請一個值為x的結點空間
Node* ApplyNode(DataType x)
{//申請空間Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL){perror("malloc fail\n");return NULL;}//賦值newNode->data = x;newNode->next = NULL;return newNode;
}

（2）頭插法

頭插法即是在鏈表的表頭進行插入。對于無頭的單向非循環單鏈表的頭插法，分為兩種情況：空表和非空表。但對于這里而言，它們是一樣的代碼。由于初始化時傳遞到是一個空的結點指針，這里頭插函數傳遞的就應該是一個指向該空結點的地址（傳二級指針），因為這里要改變頭指針的值，所以必須使用傳址調用。

需要注意的是，當生成了一個新結點后，必須先將新結點中的指針域部分進行賦值，即：“?newNode->next = *phead ”，再將頭指針指向這個新結點，即：“ *phead = newNode;? ”。

C語言實現如下：

// 單鏈表的頭插
void PushFront(Node** phead, DataType x)
{assert(phead);//由于這里的phead是頭指針的地址，所以一定不為空，需斷言Node* newNode = ApplyNode(x);//產生新結點newNode->next = *phead;*phead = newNode;
}

（3）尾插法

尾插法是指在鏈表的表尾依次插入。尾插法就必須分為兩種情況：空表和非空表，它們的情況是不同的。對于空表，由于只有一個空指針，所以只需要將申請的新結點的地址賦值給它就行了；對于非空表，就需要找到這個鏈表最后一個結點的地址：假設為tail，然后將申請的新結點地址賦給該結點的指針域。

則C語言實現如下：

//單鏈表尾插
void PushBack(Node** phead, DataType x)
{assert(phead);//這里phead指的是頭指針的地址，它一定不為空，所以必須斷言Node* newNode = ApplyNode(x);if (*phead == NULL){*phead = newNode;}else{//找尾Node* tail = *phead;while (tail->next != NULL){tail = tail->next;}tail->next = newNode;}
}

（4）按照位置來插入

按照位置來插入和順序表的插入差不多。就是先給定一個位置（第幾個位置，即一個整數），在這個位置插入所給的元素值x。

則C語言實現如下：

//在第i個位置插入x
void ListPush(Node** phead, int i, DataType x)
{assert(phead);Node* newNode = ApplyNode(x);if (*phead == NULL && i == 1 ){//空表的處理*phead = newNode;return;}Node* prev = NULL;Node* cur = *phead;int count = 1;while (cur&&count < i){prev = cur;cur = cur->next;count++;}if (cur == NULL){printf("插入位置不合理，插入失敗！\n");return;}newNode->next = cur;prev->next = newNode;
}

（5）在地址之前插入

給定一個地址pos，在該地址之前插入一個新結點。

則C語言實現如下：

//在pos的前面插入
void InsertBefore(Node** phead, Node* pos, DataType x)
{assert(phead);assert(pos);if (pos == *phead){//頭插PushFront(phead, x);}else{Node* prev = *phead;while (prev->next != pos){prev = prev->next;}Node* newNode = BuySListNode(x);newNode->next = pos;prev->next = newNode;}
}

（6）在地址之后插入

給定一個地址pos，在該地址之后插入一個新結點。

則C語言實現如下：

//在pos的后面插入
void InsertAfter(Node** phead, Node* pos, DataType x)
{assert(phead);assert(pos);if (pos == *phead){//頭插PushFront(phead, x);}else{Node* cur = *phead;while (cur != pos){cur = cur->next;}Node* newNode = ApplyNode(x);newNode->next = pos->next;cur->next = newNode;}
}

3. 單鏈表的建立

????????建立單鏈表有兩種方法：頭插法和尾插法。知道了單鏈表的插入方法，那么建立方法也就和簡單了。這里假設要將一個數組的數據依次插入到鏈表中去。

（1）頭插法建立單鏈表

還未建立單鏈表之前，只有一個空的頭指針，所以建立單鏈表只需順序遍歷數組，利用單鏈表的插入的頭插法函數將數組的數據依次傳入就可以了。則C語言實現如下：

//單鏈表的建立--頭插法建立
void CreatListByFront(Node** phead, DataType arr[], int sz)
{for (int i = 0; i < sz; i++){//通過頭插法建立PushFront(phead, arr[i]);}
}

（2）尾插法建立單鏈表

和頭插法建立單鏈表一樣，調用尾插法的函數就可以實現尾插法建立單鏈表了。則C語言實現如下;

//單鏈表的建立--尾插法建立
void CreatListByBack(Node** phead, DataType arr[], int sz)
{for (int i = 0; i < sz; i++){//通過尾插法建立PushBack(phead, arr[i]);}
}

4. 單鏈表的刪除

和插入一樣，刪除也有多種情況。

（1）頭刪

????????頭刪即刪除鏈表中的第一個結點，這里要注意的是必須將要刪除的結點的空間釋放，否則會出現內存泄漏。

頭刪需要注意的是所刪除的鏈表一定不能是空鏈表，所以在對所傳遞的二級指針（存放頭指針地址指針）進行斷言的同時，也要對頭指針是否為空進行斷言操作。則C語言實現如下：

//單鏈表頭刪
void PopFront(Node** phead)
{assert(phead);assert(*phead);Node* first = *phead;*phead = (*phead)->next;free(first);//釋放第一個結點的空間first = NULL;
}

（2）尾刪

和頭刪一樣，需要斷言頭指針和存放頭指針的地址的二級指針。尾刪也需要考慮空表的情況，然后將最后的一個結點刪除。因為空表是進行無法刪除操作的。這里也必須將所刪結點的空間釋放，并將所刪結點的上一個結點的指針域置空。

但是要刪除最后一個結點就必須找到倒數第二個結點的地址，如果當鏈表只有一個結點的情況倒數第二個結點的地址就無法找到，那么就可以只返回一個空指針NULL就可以了。則C語言實現如下：

// 單鏈表的尾刪
void PopBack(Node** phead)
{assert(phead);assert(*phead);if ((*phead)->next == NULL){*phead = NULL;}else{Node* prev = NULL;Node* tail = *phead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

（3）按位置刪

給一個位置 i，刪除第 i 個位置，C語言實現如下：

//刪除第i個位置的結點（0<i）
void Delete(Node** phead, int i)
{assert(phead);assert(*phead);if (i == 1){PopFront(phead);//頭刪return;}Node* cur = *phead;Node* prev = NULL;int count = 1;while (cur != NULL && count < i){prev = cur;cur = cur->next;count++;}	if (cur == NULL){printf("刪除位置不合理\n");}else{prev->next = cur->next;free(cur);cur = NULL;}
}

（4）刪除當前地址的結點

給定鏈表中的一個結點地址，該地址可以通過單鏈表的查找中的查找地址來獲得，然后將這個結點刪除，則C語言實現如下：

//刪除pos位置
void Delete(Node** phead, Node* pos)
{assert(phead);assert(pos);if (pos == *phead){//頭刪PopFront(phead);}else{Node* prev = *phead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

（5）刪除當前地址之后的結點

給定鏈表中的一個結點地址，刪除該結點之后的一個結點，。C語言實現如下;

//單鏈表刪除pos位置之后的結點
void DeleteAfter(Node* pos)
{assert(pos);Node* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

5. 單鏈表的查找

查找的方式也分多種，一種是給定值來查找鏈表結點的地址，這是單鏈表最主要的查找，另一種則是和順序表的按位查找一樣，當然也還有和順序表一樣的按值查找。

（1）查找結點地址

查找值為x的結構體地址，則C語言實現如下：

//單鏈表查找，查找值為x的結構體地址
Node* ListFind(Node* head, DataType x)
{Node* cur = head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

（2）單鏈表的按位查找

//按位查找
DataType ListGet(Node* head, int i)
{assert(head);Node* cur = head;int count = 1;while (cur && count < i){cur = cur->next;count++;}if (cur == NULL){printf("位置不合理，查找失敗\n");return EOF;}return cur->data;
}

（3）單鏈表的按值查找

/按值查找
DataType ListLocate(Node* head, DataType x)
{assert(head);Node* cur = head;int count = 1;while (cur){if (cur->data == x){return count;}cur = cur->next;count++;}printf("鏈表中不存在該元素\n");return -1;
}

6、單鏈表的銷毀

通過遍歷單鏈表，逐步銷毀各個結點。C語言實現如下：

//單鏈表的銷毀
void Destroy(Node** phead)
{Node* cur = *phead;while (cur){Node* tmp = cur->next;free(cur);cur = tmp;}*phead = NULL;
}

三、雙鏈表

在這里要介紹的是帶頭雙向循環鏈表。這是圖示：

它的結點結構體定義：

typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//存儲數據struct ListNode* prev;//指向前一個結點的指針 --- 前驅指針域struct ListNode* next;//指向后一個結點的指針 --- 后繼指針域
}ListNode;

以下是帶頭雙向循環鏈表中的比較重要的操作。

1. 申請新結點

給定一個值x，向內存申請一個新的雙鏈表的結點結構體指針將x存儲。這里需要注意的是需要將新結點的前驅指針域和后繼指針域都置空，防止野指針。C語言實現如下：

//建立一個結點
ListNode* ApplyNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");return NULL;}node->prev = NULL;node->next = NULL;node->data = x;return node;
}

2. 初始化

帶頭雙向循環鏈表，由于是帶哨兵位頭結點的所以需要初始化。該類型的初始化是將哨兵位頭結點的前驅指針域和后繼指針域都指向它自己。并將產生的結點返回。C語言實現如下：

//初始化
ListNode* ListInit()
{ListNode* phead = ApplyNode(-1);//假設給個-1phead->prev = phead;phead->next = phead;return phead;
}

3. 雙鏈表的插入

雙鏈表的插入只需要完成下圖中的4個操作就可以了。

C語言實現如下：

//雙向鏈表在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = ApplyNode(x);newnode->prev = pos->prev;//1pos->prev->next = newnode;//2newnode->next = pos;//3pos->prev = newnode;//4
}

由于這是帶頭循環鏈表，所以由此可以得到頭插和尾插：

// 雙向鏈表頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{ListInsert(pHead->next, x);
}
// 雙向鏈表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{ListInsert(pHead, x);
}

4. 雙鏈表的建立

建立雙鏈表只需要將給定數組的元素逐步插入即可。C語言實現如下：

//建立雙鏈表鏈表
void ListCreate(ListNode* pHead, LTDataType arr[], int sz)
{assert(pHead);for (int i = 0; i < sz; i++){ListInsert(pHead, arr[i]);}
}

4. 雙鏈表的刪除

雙鏈表的刪除只需要完成下圖中的4個操作就可以了。

C語言實現如下：

// 雙向鏈表刪除pos位置的節點
void ListErase(ListNode* pos)
{assert(pos);ListNode* tmp = pos;pos->prev->next = pos->next;//1pos->next->prev = pos->prev;//2
}

那么，也可以得到頭刪和尾刪：

// 雙向鏈表頭刪
void ListPopFront(ListNode* pHead)
{ListErase(pHead->next);
}// 雙向鏈表尾刪
void ListPopBack(ListNode* pHead)
{ListErase(pHead->prev);
}

5. 雙鏈表的打印

打印需要遍歷鏈表，以再次回到頭結點轉為終止條件。C語言實現如下：

// 雙向鏈表打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){printf("%d", cur->data);cur = cur->next;}printf("\n");
}

6. 雙鏈表的銷毀

遍歷雙鏈表，逐步釋放空間，以再次回到哨兵頭結點作為停止條件。C語言實現如下：

// 雙向鏈表銷毀
void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* next = cur->next;free(cur);cur = next;}free(pHead);
}

雖然雙鏈表的結構比較復雜，但它的代碼都簡單，比較好實現。