一、顺序表的问题及思考
在顺序表的实现中,可以发现以下问题:
- 中间/头部插入删除:时间复杂度为 O(N),效率低下。
- 增容消耗:需要申请新空间,拷贝数据,释放旧空间(realloc),导致运行速度下降。
- 空间浪费:增容一般是呈 2 倍的增长,势必会有一定的空间浪费。
为了应对以上问题,引入了链表的概念。
二、链表的概念及结构
1. 概念
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表是线性表的一种。
类比:火车由一节节车厢连接而成,物理上不连续,但逻辑上可通过前一节找到后一节。链表同理。
2. 结构
链表由一个个节点组成,每个节点包含数据 data 和指向下一个节点的指针。

定义如下:

底层为结构体。S 代表 Single(单个),node 是节点的意思。typedef 用于重定义链表的名字。
三、链表的实现
1. 头文件声明及定义
创建 .h 文件完成函数声明,.c 文件完成实现及测试。链表支持'增删查改'功能。

参数说明:pos 表示指向指定位置的指针,phead 表示链表头节点的指针,pphead 表示头节点指针的地址(二级指针)。
2. 函数实现及测试
打印函数
传链表头节点的地址(传址调用)。创建 pcur 指针遍历链表,当 pcur 为空时结束,打印 NULL。

节点申请函数
封装函数申请新节点,返回 SLTNode*。使用 malloc 开辟空间,若失败则 perror 并 exit。成功则置入值 x,next 置空,返回 newnode。













