数据结构：单链表与双链表的操作详解

• SList.h：单链表结构声明单链表的方法
• SList.c：实现单链表的方法
• test.c：测试文件

SList.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

// 定义节点的结构
// 数据 + 指向下一个节点的指针
typedef int SLDataType;
typedef struct SListNode {
    SLDataType data;
    struct SListNode* next;
} SLTNode;

typedef int SLDataType; 之所以这样重命名定义是为了后期有大量代码时，此时输入的不再是 int 类型，可能是 char、double 类型，方便修改。

typedef struct SListNode { }SLTNode; 这样是为了更方便的进行调用。

3.2 单链表的打印

首先在头文件定义一下打印的声明，使其指向链表的第一个节点。

SList.h

void SLTPrint(SLTNode* phead);

然后根据定义来实现打印效果。先定义一个指针指向传来的头结点，然后我们知道只要链表不指向空那么这个链表中就有相关的元素，此时我们就可以打印存在该节点中的值，然后再让其指向下一个节点。

SList.c

#include "SList.h"

void SLTPrint(SLTNode* phead) {
    SLTNode* pcur = phead;
    while (pcur) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

因为我们并没有在定义中构造节点，所以我们需要先开空间创造链表，之后用 next 将每个节点连一起，最后调用打印函数即可。

test.c

#include "SList.h"

void SListTest01() {
    // 链表是由一个个节点构成
    // 创建几个节点
    SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
    node1->data = 1;
    SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
    node2->data = 2;
    SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
    node3->data = 3;
    SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
    node4->data = 4;
    // 将四个节点连接起来
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = NULL;
    // 调用链表的打印
    SLTNode* plist = node1;
    SLTPrint(plist);
}

int main() {
    SListTest01();
    return 0;
}

实际上我们并不会这样手动一个一个节点的创建，我们是用空链表通过插入的方式让链表里面增加数据。

3.3 插入节点

因为我们在插入链表时创建新结点，所以先开创一块新空间，让开创的空间的数据存储传值 x，然后链表的 next 指针指向 NULL。

SList.c

// 新节点
SLTNode* SLTBuyNode(SLDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
}

3.3.1 尾插

首先定义头文件，指明要插入的头节点位置以及要插入的值。

SList.h

void SLTPushBack(SLTNode** pphead, SLDataType x);

然后定义尾插相关的操作。如果是空链表则指向新节点，当链表不为空时，则寻找最后一个节点，即当 ptail->next = NULL 时便是最后的节点，然后让其指向新节点。

SList.c

// 要先找到尾节点，再将尾节点和新节点连接
void SLTPushBack(SLTNode** pphead, SLDataType x) {
    SLTNode* newnode = SLTBuyNode(x);
    // 空链表
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        // 找尾
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            ptail = ptail->next;
        }
        // ptail 指向的是尾节点
        ptail->next = newnode;
    }
}

然后测试一下是否代码可行

test.c

void SListTest02() {
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 1);
    SLTPushBack(&plist, 2);
    SLTPushBack(&plist, 3);
    SLTPushBack(&plist, 4);
    SLTPrint(plist);
}

测试结果发现形参变了实参没变，相关的值并没有传上，说明传值操作并不符合。因此想让形参改变实参就应改为传址操作。之所以这样操作是因为头指针可能随操作变化，所以需要二级指针来修改它。

那么尾插的相关操作需要改为：

SList.h

void SLTPushBack(SLTNode** pphead, SLDataType x);

SList.c

// 尾插
// 要先找到尾节点，再将尾节点和新节点连接
void SLTPushBack(SLTNode** pphead, SLDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    // 空链表
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        // 找尾
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            ptail = ptail->next;
        }
        // ptail 指向的是尾节点
        ptail->next = newnode;
    }
}

因为不能对一个空指针进行解引用，需要加断言。

pphead 为空则就不能对其解引用 *pphead 可以为空，说明当前第一个节点地址为空，表示空链表，可以为空

3.3.2 头插

首先定义头文件，指明要插入的头节点位置以及要插入的值。

SList.h

void SLTPushFront(SLTNode** pphead, SLDataType x);

接着写出头插的实现函数，先创建一个新的节点，然后让新节点的下一位指向新节点，最后新节点变成头节点。因为头插的过程中空链表和非空链表的实现一样，所以无需分开来写。

SList.c

void SLTPushFront(SLTNode** pphead, SLDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

3.4 删除节点

3.4.1 尾删

首先定义头文件，指明要删除的链表头节点在哪，又因为可能会影响头节点，则需要用二级指针。

SList.h

void SLTPopBack(SLTNode** pphead);

尾删的过程中因为想要删除那么链表不能为空，所以需要用 assert 断言一下。然后链表分为两种情况一种是只有一个节点，另一种是有多个节点。

• 当只有一个节点时，释放这个头节点，然后置为空
• 当有多个节点时，寻找尾节点，然后释放掉，同时使尾节点的前一个节点置为空防止变成野指针

SList.c

void SLTPopBack(SLTNode** pphead) {
    // 链表不能为空
    assert(pphead && *pphead);
    // 链表只要一个结点
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    }
    // 链表有多个结点
    else {
        // 要找尾节点和前一个结点
        SLTNode* prev = *pphead;
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        // 得到尾节点和前一个结点
        free(ptail);
        ptail = NULL;
        prev->next = NULL;
    }
}

3.4.2 头删

首先定义头文件，指明要删除的链表头节点在哪，又因为可能会影响头节点，则需要用二级指针。

SList.h

void SLTPopFront(SLTNode** pphead);

接着写出头删的实现函数，首先链表不能为空，然后先找到第二个节点存储起来防止找不到第二个节点，最后释放头节点并让第二个节点为新的头节点。因为头删的过程中空链表和非空链表的实现一样，所以无需分开来写。

SList.c

void SLTPopFront(SLTNode** pphead) {
    // 链表不能为空
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

3.5 查找

首先定义头文件，指明要查找的链表头节点在哪以及要查找的元素，因为不会影响头节点，则就不需要用二级指针。

SList.h

SLTNode* SLTFind(SLTNode* phead, SLDataType x);

单链表只能从头开始查找（顺序查找），所以从头节点开始寻找有没有要查找的元素，直至头节点指向空为止。但是经过循环 phead == NULL，如果再遍历原链表则找不到链表的第一个结点。

SList.c

SLTNode* SLTFind(SLTNode* phead, SLDataType x) {
    // 如果不设置一个变量，那么经过循环 phead == NULL
    // 如果再遍历原链表则找不到链表的第一个结点
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    // 此时 pcur == NULL
    return NULL;
}

3.6 指定位置插入/删除

3.6.1 指定位置之前插入数据

首先定义头文件，指明要插入位置之前在哪以及插入的是什么元素，又因为可能会影响头节点，则需要用二级指针。

SList.h

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);

接着实现指定位置之前插入的函数，首先要断言传指针不能为空以及链表不能为空，以及 pos 也不能为空。接着创建新节点，然后遍历链表寻找 pos 节点之前的节点。最后让 pos 前一个节点的 next 指针指向新节点，新节点的 next 指针指向 pos 的节点。

还要注意如果 pos == *pphead，则为头插，直接调用头插操作即可。

SList.c

// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x) {
    // 如果链表为空，则 pos 也为空
    // 不能在指定为空的结点插入数据
    assert(pphead && *pphead);
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    // 若 pos == *pphead; 说明是头插
    if (pos == *pphead) {
        SLTPushFront(pphead, x);
    } else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        // prev -> newnode -> pos
        newnode->next = pos;
        prev->next = newnode;
    }
}

3.6.2 在指定位置之后插入数据

首先定义头文件，指明要查找的链表指定位置的节点在哪以及要查找的元素，因为不需要头节点，故不会影响头节点，则就不需要用二级指针。

SList.h

void SLTInsertAfter(SLTNode* pos, SLDataType x);

接着实现指定位置之后插入的函数，首先 pos 不能为空，接着创建新节点。创建的新节点要先指向 pos->next，然后在使 pos 的下一个节点指向新节点。如果这两种顺序搞反了会造成 pos 的下一个指针丢失。

SList.c

void SLTInsertAfter(SLTNode* pos, SLDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    // pos -> newnode -> pos->next
    newnode->next = pos->next;
    pos->next = newnode;
}

3.6.3 删除 pos 节点

首先定义头文件，指明要删除的指定位置的元素。因为指定的位置可能会是头节点，所以需要传头节点和指定位置。因为可能会影响头节点，则需要用二级指针。

SList.h

void SLTErase(SLTNode** pphead, SLTNode* pos);

因为传了头节点时，所以需要断言传的地址不能为空以及链表不能为空。pos 的位置有两种情况，一种是在头节点，另一种不是头节点。

• 在头节点上：相当于头删
• 不再头节点上时：需要找 pos 前后两个位置的节点，让 pos 前的节点指向 pos 的下一个节点，然后释放 pos 节点并置为空。

SList.c

void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && *pphead);
    assert(pos);
    // 不能删除一个空结点
    // pos 是头节点
    if (pos == *pphead) {
        // 头删
        SLTNode* next = (*pphead)->next;
        free(*pphead);
        *pphead = next;
    }
    // pos 不是头节点
    else {
        // 前一个结点 prev，后一个结点 pos->next
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        // prev -> pos -> pos->next
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

3.6.4 删除 pos 之后的节点

首先定义头文件，指明指定的位置的元素，因为不需要头节点，故不会影响头节点，则就不需要用二级指针。

void SLTEraseAfter(SLTNode* pos);

删除指定位置之后的节点，只需要删除下一个节点的位置，并让指定位置指向下一个的下一个节点。

void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->next);
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

3.7 销毁链表

首先定义头文件，指明要销毁链表的头节点。因为销毁的是从头节点开始，头节点地址会变，所以需要传头节点和指定位置。因为会影响头节点，则需要用二级指针。

SList.h

void SListDestroy(SLTNode** pphead);

接着实现销毁链表的函数，销毁的链表不能为空。销毁链表从头节点开始一点点释放，直至销毁完，销毁完后头节点要置为空。

SList.c

void SListDestroy(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    // 此时 pcur 为空，说明链表所有元素都释放掉了
    *pphead = NULL;
    // 头节点也要置为空
}

4. 双链表

由图可知，带头双向链表需要当前位置的元素，下一个节点的位置和上一个节点的位置，所以定义的时候就需要比单链表多定义一个前一个结点。

同时带头，则说明需要有一个哨兵为作为头节点。

4.1 定义带头双链表

因为双链表比单链表多一个前节点，所以定义的时候需要多定义一个前节点。同时因为需要带头，所以初始化中需要一个头节点，还需要初始化一下哨兵位。

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode {
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
} LTNode;

// 声明双向链表中提供的方法
// 初始化
void LTInit(LTNode** pphead);

因为初始化头节点时需要开创一个新节点，所以先定义创建新节点的实现函数。因为创建的是循环双链表，所以前一个节点和后一个节点的指针要指向自己。

哨兵位是不需要有效的值，但定义申请节点必须传值，所以我们传 -1，表示不是有效位置。

List.c

#include "List.h"

// 申请结点
LTNode* LTBuyNode(LTDataType x) {
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    if (node == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    node->data = x;
    node->next = node->prev = node;
    return node;
}

// 初始化
void LTInit(LTNode** pphead) {
    // 给双向链表创建一个哨兵位
    *pphead = LTBuyNode(-1);
}

test.c

#include "List.h"

void ListTest01() {
    // 指向哨兵位节点的指针
    LTNode* plist = NULL;
    LTInit(&plist);
}

int main() {
    ListTest01();
    return 0;
}

打印链表的实现

List.h

void LTPrint(LTNode* phead);

List.c

void LTPrint(LTNode* phead) {
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("\n");
}

4.2 插入节点

4.2.1 尾插

首先定义一下尾插的声明，因为哨兵位节点相当于头节点，哨兵位节点不能删除并且节点的地址也不发生改变，所以我们仅需传一级指针。因此需要链表头节点的位置和插入的元素是什么。

List.h

void LTPushBack(LTNode* phead, LTDataType x);

接着实现尾插操作。因为有哨兵位节点，所以当为空链表时就不需要考虑头节点为空的情况。我们需要申请一个新节点，然后让新节点的前一个结点指向原来的尾节点，尾节点的下一个节点指向新节点，新节点的下一个节点指向头节点，头节点的前一个节点指向新节点。

List.c

void LTPushBack(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    // phead -> phead->prev -> newnode -> newnode->prev -> phead
    newnode->prev = phead->prev;
    newnode->next = phead;
    phead->prev->next = newnode;
    phead->prev = newnode;
}

4.2.2 头插

头插的相关操作和尾插类似。

List.h

void LTPushFront(LTNode* phead, LTDataType x);

List.c

void LTPushFront(LTNode* phead, LTDataType x) {
    assert(phead);
    LTNode* newnode = LTBuyNode(x);
    newnode->next = phead->next;
    newnode->prev = phead;
    phead->next->prev = newnode;
    phead->next = newnode;
}

双向链表为空，此时链表只有一个头结点，即只有一个哨兵位。 头结点为空 phead = NULL; 则这不是一个有效的双向链表

4.3 删除节点

4.3.1 尾删

首先定义一下尾删的声明，因为哨兵位节点相当于头节点，哨兵位节点不能删除并且节点的地址也不发生改变，所以我们仅需传一级指针。因此我们只需要链表头节点的位置即可。

List.h

void LTPopBack(LTNode* phead);

尾删的实现，首先链表不能为空且有效，然后根据头节点的前一个指针找到尾节点，使头节点的前一个指针指向倒数第二个节点，倒数第二个节点的后一个指针指向头节点。然后释放尾节点并指向空防止成为野指针。

List.c

void LTPopBack(LTNode* phead) {
    // 链表必须有效且链表不能为空（只有一个哨兵位）
    assert(phead && phead->next != phead);
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    // 删除 del 结点
    free(del);
    del = NULL;
}

4.3.2 头删

头删的操作和尾删类似。

List.h

void LTPopFront(LTNode* phead);

List.c

void LTPopFront(LTNode* phead) {
    assert(phead && phead->next != phead);
    LTNode* del = phead->next;
    phead->next = del->next;
    del->next->prev = phead;
    // 删除 del 结点
    free(del);
    del = NULL;
}

4.4 查找

查找时需要从第一个实际节点开始遍历，以及要查找的数据值，故查找声明写法如下。

List.h

LTNode* LTFind(LTNode* phead, LTDataType x);

从 phead->next 开始，跳过不存储数据的头节点，提高效率。循环条件 pcur != phead，双向循环链表的特性是最后一个节点的 next 指向头节点。当遍历回到头节点时，说明已遍历所有实际节点，循环结束。逐步移动指针，通过 pcur = pcur->next 遍历每个节点，直到找到匹配值或遍历完成。

List.c

// 查找
LTNode* LTFind(LTNode* phead, LTDataType x) {
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    // 没有找到
    return NULL;
}

4.5 在指定位置插入/删除

4.5.1 在 pos 位置之后插入数据

在指定位置插入时需要从第一个实际节点开始遍历，以及要插入的数据值，故查找声明写法如下。

List.h

void LTInsert(LTNode* pos, LTDataType x);

和尾插头插类似。

List.c

void LTInsert(LTNode* pos, LTDataType x) {
    assert(pos);
    LTNode* newnode = LTBuyNode(x);
    newnode->next = pos->next;
    newnode->prev = pos;
    pos->next->prev = newnode;
    pos->next = newnode;
}

4.5.2 删除 pos 结点

仿照尾删头删。

List.h

void LTErase(LTNode* pos);

List.c

void LTErase(LTNode* pos) {
    // pos 理论上来说不能为 phead，但是没有参数 phead，无法增加校验
    assert(pos);
    pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);
    pos = NULL;
}

test.c

LTErase(find);
find = NULL;
// pos 置空，但不会影响实参，此时 find 是野指针
LTPrint(plist);

List.h

// 另外一种初始化
LTNode* LTInit();
// 以返回值形式把哨兵位返回

List.c

// 另外一种初始化
LTNode* LTInit() {
    LTNode* phead = LTBuyNode(-1);
    return phead;
}

test.c

LTNode* plist = LTInit();

4.6 销毁链表

销毁链表需要知道是哪个链表，故要传头节点。

List.h

void LTDestroy(LTNode* phead);

使用 assert 确保传入的指针非空，避免对空指针进行操作导致程序崩溃。从 phead->next 开始：头节点是哨兵节点，不存储实际数据，所以从第一个数据节点开始释放。循环条件 pcur != phead，双向循环链表中，最后一个节点的 next 指向头节点。当 pcur 回到头节点时，说明所有数据节点已遍历完毕。保存下一个节点地址，在释放当前节点前，必须提前保存其 next 指针，否则释放后无法访问下一个节点，导致内存泄漏。

List.c

void LTDestroy(LTNode* phead) {
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead) {
        LTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    // 此时 pcur 指向 phead，而 phead 还没销毁
    free(phead);
    phead = NULL;
}

phead 是函数的形参，是外部 plist 的副本。函数内 phead = NULL 只影响这个形参。函数返回后，外部的 plist 仍然指向已释放的内存地址，故需要手动置空。

test.c

LTDestroy(plist);
plist = NULL;
// 手动置空
LTPrint(plist);

结语

链表的核心在于指针操作，单链表适合简单场景，双链表以空间换时间提升操作效率。实际应用中需注意内存管理和边界条件（如空链表、头尾节点）。通过反复练习插入、删除等操作，可深入理解链表的动态特性与指针灵活性。