【初阶数据结构】单链表：数据的串联艺术

用户11872857

发布于 2025-12-17 15:52:08

3670

前言

🔍在数据结构的世界中，链表是一种独特的存在。它不像数组那样，需要一块连续的内存空间来存储数据，而是通过指针将一个个节点 “串联” 起来，实现数据的存储与逻辑顺序的表达。

📚 初阶数据结构

-【时间复杂度+空间复杂度】

-【顺序表】

一、线性表与链表的关联

线性表是 n 个具有相同特性的数据元素的有限序列，在逻辑上呈线性结构（连续的一条直线），物理存储上通常以数组（顺序表）和链式结构（链表）两种形式存在。链表作为线性表的重要实现方式，核心特点是物理存储非连续、逻辑顺序通过指针链接实现，可解决顺序表中间 / 头部插入删除效率低、增容消耗大等问题。

二、链表的概念及结构

2.1 核心定义

链表是物理存储结构非连续、非顺序，线性结构，数据元素的逻辑顺序通过链表中节点的指针链接次序实现。每个节点包含 “数据域”（存储数据）和 “指针域”（指向后续节点）两部分，从堆上申请的节点空间可能连续也可能不连续，但通过指针可形成逻辑上的连续链2。

2.2 关键特性与结构示例

逻辑与物理结构差异：链式结构在逻辑上是连续的，但物理上不一定连续；从堆上申请的空间，两次申请可能连续也可能不连续3。
结构示例（32 位系统 int 类型数据）：假设节点数据域为 int 类型（4 字节）、指针域为 4 字节，单个节点共 8 字节。若链表含数据 1、2、3、4，首节点地址为0x0012FFA0，数据为 1 且指针指向0x0012FFB0（第二个节点），第二个节点指向0x0012FFC0（第三个节点），第三个节点指向0x0012FFD0（第四个节点），第四个节点指针指向NULL（链表结尾）；即使节点地址为0x0012FFA0、0x0012FFC0、0x0012FFB0等非连续地址，仍能通过指针保证逻辑连续。

三、链表的分类

实际中链表的结构非常多样，通过 “单向或者双向”“带头或者不带头”“循环或者非循环” 三个维度组合，可形成 8 种链表结构。具体分类维度如下：

按指针方向分：单向（每个节点仅含一个指向后续节点的指针）、双向（每个节点含指向后续和前驱节点的两个指针）；
按是否含哨兵头节点分：带头（含不存储有效数据的哨兵头节点）、不带头（无哨兵头节点，首节点直接存储有效数据）；
按是否形成闭环分：循环（尾节点指针指向首节点或头节点，形成闭环）、非循环（尾节点指针指向NULL，有明确结尾）。

虽然有 8 种结构，但实际中最常用的两种链表结构为单链表和双链表：

单链表：是 “无头单向非循环链表”，结构简单。每个节点包含数据域和一个指针域，指针域仅指向后续节点，尾节点指针指向NULL。它一般不会单独用来存数据，更多作为其他数据结构的子结构（如哈希桶、图的邻接表），且在笔试面试中频繁出现。
双链表：是“带头双向循环链表”，结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

四、单链表的接口实现

4.1 节点结构定义

先定义数据类型与节点结构，数据类型用SLTDateType表示（可按需修改为char、float等）：

typedef int SLTDateType; // 单链表数据类型，可按需修改
typedef struct SListNode 
{
    SLTDateType data;       // 数据域：存储节点数据
    struct SListNode* next; // 指针域：指向后续节点
} SListNode;

4.2 核心接口实现

（1）辅助接口：动态申请节点

所有增删操作需先创建新节点，此接口负责动态申请内存并初始化：

// 动态申请一个节点，数据域为x，指针域初始化为NULL
SListNode* BuySListNode(SLTDateType x) 
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    if (newNode == NULL) 
    { 
        // 检查内存申请是否成功
        perror("malloc fail");
        return NULL;
    }
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

（2）单链表打印

遍历链表打印数据，用NULL标识结尾，避免修改原头指针：

void SListPrint(SListNode* plist) 
{
    SListNode* cur = plist; // 用cur遍历，保护原头指针
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n"); // 标识链表结束
}

（3）单链表尾插

需处理 “链表为空” 和 “链表非空” 两种场景，因可能修改头指针，传入头指针地址（二级指针）：

void SListPushBack(SListNode** pplist, SLTDateType x) 
{
    assert(pplist); // 确保二级指针有效

    SListNode* newNode = BuySListNode(x);
    // 场景1：链表为空，新节点即为首节点
    if (*pplist == NULL) 
    {
        *pplist = newNode;
    }
    // 场景2：链表非空，遍历找到尾节点（next为NULL），尾节点next指向新节点
    else 
    {
        SListNode* tail = *pplist;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newNode;
    }
}

（4）单链表头插

新节点成为首节点，其next指向原首节点，通过二级指针修改头指针：

void SListPushFront(SListNode** pplist, SLTDateType x) 
{
    assert(pplist);

    SListNode* newNode = BuySListNode(x);
    newNode->next = *pplist; // 新节点next指向原首节点
    *pplist = newNode;       // 头指针更新为新节点
}

（5）单链表尾删

禁止删除空链表，处理 “仅 1 个节点” 和 “多个节点” 场景：

void SListPopBack(SListNode** pplist)
{
    assert(pplist);
    assert(*pplist); // 禁止删除空链表

    // 场景1：仅1个节点，释放后置空头指针
    if ((*pplist)->next == NULL) 
    {
        free(*pplist);
        *pplist = NULL;
    }
    // 场景2：多个节点，找到倒数第二个节点，释放尾节点并置其next为NULL
    else 
    {
        SListNode* prev = NULL;
        SListNode* tail = *pplist;
        while (tail->next != NULL) 
        {
            prev = tail;       // prev记录当前节点（最终为倒数第二个节点）
            tail = tail->next; // tail遍历至尾节点
        }
        free(tail);
        prev->next = NULL;
    }
}

（6）单链表头删

禁止删除空链表，释放原首节点后更新头指针：

void SListPopFront(SListNode** pplist) 
{
    assert(pplist);
    assert(*pplist != NULL); // 禁止删除空链表

    SListNode* oldHead = *pplist; // 保存原首节点
    *pplist = oldHead->next;      // 头指针指向原首节点的下一个节点
    free(oldHead);                // 释放原首节点
    oldHead = NULL;               // 避免野指针
}

（7）单链表查找

遍历链表，返回目标数据节点指针，未找到则返回NULL：

SListNode* SListFind(SListNode* plist, SLTDateType x) 
{
    SListNode* cur = plist;
    while (cur != NULL) 
    {
        if (cur->data == x) 
        {
            return cur; // 找到目标节点，返回指针
        }
        cur = cur->next;
    }
    return NULL; // 未找到，返回NULL
}

（8）单链表在 pos 位置之后插入

选择 “pos 之后插入” 是因无需遍历找前驱节点，效率更高（O (1)）：

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    assert(pos != NULL); // 确保pos是有效节点

    SListNode* newNode = BuySListNode(x);
    newNode->next = pos->next; // 新节点next指向pos的原后继
    pos->next = newNode;       // pos的next指向新节点
}

（9）单链表删除 pos 位置之后的节点

无需找前驱节点，直接修改指针并释放节点：

void SListEraseAfter(SListNode* pos) 
{
    assert(pos != NULL);
    assert(pos->next != NULL); // 确保pos之后有节点可删

    SListNode* delNode = pos->next; // 保存待删除节点
    pos->next = delNode->next;      // pos的next指向delNode的后继
    free(delNode);                  // 释放待删除节点
    delNode = NULL;                 // 避免野指针
}

（10）单链表销毁

遍历释放所有节点，避免内存泄漏，最后置空头指针：

void SListDestory(SListNode** pplist) 
{
    assert(pplist);

    SListNode* cur = *pplist;
    while (cur != NULL) 
    {
        SListNode* nextNode = cur->next; // 先保存下一个节点
        free(cur);                       // 释放当前节点
        cur = nextNode;                  // 移动到下一个节点
    }
    *pplist = NULL; // 置空头指针，避免野指针
}

五、单向链表的优缺点

5.1 优点

插入 / 删除效率高：头插、尾插（找到尾节点后）、pos 后插入均为 O (1)，无需像顺序表那样搬移大量元素（顺序表中间 / 头部插入删除时间复杂度为 O (N)）
无扩容浪费：节点动态申请，随用随建，不存在顺序表 “增容浪费” 或 “容量不足” 的问题（顺序表增容需申请新空间、拷贝数据、释放旧空间，还可能浪费部分空间）
内存利用率灵活：物理存储非连续，无需提前申请大块连续内存，适合数据量不确定的场景

5.2 缺点

不支持随机访问：访问第 k 个节点需从首节点遍历，时间复杂度 O (N)，无法像顺序表那样通过下标直接访问（O (1)）
存储密度低：每个节点需额外存储next指针，增加内存开销（如 int 数据节点，指针占比 50%）
缓存利用率低：节点物理分散，无法利用 CPU 缓存的 “局部性原理”（顺序表数组连续，缓存命中率高）

六、单、双链表、顺序表效率对比

操作类型	顺序表（数组实现）	链表（单链表，已知头尾指针）	链表（双链表，已知头尾指针）
头插 / 头删	O (n)（需移动所有元素）	O (1)（直接改头指针）	O (1)（直接改头指针）
尾插 / 尾删	O (1)（直接操作数组末尾）	O (1)（已知尾指针）	O (1)（已知尾指针）
中间插入 / 删除	O (n)（需移动目标后元素）	O (n)（需遍历找目标前驱）	O(1)（已知目标节点时，直接改前后指针）O (n)（未知目标节点时，需遍历定位）

局部效率有高低：
- 头插 / 头删：链表（O (1)）远高于顺序表（O (n)）；
- 尾插 / 尾删：两者效率一致（O (1)）；
- 中间操作：双链表（已知目标节点时 O (1)）高于顺序表 / 单链表（O (n)）。
整体无优劣，场景决定选择：
- 选顺序表：需要随机访问（O (1)）+ 尾操作频繁；
- 选单链表：头操作频繁 + 对空间开销敏感；
- 选双链表：中间操作频繁（且能定位目标节点）+ 双端操作需求。

最终结论：插入删除的效率差异由 “操作位置” 决定，两类结构没有绝对更优，只看业务中 “高频操作是什么”

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构