往期《數據結構初階》回顧：
【時間復雜度 + 空間復雜度】

前言：

先聊些其他的東西！！！

在之前的博客中博主向大家信誓旦旦地宣布博主之后將持續更新的《數據結構初階》這個系列的博客。
博客內容主要劃分為：數據結構的介紹 + 數據結構的實現 + 數據結構的OJ練習，這三大板塊的內容。
結果一動手發現——好家伙！三部分加起來有2萬字，要是把OJ練習也塞進來，怕是要寫成《數據結構從入門到放棄》了！
所以博主這里選擇先將前兩個板塊的內容寫成一篇博客，至于數據結構的OJ練習這個板塊就單獨成文。

---

溫馨提示：這篇博客中的主要內容是代碼，每個代碼塊中的代碼都有非常詳細的注釋，相信各位勇士一定能征服這些數據結構！? （畢竟博主的注釋寫得比情書還用心💘）

什么是線性表？

線性表(Linear List)：是具有相同數據類型的n(n≥0)個數據元素的有限序列。

• 線性表是數據結構中最基本、最簡單的一種結構。

• 線性表是一種在實際中廣泛使用的數據結構。

• 常見的線性表：順序表、鏈表、棧、隊列、字符串…

線性表在邏輯結構上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以 順序結構 和 鏈式結構 的形式存儲。

線性表有兩種主要的存儲結構：

1. 順序存儲結構（順序表）

   • 用一組地址連續的存儲單元依次存儲線性表的元素
   • 可以通過數組實現

2. 鏈式存儲結構（鏈表）

   • 用一組任意的存儲單元存儲線性表的元素

   • 每個元素除了存儲數據外，還需要存儲指向后繼元素的指針

特性	順序表 (Array List)	鏈表 (Linked List)
邏輯結構	1. 線性結構，元素按順序排列 2. 通過下標直接表示邏輯關系	1. 線性結構，元素通過指針鏈接 2. 邏輯順序由指針決定
物理結構	1. 連續內存空間存儲 2. 物理順序 = 邏輯順序	1. 非連續內存存儲（節點分散） 2. 物理順序 != 邏輯順序

什么是順序表？

順序表（Sequential List）：是線性表的順序存儲結構，即用一組地址連續的存儲單元依次存儲線性表中的數據元素。

順序表在內存中的物理結構與邏輯結構一致，元素之間的順序關系由存儲位置決定。

順序表的種類有哪些？

順序表一般可以分為：

1. 靜態順序表：使用定長數組存儲元素

--------------------------順序表的靜態存儲實現-----------------------------// 定義順序表的最大容量為7
#define N 7// 定義順序表存儲的數據類型為int（便于后續靈活修改數據類型）
typedef int SLDataType;// 定義靜態順序表的結構體
typedef struct SeqList
{size_t size;          //1.記錄當前順序表中有效數據的個數（即：表長）SLDataType array[N];  //2.靜態分配的定長數組，用于存儲順序表元素
} SeqList;

2. 動態順序表：使用動態開辟的數組存儲

--------------------------順序表的動態存儲實現-----------------------------// 定義順序表存儲的數據類型（默認為int，可通過修改此處改變整個表的數據類型）
typedef int SLDataType;// 定義動態順序表結構體
typedef struct SeqList
{size_t size;         //1.當前順序表中實際存儲的有效元素個數           size_t capacity;     //2.當前動態數組的總容量大小SLDataType* array;   //3.指向動態開辟的數組空間的首地址     
} SeqList;

什么是鏈表？

鏈表（Linked List） ：是一種線性表的 鏈式存儲結構，它通過 指針（或引用） 將一組 零散的內存塊（結點）串聯起來，形成邏輯上的線性序列。

鏈表的種類有哪些？

實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：

單向或者雙向

帶頭或者不帶頭

循環或者非循環

雖然鏈表有這么多的結構，但是我們實際中最常用的只有以下兩種結構：

• 無頭單向非循環鏈表：又名為 單鏈表
  • 結構最簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構
  • 如：哈希桶、圖的鄰接表等等。
• 帶頭雙向循環鏈表：又名為 雙向鏈表
  • 結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環鏈表

1. 單鏈表：

typedef int SLTDataType;typedef struct singleListNode
{//1.記錄鏈表中節點的值 ---> 一個SLTDataType類型的變量//2.記錄下一個節點的地址 ---> 一個struct singleListNode*類型的指針SLTDataType data;struct singleListNode* next;
}SLTNode;

1. 雙向鏈表：

typedef int DLTDataType;typedef struct DoubleListNode
{//1.存儲雙向鏈表中的節點的值 --> 一個DLTDataType類型的變量//2.記錄節點的前驅節點的位置 --> 一個struct DoubleListNode*類型的指針//3.記錄節點的后繼節點的位置 --> 一個struct DoubleListNode*類型的指針DLTDataType data;struct DoubleListNode* prev;struct DoubleListNode* next;
}DLTNode;

---------------順序表---------------

動態順序表的實現

頭文件

-------------------------------SeqList.h--------------------------------#pragma once//任務1：包含需要使用的頭文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//任務2：定義順序表的存儲結構
typedef int SLDataType;
typedef struct SeqList
{//1.動態順序的底層使用動態數組實現 ---> 一個SLDataType類型的指針（代表動態數組的首元素地址）//2.記錄當前動態順序中元素的數量 ---> 一個int類型的變量//3.記錄動態順序表的容量 ---> 一個int類型的變量SLDataType* a;int size;int capacity;
}SL;//任務3：聲明動態順表使用的工具函數
//1.擴容函數
void SLCheckCapacity(SL* ps);//任務4：聲明順序表的接口函數/*--------------------- 基礎操作 ---------------------*/
//1.順序表的初始化
//2.順序表的銷毀
//3.順序表的打印/*--------------------- 插入刪除操作 ---------------------*/
//4.順序表的頭插
//5.順序表的尾插
//6.順序表的頭刪
//7.順序表的尾刪/*--------------------- 指定位置操作 ---------------------*/
//8.順序表的指定位置插入
//9.順序表的指定位置刪除
//10.順序表的查找某個元素void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL ps);void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

實現文件

-------------------------------SeqList.c--------------------------------#include "SeqList.h"/*--------------------- 工具函數的實現 ---------------------*/
//1.實現：“動態順序表的擴容”的工具函數
/*** @brief 檢查并擴容順序表* @param ps 指向順序表結構的指針* @note 當size == capacity時自動擴容*       初始容量為4，后續每次擴容為原來的2倍*/void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){//1.先判斷需要擴容的數量int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//2.再使用realloc進行空間的擴容SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SL)); //注意：這里先使用一個臨時的指針指向開辟的這片空間，因為開辟空間可能開辟失敗//2.1：使用if判斷：擴容是否成功if (tmp == NULL){perror("realloc fail");return;}//3.最后更新指針和容量（擴容成功）ps->a = tmp;ps->capacity = newCapacity;}
}/*--------------------- 順序表接口函數的實現 ---------------------*///1.實現：“順序表的初始化”操作
/*** @brief 初始化順序表* @param ps 指向順序表結構的指針* @note 將順序表置為空表，a指針置NULL*       size和capacity初始化為0*/
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//2.實現：“順序表的銷毀”操作
/*** @brief 銷毀順序表* @param ps 指向順序表結構的指針* @note 釋放動態分配的數組內存*       并將所有成員重置為初始狀態*/
void SLDestroy(SL* ps)
{assert(ps);free(ps->a); //順序表的銷毀相較于初始化唯一的不同在于銷毀時需要將ps->a指向的動態開辟的空間釋放掉；//同時我們也要注意我們的初始化操作中沒有動態開辟空間ps->a = NULL;ps->size = 0;ps->capacity = 0;
}//3.實現：“順序表的打印”操作
/*** @brief 打印順序表內容* @param s 順序表結構（傳值）* @note 遍歷打印所有有效元素*/
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.a[i]);}printf("\n");
}//4.實現：“順序表的尾插”操作
/*** @brief 順序表尾部插入元素* @param ps 指向順序表結構的指針* @param x 要插入的元素值* @note 先檢查容量，不足則自動擴容*       時間復雜度O(1)（不考慮擴容）*/
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//1.直接在數組的尾部添加要插入的元素ps->a[ps->size] = x;//2.將順序表中當前元素的數量+1ps->size++;
}//5.實現：“順序表的頭插”操作
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);//1.將數組中的所有元素都向后挪動一位（從后向前處理元素）for (int i = ps->size - 1; i >= 0; i--){ps->a[i + 1] = ps->a[i];}//2.直接在數組的頭部添加要插入的元素ps->a[0] = x;//3.將順序表中當前元素的數量+1ps->size++;}//6.實現：“順序表的尾刪”操作
/*** @brief 順序表尾部刪除元素* @param ps 指向順序表結構的指針* @note 只需減小size，不實際釋放內存*       時間復雜度O(1)*/
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size > 0);//1.直接順序表中當前的元素的數量-1ps->size--;
}//7.實現：“順序表的頭刪”操作void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);//1.將數組中的所有的元素都向前移動一位（從前往后處理元素）for (int i = 1; i <= ps->size - 1; i++){ps->a[i - 1] = ps->a[i];}//2.將順序表中當前的元素的數量-1ps->size--;
}//8.實現：“順序表的指定位置的前面插入”操作
/*** @brief 在指定位置前面插入元素* @param ps 指向順序表結構的指針* @param pos 插入位置（0-based）* @param x 要插入的元素值* @note 位置必須合法（0 <= pos <= size）*       自動檢查擴容，時間復雜度O(n)*/
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//1.將指定位置及其之后的所有的元素都向后挪動一個位置（從后往前處理元素）for (int i = ps->size - 1; i >= pos; i--){ps->a[i + 1] = ps->a[i];}//2.直接在數組的pos位置上添加想要插入的元素ps->a[pos] = x;//3.將順序表中當前元素的數量+1ps->size++;
}//9.實現：“順序表的指定位置的刪除”操作
/*** @brief 刪除指定位置元素* @param ps 指向順序表結構的指針* @param pos 刪除位置（0-based）* @note 位置必須合法（0 <= pos < size）*       時間復雜度O(n)*/void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//1.將指定位置之后的所有的元素都向前挪動一個位置（從前向后處理元素）for (int i = pos + 1; i <= ps->size - 1; i++){ps->a[i - 1] = ps->a[i];}//2.將順序表中當前元素的數量-1ps->size--;
}//10.實現：“順序表的查找某個元素”操作
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
} 

測試文件

--------------------------------Test.c---------------------------------#include "SeqList.h"/*** @brief 測試順序表基礎功能* @note 包含初始化、銷毀、尾部插入、打印等基礎測試*/
void test01()
{SL sl;SLInit(&sl);// 測試頭插SLPushFront(&sl, 5);SLPushFront(&sl, 3);printf("頭插2個元素后: ");SLPrint(sl);  // 預期輸出：3 5// 測試尾插SLPushBack(&sl, 7);SLPushBack(&sl, 9);printf("尾插2個元素后: ");SLPrint(sl);  // 預期輸出：3 5 7 9// 測試頭刪SLPopFront(&sl);printf("頭刪1次后: ");SLPrint(sl);  // 預期輸出：5 7 9// 測試尾刪SLPopBack(&sl);printf("尾刪1次后: ");SLPrint(sl);  // 預期輸出：5 7SLDestroy(&sl);printf("\n");
}/*** @brief 測試順序表高級功能* @note 測試指定位置插入/刪除、查找等功能*       驗證邊界條件處理是否正確*/
void test02()
{SL sl;                  // 聲明順序表變量SLInit(&sl);            //準備測試數據 SLPushBack(&sl, 1);     SLPushBack(&sl, 2);     SLPushBack(&sl, 3);     SLPushBack(&sl, 4);     printf("初始數據: ");SLPrint(sl);            // 預期輸出：1 2 3 4///測試指定位置插入SLInsert(&sl, 1, 99);   SLInsert(&sl, sl.size, 88); printf("插入后數據: ");SLPrint(sl);            // 預期輸出：1 99 2 3 4 88//測試指定位置刪除 SLErase(&sl, 1);        printf("刪除后數據: ");SLPrint(sl);            // 預期輸出：1 2 3 4 88///測試查找功能 int find = SLFind(&sl, 40); if (find < 0) {printf("沒有找到！\n");  }else {printf("找到了！下標為%d\n", find);}SLDestroy(&sl);      
}int main()
{test01();test02();return 0;
}

運行結果

---------------單鏈表---------------

無頭單向非循環鏈表的實現

頭文件

-----------------------------SingleList.h-------------------------------#pragma once//任務1：包含要使用的頭文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//任務2：定義單鏈表的存儲結構
typedef int SLTDataType;typedef struct singleListNode
{//1.記錄鏈表中節點的值 ---> 一個SLTDataType類型的變量//2.記錄下一個節點的地址 ---> 一個struct singleListNode*類型的指針SLTDataType data;struct singleListNode* next;
}SLTNode;//任務3：聲明單鏈表使用的工具函數
SLTNode* SLTCreateNode(SLTDataType x);//任務4：聲明單鏈表的接口函數//0.單鏈表的打印//1.單鏈表的尾插
//2.單鏈表的頭插
//3.單鏈表的尾刪
//4.單鏈表的頭刪//5.單鏈表的查找
//6.單鏈表的指定節點的前驅節點插入
//7.單鏈表的指定節點的后繼節點插入
//8.單鏈表的指定節點的刪除
//9.單鏈表的指定節點的后繼節點的刪除
//10.單鏈表的銷毀void SLTPrint(SLTNode* phead);void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
void SLTErase(SLTNode** pphead, SLTNode* pos);
void SLTEraseAfter(SLTNode* pos);
void SLTDestroy(SLTNode** pphead);   

實現文件

-----------------------------SingleList.c-------------------------------#include "SingleList.h"//0.實現：“單邊表的節點創建”工具函數
/*** @brief 動態創建一個新的鏈表節點并初始化* @param x 要存儲在新節點中的數據* @return 返回指向新創建節點的指針* @note 1. 使用malloc動態分配內存*       2. 檢查內存分配是否成功*       3. 初始化節點的data和next成員*/SLTNode* SLTCreateNode(SLTDataType x)
{//1.節點空間的創建SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));//1.1：判斷空間是否開辟成功if (newNode == NULL){perror("malloc fail");return NULL;}//2.節點參數的初始化newNode->data = x;newNode->next = NULL;//3.節點地址的返回return newNode;
}//1.實現：“單鏈表的打印”操作
/*** @brief 打印單鏈表的所有元素* @param phead 指向單鏈表頭節點的指針* @note 遍歷鏈表并打印每個節點的數據，最后以NULL結尾*/
void SLTPrint(SLTNode* phead)
{//1.定義一個臨時的指針代替phead指針遍歷整個鏈表SLTNode* pcur = phead;//2.進行循環遍歷while (pcur != NULL){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//2.實現：“單鏈表的尾插”操作
/*** @brief 在單鏈表的尾部插入新節點* @param pphead 指向頭節點指針的指針（二級指針，用于修改頭節點）* @param x 要插入的數據* @note 1. 如果鏈表為空（*pphead == NULL），新節點成為頭節點*       2. 如果鏈表非空，遍歷找到尾節點，并在其后插入新節點*/
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作//1.創建一個新節點并將其初始化SLTNode* newNode = SLTCreateNode(x);//2.情況1：處理單鏈表是空鏈表的情況if (*pphead == NULL){//1.1：更新頭指針*pphead = newNode;}//3.情況2：處理單鏈表是非空鏈表的情況else{//3.1：遍歷鏈表找到尾節點的位置SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//3.2：將新節點鏈接到鏈表的尾部ptail->next = newNode;}
}//3.實現：“單鏈表的頭插”操作
/*** @brief 在單鏈表的頭部插入新節點* @param pphead 指向頭節點指針的指針（二級指針，用于修改頭節點）* @param x 要插入的數據* @note 1. 新節點會成為新的頭節點*       2. 無論鏈表是否為空都適用*/
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead); //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作//1.創建一個新節點并將其初始化SLTNode* newNode = SLTCreateNode(x);//2.將新節點鏈接到鏈表的頭部    (注意：這里無論鏈表的是空鏈表還是非空鏈表都是符合)newNode->next = *pphead;//3.更新頭指針*pphead = newNode;
}//4.實現：“單鏈表的尾刪”操作
/*** @brief 刪除單鏈表的尾節點* @param pphead 指向頭節點指針的指針（二級指針）* @note 1. 鏈表不能為空*       2. 處理單節點和多節點不同情況*       3. 釋放尾節點內存并維護鏈表結構*/void SLTPopBack(SLTNode** pphead)
{assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行刪除節點的操作//情況1：處理單鏈表中只有一個節點的情況if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//情況2：處理單鏈表中節點不止一個的情況else{//1.找到尾節點前面的那個節點的位置SLTNode* prev = *pphead;while (prev->next->next != NULL){prev = prev->next;}//2.斷開尾節點的鏈接 + 釋放尾節點的內存//2.1：定義指針指向要刪除的節點SLTNode* del = prev->next;//2.2：斷開要刪除的節點的鏈接prev->next = prev->next->next;//2.3：釋放要刪除的節點的內存free(del);//2.4：將指向被刪除節點的指針都置空del = NULL;}
}//5.實現：“單鏈表的頭刪”操作
/*** @brief 刪除單鏈表的頭節點* @param pphead 指向頭節點指針的指針（二級指針）* @note 1. 鏈表不能為空*       2. 釋放原頭節點內存*       3. 更新頭指針指向下一個節點*/
void SLTPopFront(SLTNode** pphead)
{assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行刪除節點的操作//1.定義指向頭節點的下一個節點的指針SLTNode* next = (*pphead)->next;//2.釋放頭指針指向的頭節點的內存free(*pphead);//3.更新頭指針  （注意：這里并沒有將指向被刪除節點的指針*pphead置空，原因是：*pphead會被更新為next指針所在的位置并未變成野指針）*pphead = next;
}//6.實現：“單鏈表的查找”操作
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur != NULL){if (pcur->data == x)  return pcur;pcur = pcur->next;}return NULL;
}//7.實現：“單鏈表的指定節點的前驅節點插入”操作
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行指定節點之前插入的操作assert(pos); //斷言檢查3：確保pos指針有效，防止對空節點之前插入節點SLTNode* newNode = SLTCreateNode(x);//情況1：處理pos是頭節點的情況 --> 相當于頭插if (pos == *pphead){SLTPushFront(pphead, x);}//情況2：處理pos不是頭節點的情況else{//1.找到pos節點前面那個節點的位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//2.鏈接新節點：prev -> newNode -> pos （新插入的節點的前后節點有獨立的指針指向，所以這里的鏈接隨意）prev->next = newNode;newNode->next = pos;}}//8.實現：“單鏈表的指定節點的后繼節點插入”操作
/*** @brief 在單鏈表指定節點后插入新節點* @param pos 要在其后插入新節點的目標節點指針* @param x 要插入的新數據* @note 1. 不需要頭指針，直接操作pos節點*       2. 時間復雜度O(1)*       3. 新節點插入在pos和原pos->next之間*/void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos); //斷言檢查1：確保pos指針有效，防止對空節點之后插入節點SLTNode* newNode = SLTCreateNode(x);//鏈接新節點：pos -> newNode -> pos->next 新插入的節點的后一個節點沒有獨立的指針指向，所以這里的鏈接順序必須是下面的這個順序//同時這也是為什么我們傳參數的時候之傳入一個指針即可，因為一個指針就可以管控newNode節點前后的兩個節點//1.先鏈接新節點的下一個節點newNode->next = pos->next;//2.再鏈接新節點的上一個節點pos->next = newNode;
}//9.實現：“單鏈表的指定節點的刪除”操作
/*** @brief 刪除單鏈表中的指定節點* @param pphead 指向頭節點指針的指針（二級指針）* @param pos 要刪除的目標節點指針* @note 1. 處理pos是頭節點和非頭節點兩種情況*       2. 需要維護鏈表結構完整性*       3. 釋放被刪除節點的內存*/
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行指定節點的刪除的操作assert(pos); //斷言檢查3：確保pos指針有效，防止對空節點進行刪除//情況1：處理pos頭節點的情況 ---> 相當于頭刪if (pos == *pphead){SLTPopFront(pphead);}//情況2：處理pos非頭節點的情況else{//1.找到要刪除節點pos之前的節點位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//2.斷開pos節點的鏈接 + 釋放pos節點的內存//2.1：斷開鏈接prev->next = prev->next->next;//2.2：釋放內存free(pos);//2.3:將指向被刪除節點的指針置為空pos = NULL;}
}//10.實現：“單鏈表的指定節點的后繼節點刪除”操作
/*** @brief 刪除指定節點后的節點* @param pos 指定節點指針（要刪除其后的節點）* @note 1. 直接操作pos節點的next指針*       2. 時間復雜度O(1)*       3. 需要確保pos->next存在（不能是尾節點）*/
void SLTEraseAfter(SLTNode* pos)
{assert(pos); //斷言檢查1：確保pos指針有效，防止對空節點之后進行刪除//1.定義指針指向要刪除的節點SLTNode* del = pos->next;//2.斷開要刪除的節點的鏈接pos->next = pos->next->next;//3.釋放要刪除的節點的內存free(del);//4.將指向被刪除的節點的中指針置空del = NULL;
}//11.實現：“單鏈表的銷毀”操作
/*** @brief 銷毀整個單鏈表，釋放所有節點內存* @param pphead 指向頭節點指針的指針（二級指針）* @note 1. 遍歷鏈表逐個釋放節點*       2. 最后將頭指針置NULL*       3. 時間復雜度O(n)*/
void SLTDestroy(SLTNode** pphead)
{assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作//1.定義臨時指針代替*pphead進行單鏈表的遍歷SLTNode* pcur = *pphead;while (pcur != NULL){//2.定義指針存儲臨時指針的下一個遍歷的位置SLTNode* next = pcur->next;//3.釋放要刪除的節點的內存free(pcur);//4.更新臨時指針pcur = next; //指針指向空間被釋放后并沒有進行置空來防止其為野指針，因為我們更新了指針}//5.將鏈表的頭指針置空防止其為野指針*pphead = NULL;
}

測試文件

---------------------------------Test.c----------------------------------#include "SingleList.h"void TestSLT1() 
{printf("\n========== 測試1：創建和打印 ==========\n");SLTNode* plist = NULL;SLTPrint(plist);  // 預期輸出：NULL// 測試尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("尾插1,2,3后: ");SLTPrint(plist);  // 預期輸出：1->2->3->NULL// 測試頭插SLTPushFront(&plist, 0);SLTPushFront(&plist, -1);printf("頭插0,-1后: ");SLTPrint(plist);  // 預期輸出：-1->0->1->2->3->NULL
}void TestSLT2() 
{printf("\n========== 測試2：刪除操作 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("初始鏈表: ");SLTPrint(plist);  // 1->2->3->NULL// 測試尾刪SLTPopBack(&plist);printf("尾刪后: ");SLTPrint(plist);  // 1->2->NULL// 測試頭刪SLTPopFront(&plist);printf("頭刪后: ");SLTPrint(plist);  // 2->NULL// 刪除最后一個節點SLTPopBack(&plist);printf("刪除最后一個節點后: ");SLTPrint(plist);  // NULL
}void TestSLT3() 
{printf("\n========== 測試3：查找和插入 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 4);printf("初始鏈表: ");SLTPrint(plist);  // 1->2->4->NULL// 測試查找SLTNode* pos = SLTFind(plist, 2);if (pos) {printf("找到節點2，在其后插入3\n");SLTInsertAfter(pos, 3);SLTPrint(plist);  // 1->2->3->4->NULL}pos = SLTFind(plist, 1);if (pos) {printf("找到節點1，在其前插入0\n");SLTInsert(&plist, pos, 0);SLTPrint(plist);  // 0->1->2->3->4->NULL}
}void TestSLT4() 
{printf("\n========== 測試4：刪除指定節點 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);printf("初始鏈表: ");SLTPrint(plist);  // 1->2->3->4->NULL// 測試刪除中間節點SLTNode* pos = SLTFind(plist, 2);if (pos) {printf("刪除節點2\n");SLTErase(&plist, pos);SLTPrint(plist);  // 1->3->4->NULL}// 測試刪除后繼節點pos = SLTFind(plist, 3);if (pos) {printf("刪除節點3的后繼\n");SLTEraseAfter(pos);SLTPrint(plist);  // 1->3->NULL}
}void TestSLT5() 
{printf("\n========== 測試5：銷毀鏈表 ==========\n");SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);printf("銷毀前: ");SLTPrint(plist);  // 1->2->3->NULLSLTDestroy(&plist);printf("銷毀后: ");SLTPrint(plist);  // NULL// 測試銷毀后能否繼續操作SLTPushBack(&plist, 5);printf("重新插入后: ");SLTPrint(plist);  // 5->NULLSLTDestroy(&plist);
}void TestSLT6() 
{printf("\n========== 測試6：邊界測試 ==========\n");SLTNode* plist = NULL;// 測試空鏈表操作printf("嘗試對空鏈表頭刪: ");//SLTPopFront(&plist);  // 應該觸發斷言printf("嘗試對空鏈表尾刪: ");//SLTPopBack(&plist);   // 應該觸發斷言// 測試單節點操作SLTPushFront(&plist, 1);printf("單節點鏈表: ");SLTPrint(plist);  // 1->NULLSLTPopBack(&plist);printf("刪除后: ");SLTPrint(plist);  // NULL
}int main() 
{TestSLT1();  // 基本插入測試TestSLT2();  // 基本刪除測試TestSLT3();  // 查找和插入測試TestSLT4();  // 指定位置刪除測試TestSLT5();  // 銷毀測試//TestSLT6();  // 邊界測試printf("\n所有測試完成!\n");return 0;
}

運行結果

心得總結

0.單鏈表的打印1.單鏈表的尾插
2.單鏈表的頭插
3.單鏈表的尾刪
4.單鏈表的頭刪5.單鏈表的查找
6.單鏈表的指定節點的前驅節點插入
7.單鏈表的指定節點的后繼節點插入
8.單鏈表的指定節點的刪除
9.單鏈表的指定節點的后繼節點的刪除
10.單鏈表的銷毀

哪些操作使用了斷言？都使用了哪些斷言？

1. 除了 0.單鏈表的打印 和 5.單鏈表的查找 操作沒有使用斷言，其余的操作都使用了斷言
2. 只要是指定節點的操作，都要添加這一條斷言：assert(pos); //斷言檢查1：確保pos指針有效
3. 只要是涉及刪除的操作都使用了這一條斷言：assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表
4. 除了 7.單鏈表的指定節點的后繼節點插入 和 9.單鏈表的指定節點的后繼節點的刪除 這兩操作的接口函數的形參中沒有SLTNode** pphead，導致斷言中沒有 assert(pphead); //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作，其他有斷言的函數中都有這個斷言。并且這兩個函數中且只有這一個斷言：assert(pos); //斷言檢查1：確保pos指針有效

1.單鏈表的尾插
2.單鏈表的頭插
assert(pphead); //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作
------------------------------------------------------------------------3.單鏈表的尾刪
4.單鏈表的頭刪 
10.單鏈表的銷毀
assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作
assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行刪除節點的操作------------------------------------------------------------------------6.單鏈表的指定節點的前驅節點插入
assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作
assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行指定節點之前插入的操作
assert(pos); //斷言檢查3：確保pos指針有效，防止對空節點之前插入節點8.單鏈表的指定節點的刪除
assert(pphead);  //斷言檢查1：確保傳入的二級指針pphead是有效的，防止對空指針進行解引用的操作
assert(*pphead); //斷言檢查2：確保單鏈表是非空單鏈表，防止對空鏈表進行指定節點的刪除的操作
assert(pos); //斷言檢查3：確保pos指針有效，防止對空節點進行刪除------------------------------------------------------------------------7.單鏈表的指定節點的后繼節點插入
assert(pos); //斷言檢查1：確保pos指針有效，防止對空節點之后插入節點9.單鏈表的指定節點的后繼節點的刪除
assert(pos); //斷言檢查1：確保pos指針有效，防止對空節點之后進行刪除

哪些操作是需要分情況處理的？都分為哪些情況？

1.單鏈表的尾插

• 情況1：處理單鏈表是空鏈表的情況
• 情況2：處理單鏈表是非空鏈表的情況

3.單鏈表的尾刪

• 情況1：處理單鏈表中只有一個節點的情況
• 情況2：處理單鏈表中節點不止一個的情況

6.單鏈表的指定節點的前驅節點插入

• 情況1：處理pos是頭節點的情況 --> 相當于頭插
• 情況2：處理pos不是頭節點的情況

8.單鏈表的指定節點的刪除

• 情況1：處理pos頭節點的情況 —> 相當于頭刪
• 情況2：處理pos非頭節點的情況

---------------雙向鏈表---------------

帶頭雙向循環鏈表的實現

頭文件

-----------------------------DoubleList.h--------------------------------#pragma once//任務1：包含要使用的頭文件
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>//任務2：定義雙向鏈表的存儲結構
typedef int DLTDataType;typedef struct DoubleListNode
{//1.存儲雙向鏈表中的節點的值 --> 一個DLTDataType類型的變量//2.記錄節點的前驅節點的位置 --> 一個struct DoubleListNode*類型的指針//3.記錄節點的后繼節點的位置 --> 一個struct DoubleListNode*類型的指針DLTDataType data;struct DoubleListNode* prev;struct DoubleListNode* next;
}DLTNode;//任務3：聲明雙向鏈表需要使用輔助工具函數
//1.用于創建雙向鏈表的節點
DLTNode* DLTCreateNode(DLTDataType x);//任務4：聲明雙向鏈表的接口函數
//1.雙向鏈表的初始化
//2.雙向鏈表的銷毀
//3.雙向鏈表打印//3.雙向鏈表的尾插
//4.雙向鏈表的頭插
//5.雙向鏈表的尾刪
//6.雙向鏈表的頭刪//7.雙向鏈表的查找
//8.雙向鏈表的指定節點之后插入
//9.雙向鏈表的指定節點的刪除//void DLTInit(DLTNode** pphead);
DLTNode* DLTInit();
void DLTDestroy(DLTNode* phead);
void DLTPrint(DLTNode* phead);void DLTPushBack(DLTNode* phead, DLTDataType x);
void DLTPushFront(DLTNode* phead, DLTDataType x);
void DLTPopBack(DLTNode* phead);
void DLTPopFront(DLTNode* phead);DLTNode* DLTFind(DLTNode* phead, DLTDataType x);
void DLTInsert(DLTNode* pos, DLTDataType x);
void DLTErase(DLTNode* pos);

實現文件

-----------------------------DoubleList.c--------------------------------#include "DoubleList.h"//0.實現：“用于創建雙向鏈表的節點”的工具函數
/*** @brief 申請一個新節點并初始化* @param x 節點存儲的數據* @return 返回新節點的指針* @note 1. 動態分配內存*       2. 初始化前后指針都指向自己*/
DLTNode* DLTCreateNode(DLTDataType x)
{DLTNode* newNode = (DLTNode*)malloc(sizeof(DLTNode));if (newNode == NULL){perror("malloc fail");return NULL;}newNode->data = x;newNode->prev = newNode;newNode->next = newNode;return newNode;
}//1.實現：“雙向鏈表的初始化”操作
/*** @brief 初始化雙向鏈表* @return 返回哨兵位的指針* @note 創建一個值為-1的哨兵位節點*//*
void DLTInit(DLTNode** pphead)
{//雙向鏈表的初始化本質就是：給雙向鏈表創建一個哨兵節點*pphead = DLTCreateNode(-1);//注意：雙向鏈表的哨兵節點中存儲的值并無實際的意義，所以這里我們將其賦值為-1
}*/
//由于雙向鏈表的其他的接口函數的形式參數的中都是使用的一個*的值傳遞
//為了保持一致性，這里我們重寫DLTInint函數
DLTNode* DLTInit()
{DLTNode* phead = DLTCreateNode(-1);return phead;
}//2.實現：“雙向鏈表的銷毀”操作
/*** @brief 銷毀雙向鏈表* @param phead 哨兵位指針* @note 釋放所有節點包括哨兵位*/
void DLTDestroy(DLTNode* phead) //注意：這里我們傳參的時候只是用了一個*，是值傳遞：所以調用完DLTDestroy函數之后我們還要手動的將phead指針置空
{assert(phead); //作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用DLTNode* pcur = phead->next;while (pcur != phead){DLTNode* next = pcur->next;free(pcur);pcur = next;}// 注意：相較于單鏈表雙向鏈表還需要將哨兵節點置空free(phead);//注意：這里我們并沒用將哨兵節點置為空，原因是：此處phead是函數的局部變量，對其置NULL不會影響外部實參//所以：調用者必須自行處理外部指針
}//3.實現：“雙向鏈表的打印”操作
/*** @brief 打印雙向鏈表的所有元素（不打印哨兵位）* @param phead 指向雙向鏈表哨兵位的指針* @note 從哨兵位的下一個節點開始遍歷，直到回到哨兵位*/
void DLTPrint(DLTNode* phead)
{assert(phead); //作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用DLTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//4.實現：“雙向鏈表的尾插”操作
/*** @brief 雙向鏈表尾插* @param phead 哨兵位指針* @param x 要插入的數據* @note 將新節點插入到哨兵位之前*/
void DLTPushBack(DLTNode* phead, DLTDataType x)
{assert(phead); //作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用DLTNode* newNode = DLTCreateNode(x);//雙向鏈表的尾插涉及到三個節點：//1.哨兵節點：phead//2.尾節點：phead->prev//3.要插入的節點：newNode//總共要出連接四條線才能完成插入//1.將“要插入的節點”和其他的節點產生聯系newNode->prev = phead->prev;newNode->next = phead;//2.將“哨兵節點 + 尾節點”和要插入的節點產生聯系phead->prev->next = newNode;phead->prev = newNode;
}//5.實現：“雙向鏈表的頭插”操作
/*** @brief 雙向鏈表頭插* @param phead 哨兵位指針* @param x 要插入的數據* @note 將新節點插入到哨兵位之后*/
void DLTPushFront(DLTNode* phead, DLTDataType x)
{assert(phead); //作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用DLTNode* newNode = DLTCreateNode(x);//雙向鏈表的頭插涉及到三個節點：//1.哨兵節點：phead//2.首元節點：phead->next//3.要插入的節點：newNode//總共要出連接四條線才能完成插入//1.將“要插入的節點”和其他節點建立連接newNode->prev = phead;newNode->next = phead->next;//2.將“哨兵節點 + 首元節點”和要插入的節點之間建立連接phead->next = newNode;phead->next->next->prev = newNode;//這里一般大家會交換一下這兩個連接的順序，這樣的話不用寫這么多的箭頭phead->next->next->prev//又或者有一部分人會將phead->next替換為newNode，這樣也可以省去一個箭頭//這里我沒有：1.交換連接的順序 2.使用newNode進行替換 //只是為告訴大家：這里的連接正常連就行，僅僅使用phead即可完成}//6.實現：“雙向鏈表的尾刪”操作
void DLTPopBack(DLTNode* phead)
{assert(phead);//作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用assert(phead->next != phead); //作用：確保雙向鏈表非空，防止對空鏈表進行刪除操作（雙向鏈表為空的判斷依據：phead->next == phead）//雙向鏈表的尾刪涉及到三個節點：//1.哨兵節點：phead//2.尾節點的前一個節點：phead->prev->prev//3.要插入的節點（尾節點）：phead->prev//總共要出調整兩條線才能完成刪除//鏈表刪除一個節點的步驟：//1.定義一個指針指向要刪除的節點//2.重新調整節點的連接//3.將要刪除的節點的空間釋放 + 該指針置空//1.DLTNode* del = phead->prev;//2.phead->prev = phead->prev->prev;phead->prev->next = phead;//注意：上面的這兩個連接的順序交不交換完全沒有影響（既不會出現錯誤，也不會帶來簡化）//但是絕大多數人在調整節點的連接的時候會使用上之前已經定義的指針del來簡化連接的箭頭//但是這里我還是沒有進行簡化，因為還是想明確未刪除只是使用phead并且不需要考慮連接的順序就可以實現//我們定義del指針只是用來釋放刪除的節點而已//3.free(del);del = NULL;
}//7.實現：“雙向鏈表的頭刪”操作
/*** @brief 雙向鏈表頭刪* @param phead 哨兵位指針* @note 刪除哨兵位后的一個節點*/
void DLTPopFront(DLTNode* phead)
{assert(phead);//作用：保證傳入的哨兵節點的有效性，防止對空指針進行解引用assert(phead->next != phead); //作用：確保雙向鏈表非空，防止對空鏈表進行刪除操作（雙向鏈表為空的判斷依據：phead->next == phead）//雙向鏈表的頭刪涉及到三個節點：//1.哨兵節點：phead//2.首元節點的下一個節點：phead->next->next//3.要插入的節點(首元節點)：phead->next//總共要出調整兩條線才能完成刪除//鏈表刪除一個節點的步驟：//1.定義一個指針指向要刪除的節點//2.重新調整節點的連接//3.將要刪除的節點的空間釋放 + 該指針置空//1.DLTNode* del = phead->next;//2.phead->next = phead->next->next;phead->next->prev = phead;//3.free(del);del = NULL;
}//8.實現：“雙向鏈表的查找”操作
/*** @brief 在雙向鏈表中查找值為x的節點* @param phead 哨兵位指針* @param x 要查找的值* @return 找到返回節點指針，否則返回NULL*/
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{DLTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//9.實現：“雙向鏈表的指定節點之后插入”操作
void DLTInsert(DLTNode* pos, DLTDataType x)
{assert(pos); //作用：保證傳入的節點的有效性，防止對空指針進行解引用DLTNode* newNode = DLTCreateNode(x);//雙向鏈表的插入涉及到三個節點：//1.插入節點的前一個節點：pos//2.插入節點的后一個節點：pos->next//3.要插入的節點：newNode//總共要出調整四條線才能完成插入操作//1.將“要插入的節點”和其他節點建立連接newNode->prev = pos;newNode->next = pos->next;//2.將“插入節點的前一個節點 + 插入節點的前一個節點” 和要插入的節點建立連接pos->next = newNode;pos->next->next->prev = newNode;
}//10.實現：“雙向鏈表的指定節點的刪除”操作
/*** @brief 刪除pos節點* @param pos 要刪除的節點指針* @note 不能刪除哨兵位*/
void DLTErase(DLTNode* pos)
{assert(pos); //作用：保證傳入的節點的有效性，防止對空指針進行解引用//雙向鏈表的刪除涉及到三個節點：//1.刪除節點的前一個節點：pos->prev//2.刪除節點的后一個節點：pos->next//3.要刪除的節點：pos//總共要調整兩條線才能完成刪除//鏈表刪除一個節點的步驟：//1.定義一個指針指向要刪除的節點//2.重新調整節點的連接//3.將要刪除的節點的空間釋放 + 該指針置空//1.//2.pos->prev->next = pos->next;pos->next->prev = pos->prev;//注：交換連接順序沒有任何影響，只能這么寫//3.free(pos);//pos = NULL; 外面置空
}    

測試文件

---------------------------------Test.c----------------------------------#include "DoubleList.h"
#include <stdio.h>
#include <assert.h>// 打印分隔線，用于區分不同的測試環節
void print_separator() 
{printf("------------------------\n");
}// 測試雙向鏈表的初始化、尾插、頭插和打印功能
void test01() 
{printf("開始測試雙向鏈表的初始化、尾插、頭插和打印功能\n");/*第一代雙向鏈表的初始化方式：DLTNode* head = NULL;DLTInit(&head);*/DLTNode* head = DLTInit();printf("雙向鏈表已初始化\n");printf("執行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("當前雙向鏈表內容為：");DLTPrint(head);printf("執行尾插操作，插入 2\n");DLTPushBack(head, 2);printf("當前雙向鏈表內容為：");DLTPrint(head);printf("執行頭插操作，插入 3\n");DLTPushFront(head, 3);printf("當前雙向鏈表內容為：");DLTPrint(head);printf("執行頭插操作，插入 4\n");DLTPushFront(head, 4);printf("當前雙向鏈表內容為：");DLTPrint(head);DLTDestroy(head);printf("雙向鏈表已銷毀\n");print_separator();
}// 測試雙向鏈表的尾刪和頭刪功能
void test02() 
{printf("開始測試雙向鏈表的尾刪和頭刪功能\n");DLTNode* head = DLTInit();printf("執行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("執行尾插操作，插入 2\n");DLTPushBack(head, 2);printf("執行尾插操作，插入 3\n");DLTPushBack(head, 3);printf("插入元素后，當前雙向鏈表內容為：");DLTPrint(head);printf("執行尾刪操作\n");DLTPopBack(head);printf("尾刪操作后，當前雙向鏈表內容為：");DLTPrint(head);printf("執行頭刪操作\n");DLTPopFront(head);printf("頭刪操作后，當前雙向鏈表內容為：");DLTPrint(head);DLTDestroy(head);printf("雙向鏈表已銷毀\n");print_separator();
}// 測試雙向鏈表的查找、指定節點后插入和指定節點刪除功能
void test03() 
{printf("開始測試雙向鏈表的查找、指定節點后插入和指定節點刪除功能\n");DLTNode* head = DLTInit();printf("執行尾插操作，插入 1\n");DLTPushBack(head, 1);printf("執行尾插操作，插入 3\n");DLTPushBack(head, 3);printf("插入元素后，當前雙向鏈表內容為：");DLTPrint(head);printf("查找值為 1 的節點\n");DLTNode* pos = DLTFind(head, 1);if (pos != NULL) {printf("已找到值為 1 的節點，執行在該節點后插入 2 的操作\n");DLTInsert(pos, 2);printf("插入操作后，當前雙向鏈表內容為：");DLTPrint(head);printf("刪除值為 1 的節點\n");DLTErase(pos);printf("刪除操作后，當前雙向鏈表內容為：");DLTPrint(head);}else {printf("未找到值為 1 的節點\n");}DLTDestroy(head);printf("雙向鏈表已銷毀\n");print_separator();
}int main() 
{test01();test02();test03();printf("所有雙向鏈表接口函數測試完成\n");return 0;
}

運行結果

心得總結

鏈表類型	空鏈表判斷	斷言示例
單鏈表	*pphead == NULL	assert(*pphead);
雙向帶頭鏈表	phead->next == phead	assert(phead->next != phead);

順序表和鏈表的區別有哪些？

對比維度	順序表（數組實現）	鏈表
存儲結構	物理存儲連續	邏輯連續，物理存儲不連續（通過指針鏈接）
隨機訪問	支持，O(1) 時間復雜度	不支持，需遍歷，O(n) 時間復雜度
插入/刪除效率	可能需要搬移元素，平均 O(n)	只需修改指針，已知位置時 O(1)
空間開銷	只需存儲數據，無額外開銷	每個結點需額外存儲指針（存儲密度較低）
擴容方式	動態順序表需重新分配內存并拷貝數據（代價高）	無容量限制，隨時插入新結點
內存碎片	無	可能產生碎片（頻繁動態分配釋放）
緩存命中率	高（空間局部性好）	低（結點分散存儲）
適用場景	1. 頻繁訪問 2. 數據量可預估 3. 強調存儲效率	1. 頻繁插入/刪除 2. 數據規模變化大 3. 內存靈活性要求高