在数据结构中，我们知道顺序表虽然尾插的时间复杂度O(1),但其无论是
中间/头部的插⼊删除（时间复杂度O(N)),还是增容时所面临空间的消耗都不可忽视，思考我们当如何解决以上问题呢？

一、什么是链表？其与数组的区别是什么？

1、链表：一种物理上不连续，但数据元素的逻辑顺序通过链表中指针次序所链接的存储结构链表结构

2、其与数组的区别：

对比维度 数组（顺序表） 单链表（无尾指针）
内存存储 物理内存连续 内存碎片化、不连续
访问方式 支持，arr[i] 直接取，O(1) 不支持，必须从头遍历，O(n)
头部插入/删除 O(n)，所有元素后移 O(1)，仅修改指针指向
尾部插入 均摊O(1)，偶尔扩容拷贝 O(n)，每次要遍历到末尾
中间插入/删除 O(n)，后续元素整体移位 O(n)，需要先找到目标位置
空间开销 仅存储数据，额外开销小 每个节点多存1个next指针，额外内存开销大
容量大小 固定/动态扩容，扩容有性能损耗 无固定上限，按需申请节点，无需扩容

3、链表结构(以单链表SLT [Single Linked Table]为例）

#include <stdio.h>
#include <stdlib.h>

// 1. 定义单链表节点结构体
struct SLTNode
{
    int data;               // 数据域：存储节点数据，可按需更换数据类型
    struct SLTNode* next;   // 指针域：指向下一个节点的指针
};

// 2. 给结构体起别名，简化代码书写
typedef struct SLTNode Node;     // Node 等价于 struct SLTNode
typedef struct SLTNode* PNode;   // PNode 等价于 struct SLTNode*（节点指针）

采用struct关键字定义链表节点结构体，节点分为两部分：

  1. 数据域 int data：用于存储链表需要保存的数据，可按需更换数据类型；
  2. 指针域 struct SListNode* next：一级结构体指针，存储下一个相邻节点的内存地址，通过地址串联所有节点形成链式结构。

使用typedef对结构体及结构体指针重命名：

  • Node：等价于 struct SLTNode，代表单个节点实体；
  • PNode：等价于 struct SLTNode*，代表节点指针，简化链表操作代码书写。

单链表逻辑特征：节点内存不连续，仅依靠next指针维系前后节点关系，尾部节点next指针置NULL代表链表结束。

二、链表的基本功能代码实现

1、工具函数：新建节点

/**
 * @brief 创建新节点并分配内存
 * @param x 节点存储的数据值
 * @return PNode 成功返回新节点指针，失败则程序退出
 */
PNode BuyNode(int x)
{
    // 动态分配节点内存
    PNode newNode = (PNode)malloc(sizeof(Node));
    
    // 检查内存分配是否成功
    if (newNode == NULL)
    {
        perror("malloc failed");
        exit(-1);  // 内存分配失败，程序退出
    }
    
    // 初始化节点数据
    newNode->data = x;     // 设置数据域
    newNode->next = NULL;  // 新节点next指针置空
    
    return newNode;  // 返回新节点指针
}

malloc动态开辟内存，初始化数据，next 置空，所有插入操作都会复用这个函数 注意事项 这里的newNode的类型是一级指针PNode，即newNode存有对应节点的地址，其指向一个节点


/**
 * 打印链表所有节点的数据（调试用）
 * phead 链表头指针（哨兵头节点）
 */
void SLTPrint(PNode phead)
{
    // 跳过哨兵头节点，从第一个有效节点开始
    PNode cur = phead->next;  
    
    // 遍历链表直到末尾
    while (cur != NULL)
    {
        printf("%d -> ", cur->data);  // 打印当前节点数据
        cur = cur->next;              // 移动到下一个节点
    }
    
    printf("NULL\n");  // 链表结束标记
}

这里phead是一个不存有数据的指针(哨兵头节点)，通过phead->next找到链表中第一个存有数据的有效节点，通过cur指针不断将节点的数据打印而出，并且将cur不断赋值成其所指向的下一节点的指针，直至cur变为空指针 打印截止

3、头插：在链表最前面插入数据


/**

 * 在链表头部插入新节点
 *  pphead 指向头指针的二级指针（用于修改外部头指针）
 *  x 要插入的数据
 */
void SLTPushFront(Node** pphead, LinkData x)
{
    // 创建新节点
    Node* newnode = BuyNode(x);
    
    // 新节点指向原头节点
    newnode->next = *pphead;  // 关键：二级指针解引用获取原头指针
    
    // 更新头指针指向新节点
    *pphead = newnode;  // 关键：通过二级指针修改外部头指针
}

// 错误写法：无法修改外部头指针
void SLTPushFront(Node* phead, LinkData x)
{
    Node* newnode = BuyNode(x);
    newnode->next = phead;
    phead = newnode;  // 错误：只修改函数内局部副本，外部原指针完全不变！
}

C 语言函数传参属于值拷贝传递，如果头插函数仅使用一级指针Node* phead作形参：当head为空指针时调用函数，head（NULL）的值被拷贝到形参phead中，此时phead也是NULL，此时虽然他们的值都是NULL,但地址却是不一样的，比如下方中的phead（值为NULL 存有地址0x0003） 自己地址为0x0002，传入后会出现新的phead（值NULL 存有地址0x0003），但其地址可能时0x00A3

在这里插入图片描述

4、尾插：在链表末尾插入数据(原理与3差不多) ps：这里的ptail是为了找到原链表的尾节点，不直接用pphead为了便于寻找的同时不改动头节点（当phead为空时）


void SLTPushBack(Node** pphead,LinkData x)
{
	Node* newnode=BuyNode(x);
	Node* ptail = *pphead;
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

5、其余本质上实现原理与之前一致，这里简要概述

// 头删
void SLTPopFront(Node** pphead);
// 尾删
void SLTPopBack(Node** pphead);
// 按值查找节点
Node* SLTFind(Node* phead, LinkData x);
// 在pos节点前插入数据
void SLTInsert(Node** pphead, LinkData x, Node* pos);
// 在pos节点后插入数据
void SLTInsertAfter(Node* pos, LinkData x);
// 释放整条链表并置空头指针
void SLTDestroy(Node** pphead);

各功能实现与简短说明

5.1. 头删 SLTPopFront
void SLTPopFront(Node** pphead)
{
    Node* del = *pphead;
    *pphead = del->next;
    free(del);
}

说明：可能修改头指针，使用二级指针；直接更新表头并释放原首节点，局部指针del在函数结束后 会销毁，所以不用置空

5.2. 尾删 SLTPopBack
void SLTPopBack(Node** pphead)
{
    // 链表仅有一个节点
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }
    // 找到倒数第二个节点
    Node* cur = *pphead;
    while (cur->next->next)
        cur = cur->next;
    free(cur->next);
    cur->next = NULL;
}

说明：链表只剩单个节点时需要置空头指针，必须二级指针。

5.3. 查找 SLTFind
Node* SLTFind(Node* phead, LinkData x)
{
    Node* cur = phead;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

说明：仅遍历读取数据，不修改表头与其他结点链接，一级指针即可。
（虽然不用cur也可以 因为函数的形参是值的拷贝，但工程规范尽量用cur表示头节点，进而不修改头节点）

5.4. 指定节点前插入 SLTInsert
void SLTInsert(Node** pphead, LinkData x, Node* pos)
{
    Node* newnode = BuyNode(x);
    
    // 插入位置为头部，更新表头
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
        return;
    }
    // 寻找 pos 的前驱节点
    Node* cur = *pphead;
    while (cur->next != pos)
        cur = cur->next;
    cur->next = newnode;
    newnode->next = pos;
    
}

说明：若 pos 是头节点，会改变链表头部，使用二级指针。

5.5. 指定结点后插入 SLTInsertAfter
void SLTInsertAfter(Node* pos, LinkData x)
{
    Node* newnode = BuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

说明：1、永远不会改动链表头部，仅修改节点内部 next，一级指针够用。2、需要先将指定结点的next先复制给newnode的next，不然会丢失pos的下一节点的地址

5.6. 销毁链表 SLTDestroy
void SLTDestroy(Node** pphead)
{
    assert(pphead);//断定不为空
    Node* cur = *pphead;
    while (cur)
    {
        Node* next = cur->next;
        free(cur);
        cur = next;
    }
    // 外部头指针置空，防止野指针
    *pphead = NULL;
}

说明：销毁后需要清空外部头指针变量，必须二级指针。

总结

需要修改外部头指针：头删、尾删、pos 前插、销毁链表 → 参数 Node**
仅遍历 / 后置插入，不改动表头：查找、pos 后插 → 参数 Node*
二级指针核心逻辑：C 语言值传递，只有传入指针变量的地址，才能修改外部原始指针。

# c语言 # 链表 # 数据结构 # 学习
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

一个 API 入口调用多个大模型：AiiOnly客户端 + CC Switch 打通 Codex AI编程流程

avatar AI编程社区
cover

VSCode Claude Code + MiMo 中转免登录完整配置教程（解决原生登录弹窗 + 模型报错）

avatar AI编程社区
cover

从零开始做一个属于自己的 Skill（保姆级教程）

avatar AI编程社区