数据结构基础：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;
}

这里申请了新节点，并将对应的数据存入节点中。接下来只需要将各个节点连接起来即可。

尾插

在链表尾部添加新节点。注意使用二级指针 pphead，因为如果链表为空，需要修改头指针本身。

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;
    }
}

头插

在链表头部添加新节点。同样需要二级指针来更新头指针。

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

尾删

删除链表尾部的节点。需要处理链表只有一个节点的特殊情况，否则无法找到前驱节点。

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;
}

查找

遍历链表寻找特定值，不需要传二级指针，因为不修改链表结构。

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

在指定位置之前插入数据

需要在 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->next 之间插入新节点。

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

删除 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->next 节点并释放。

void SLTEraseAfter(SLTNode* pos) {
    assert(pos && pos->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;
}

链表的分类

链表的结构非常多样，组合起来有多种形式。虽然有这么多的链表结构，但我们实际中最常用的是两种：

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

掌握单链表是理解更复杂链表结构的基础，建议在实际编码中多动手练习指针操作。