一.前情回顧

上篇文章講述了動態順序表及其實現，我們知道了動態順序表在物理結構上是連續的，因此我們也認識到它的缺點：
①如果空間不足需進行增容，付出一定的性能消耗，并且可能存在一定的空間浪費。
②在進行某些插入或刪除操作時，需要大量移動數據。這是因為相鄰數據元素在物理存儲結構上也是連續存儲的，中間沒有空隙。

因此本篇文章將講述線性表的另一種表示方法：鏈表。

二.鏈表的概念

鏈表，即線性表的鏈式實現，指用一組任意連續或者不連續的存儲單元存儲數據，通過指針像鏈條一樣鏈結各個元素的一種存儲結構。
如圖所示：

因此，對于每個數據元素，除了要存儲自身信息，也要存儲后繼（下一個）數據元素的信息。這兩部分合起來被稱為結點。
每個結點包含兩個域，一個是數據域：存儲數據元素的信息；另一個是指針域：存儲后繼元素的位置信息。n個結點鏈結成一個鏈表。如圖所示：

對于線性表，總要有頭有尾，我們把鏈表中第一個結點的存儲位置叫做頭指針，最后一個結點置為NULL。由于每個結點的指針域只包含一個指向后繼位置的指針，因此該鏈表又稱單鏈表（單向鏈表）。

三.鏈表的實現

1.鏈表結點的結構：

在C語言中用結構體指針來存儲后繼結點的信息。

typedef int SLDataType;//結點的結構體
typedef struct SListNode
{SLDataType data;//數據域struct SListNode* next;//指向下一個結點的指針域，所以指針類型應該為struct SListNode*
}SLTNode;//起別名，將struct SListNode簡寫成SLTNode

2.申請新結點函數：

因為在插入操作中需要頻繁申請結點，因此可以將申請結點的操作封裝成一個函數。

//申請新結點
SLTNode* BuySListNode(SLDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;return NewNode;
}

3.尾插函數：

需要特別注意的是，凡是涉及修改鏈表，必須傳二級指針，因為鏈表本身是用每個結點的指針鏈結而成的，作為參數傳遞時是一級指針，再將每個結點的地址作為實參傳遞，這是二級指針。

//尾插函數
//需要傳二級指針，否則形參的改變不影響實參
void SListPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);//不能傳空地址，否則解引用找鏈表頭結點會報錯//創建新結點SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;//鏈表為空，直接插入if (*pphead == NULL){*pphead = NewNode;}else{//需要找到最后一個結點才能尾插，因此先用一個cur結點標記當前所在位置SLTNode* cur = *pphead;while (cur->next != NULL)//循環結束走到最后一個結點{cur = cur->next;//讓cur遍歷到最后一個結點}if (NewNode == NULL){perror("malloc fail!");exit(1);}cur->next = NewNode;}
}

4.頭插函數：

//頭插函數
void SListPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);//創建新結點SLTNode* NewNode = BuySListNode(x);NewNode->next = *pphead;*pphead = NewNode;
}

5.尾刪函數：

//尾刪函數
void SListPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//如果只有一個結點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL)//需要找到倒數第二個結點才能刪除最后一個結點{cur = cur->next;}SLTNode* tmp = cur->next;free(tmp);tmp = NULL;cur->next = NULL;}
}

6.頭刪函數：

//頭刪函數
void SListPopFront(SLTNode** pphead)
{assert(pphead&&*pphead);//鏈表為空時不能刪除SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}

7.在指定結點之前插入：

//在指定結點之前插入函數
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);//需要找到指定結點的前一個結點SLTNode* prev = *pphead;//可能第一個結點就是指定結點，此時相當于頭插if (prev == pos){//直接調用頭插函數SListPushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;}SLTNode* NewNode = BuySListNode(x);NewNode->next = prev->next;prev->next = NewNode;}
}

8.在指定結點之后插入：

//在指定結點之后插入函數
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* NewNode = BuySListNode(x);NewNode->next = pos->next;pos->next = NewNode;
}

8.刪除指定結點：

//刪除指定結點
void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* prev = *pphead;//如果第一個結點就是要刪除的結點if (prev == pos){//直接調用頭刪SListPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}SLTNode* tmp = prev->next;//tmp即要刪除的結點prev->next = tmp->next;free(tmp);tmp = NULL;}
}

9.查找函數：

//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}//沒找到或鏈表為空時，返回空指針return NULL;
}

10.銷毀鏈表：

//銷毀鏈表函數
void SListDestory(SLTNode** pphead)
{assert(pphead && *pphead);while (*pphead != NULL){SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;}
}

四.全部源代碼實現

1.頭文件（聲明動態順序表的結構，操作等，起到目錄作用）：

SList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;//結點的結構體
typedef struct SListNode
{SLDataType data;//數據域struct SListNode* next;//指向下一個結點的指針域，所以指針類型應該為struct SListNode*
}SLTNode;//起別名，將struct SListNode簡寫成SLTNode//打印函數（方便調試）
void SListPrint(SLTNode* phead);//申請新結點
SLTNode* BuySListNode(SLDataType x);//尾插函數
void SListPushBack(SLTNode** pphead, SLDataType x);//需要傳二級指針，否則形參的改變不影響實參//頭插函數
void SListPushFront(SLTNode** pphead, SLDataType x);//尾刪函數
void SListPopBack(SLTNode** pphead);//頭刪函數
void SListPopFront(SLTNode** pphead);//在指定位置之前插入函數
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);//在指定位置之后插入函數
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x);//刪除指定結點
void SListErase(SLTNode** pphead, SLTNode* pos);//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x);//銷毀鏈表函數
void SListDestory(SLTNode** pphead);

2.源文件（具體實現各種操作）：

SList.c

#include"SList.h"//打印函數（方便調試）
void SListPrint(SLTNode* phead)
{assert(phead);SLTNode* cur = phead;while (cur != NULL)//循環結束走到空結點{printf(" %d ->", cur->data);cur = cur->next;}printf("NULL\n");
}//申請新結點
SLTNode* BuySListNode(SLDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));NewNode->data = x;NewNode->next = NULL;return NewNode;
}//尾插函數
//需要傳二級指針，否則形參的改變不影響實參
void SListPushBack(SLTNode** pphead, SLDataType x)
{assert(pphead);//不能傳空地址，否則解引用找鏈表頭結點會報錯//創建新結點SLTNode* NewNode = BuySListNode(x);//鏈表為空，直接插入if (*pphead == NULL){*pphead = NewNode;}else{//需要找到最后一個結點才能尾插，因此先用一個cur結點標記當前所在位置SLTNode* cur = *pphead;while (cur->next != NULL)//循環結束走到最后一個結點{cur = cur->next;//讓cur遍歷到最后一個結點}if (NewNode == NULL){perror("malloc fail!");exit(1);}cur->next = NewNode;}
}//頭插函數
void SListPushFront(SLTNode** pphead, SLDataType x)
{assert(pphead);//創建新結點SLTNode* NewNode = BuySListNode(x);NewNode->next = *pphead;*pphead = NewNode;
}//尾刪函數
void SListPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//如果只有一個結點if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL)//需要找到倒數第二個結點才能刪除最后一個結點{cur = cur->next;}SLTNode* tmp = cur->next;free(tmp);tmp = NULL;cur->next = NULL;}
}//頭刪函數
void SListPopFront(SLTNode** pphead)
{assert(pphead&&*pphead);//鏈表為空時不能刪除SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//在指定結點之前插入函數
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);//需要找到指定結點的前一個結點SLTNode* prev = *pphead;//可能第一個結點就是指定結點，此時相當于頭插if (prev == pos){//直接調用頭插函數SListPushFront(pphead, x);}else{while (prev->next != pos){prev = prev->next;}SLTNode* NewNode = BuySListNode(x);NewNode->next = prev->next;prev->next = NewNode;}
}//在指定結點之后插入函數
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* NewNode = BuySListNode(x);NewNode->next = pos->next;pos->next = NewNode;
}//刪除指定結點
void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* prev = *pphead;//如果第一個結點就是要刪除的結點if (prev == pos){//直接調用頭刪SListPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}SLTNode* tmp = prev->next;//tmp即要刪除的結點prev->next = tmp->next;free(tmp);tmp = NULL;}
}//查找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{SLTNode* cur = phead;while (cur != NULL){if (cur->data == x)return cur;cur = cur->next;}//沒找到或鏈表為空時，返回空指針return NULL;
}//銷毀鏈表函數
void SListDestory(SLTNode** pphead)
{assert(pphead && *pphead);while (*pphead != NULL){SLTNode* tmp = *pphead;*pphead = (*pphead)->next;free(tmp);tmp = NULL;}
}

3.測試文件（測試各個函數的功能）

test.c

#include"SList.h"//測試尾插函數
void test01()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);
}//測試頭插函數
void test02()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);
}//測試尾刪函數
void test03()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);SListPopBack(&phead);SListPrint(phead);
}//測試頭刪函數
void test04()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);SListPopFront(&phead);SListPrint(phead);
}//測試查找函數
void test05()
{SLTNode* phead = NULL;SListPushFront(&phead, 1);SListPushFront(&phead, 2);SListPushFront(&phead, 3);SListPushFront(&phead, 4);SListPrint(phead);SLTNode* ret1 = SListFind(phead, 2);if (ret1 != NULL)printf("找到了\n");elseprintf("未找到\n");SLTNode* ret2 = SListFind(phead, 57);if (ret2 != NULL)printf("找到了\n");elseprintf("未找到\n");
}//測試在指定結點之前插入
void test06()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//在第三個結點前插入57//先查找到第三個結點SLTNode* pos1 = SListFind(phead, 3);SListInsert(&phead, pos1, 57);SListPrint(phead);//在第一個結點前插入79//先查找到第一個結點SLTNode* pos2 = SListFind(phead, 1);SListInsert(&phead, pos2, 79);SListPrint(phead);//在最后一個結點前插入36//先查找到最后一個結點SLTNode* pos3 = SListFind(phead, 4);SListInsert(&phead, pos3, 36);SListPrint(phead);
}//測試在指定結點之后插入
void test07()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//在第三個結點后插入57//先查找到第三個結點SLTNode* pos1 = SListFind(phead, 3);SListInsertAfter(&phead, pos1, 57);SListPrint(phead);//在第一個結點后插入79//先查找到第一個結點SLTNode* pos2 = SListFind(phead, 1);SListInsertAfter(&phead, pos2, 79);SListPrint(phead);//在最后一個結點后插入36//先查找到最后一個結點SLTNode* pos3 = SListFind(phead, 4);SListInsertAfter(&phead, pos3, 36);SListPrint(phead);
}//測試刪除結點函數
void test08()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);//刪除第一個結點SLTNode* pos1 = SListFind(phead, 1);SListErase(&phead, pos1);SListPrint(phead);//刪除第三個結點SLTNode* pos2 = SListFind(phead, 3);SListErase(&phead, pos2);SListPrint(phead);//刪除最后一個結點SLTNode* pos3 = SListFind(phead, 4);SListErase(&phead, pos3);SListPrint(phead);
}//測試銷毀函數
void test09()
{SLTNode* phead = NULL;SListPushBack(&phead, 1);SListPushBack(&phead, 2);SListPushBack(&phead, 3);SListPushBack(&phead, 4);SListPrint(phead);SListDestory(&phead);SListPrint(phead);
}
int main()
{//test01();//test02();//test03();//test04();//test05();//test06();//test07();//test08();test09();return 0;
}

五.單鏈表和順序表的對比

1.存儲分配方式

順序表采用一段連續的存儲單元存儲數據元素。
單鏈表采用一組任意的存儲單元存儲元素。

2.時間性能

查找：
順序表按值查找O(n)，按索引查找O(1)。
單鏈表O(n)。
插入和刪除：
順序表O(n)。
單鏈表O(1)。

3.空間性能

順序表需要預分配空間，小了需再次分配，大了造成空間浪費。
單鏈表需要時申請結點空間。

4.總結

若線性表需要頻繁查找，宜采用順序存儲結構。若頻繁插入和刪除，宜采用鏈式存儲結構。比如說游戲開發中，對于用戶注冊的個人信息，除了注冊時插入數據外，絕大多數情況都是讀取，所以應該考慮用順序存儲結構 。而游戲中的玩 家的武器或者裝備列表，隨著玩家的游戲過程中，可能會隨時增加或刪除，此時再用順序存儲就不大合適了，鏈表結構就可以大展拳腳。當然，這只是簡單的類比，現實中的軟件開發，要考慮的問題會復雜得多。
總之，線性表的順序存儲和鏈式存儲各有優缺點，不能簡單說哪個好，哪個不好，需根據實際情況做出選擇。