数据结构：单链表详解与 C 语言实现

源文件 (SList.c)

单链表的打印

遍历链表，输出每个节点的数据，直到遇到空指针。

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

单链表申请新节点内存

这是创建节点的基础函数，负责从堆上分配内存并初始化。

SLTNode* SLTBuyNode(SLTDataType x) {
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL) {
        perror("malloc fail!");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

这里是申请新节点，并且把对应的数据存入节点中，所以接下来只需要将各个节点连接起来（链表中的指针）。

尾插

在链表尾部添加新节点。如果链表为空，新节点直接成为头结点；否则需要遍历到尾端再连接。

// 尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    // 申请新节点
    SLTNode* newnode = SLTBuyNode(x);
    // 链表为空
    if (*pphead == NULL) {
        *pphead = newnode;
    } else {
        SLTNode* ptail = *pphead;
        while (ptail->next != NULL) {
            ptail = ptail->next;
        }
        // 找到了尾结点 ptail，将新节点接在后面
        ptail->next = newnode;
    }
}

传址调用，使用 SLTNode** pphead，不然无法修改 SLTNode* phead 结构体指针。需要做出特殊判断，当链表为空的时候。

头插

在链表头部添加新节点。新节点的 next 指向原头结点，然后更新头指针。

// 头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead);
    SLTNode* newnode = SLTBuyNode(x);
    // newnode -> *pphead
    newnode->next = *pphead;
    *pphead = newnode;
}

尾删

删除链表尾部的节点。需要找到倒数第二个节点，将其 next 置为 NULL，并释放原尾节点。注意处理只有一个节点的情况。

// 尾删
void SLTPopBack(SLTNode** pphead) {
    // 链表为空不能删除
    assert(pphead && *pphead);
    // 链表只有一个节点的情况
    if ((*pphead)->next == NULL) {
        free(*pphead);
        *pphead = NULL;
    } else {
        SLTNode* prev = NULL;
        SLTNode* ptail = *pphead;
        while (ptail->next) {
            prev = ptail;
            ptail = ptail->next;
        }
        // prev -> ptail
        prev->next = NULL;
        free(ptail);
        ptail = NULL;
    }
}

处理特殊情况，链表只有一个节点的情况。链表为空不能删除。

头删

删除链表头部的节点。先保存下一个节点地址，释放当前头结点，然后更新头指针。

// 头删
void SLTPopFront(SLTNode** pphead) {
    assert(pphead && *pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

查找

遍历链表寻找值为 x 的节点。不需要传二级指针，因为只读不写头指针。

// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) {
        if (pcur->data == x) {
            return pcur;
        }
        pcur = pcur->next;
    }
    // 未找到
    return NULL;
}

在指定位置之前插入数据

在 pos 节点之前插入新节点。如果 pos 是头结点，则退化为头插操作；否则需要找到 pos 的前驱节点。

// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
    assert(pphead && pos);
    SLTNode* newnode = SLTBuyNode(x);
    // pos 指向头结点
    if (pos == *pphead) {
        SLTPushFront(pphead, x);
    } else {
        // 找 pos 的前一个节点
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        // prev -> newnode -> pos
        prev->next = newnode;
        newnode->next = pos;
    }
}

pos 不能为空指针。特殊情况，pos 指向头结点。

在指定位置之后插入数据

在 pos 节点之后插入新节点。逻辑相对简单，只需调整指针指向。

// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
    assert(pos);
    SLTNode* newnode = SLTBuyNode(x);
    // pos -> newnode -> pos->next
    newnode->next = pos->next;
    pos->next = newnode;
}

删除 pos 结点

删除指定的 pos 节点。如果 pos 是头结点，执行头删；否则找到前驱节点，断开连接并释放内存。

// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
    assert(pphead && pos);
    // pos 刚好就是头结点——头删
    if (pos == *pphead) {
        SLTPopFront(pphead);
    } else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) {
            prev = prev->next;
        }
        // prev -> pos->next
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

pos 不能为空指针。特殊情况，pos 刚好就是头结点—头删。

删除 pos 之后的结点

删除 pos 节点的下一个节点。需要确保 pos 和 pos->next 都不为空。

// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->next);
    // pos -> del -> del->next
    SLTNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

销毁链表

遍历整个链表，逐个释放节点内存，最后将头指针置空。

// 销毁链表
void SListDestroy(SLTNode** pphead) {
    assert(pphead);
    SLTNode* pcur = *pphead;
    while (pcur) {
        SLTNode* next = pcur->next;
        free(pcur);
        pcur = next;
    }
    *pphead = NULL;
}

链表的分类

链表的结构非常多样，以下情况组合起来就有 8 种（2 x 2 x 2）链表结构：有无头结点、单向/双向、循环/非循环。

虽然有这么多的链表结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

在实际开发中，理解单链表是基础，掌握其内存模型和指针操作对于深入理解 C/C++ 至关重要。