数据结构 | 深入理解顺序表与链表

深入理解顺序表与链表

在数据结构的世界中，顺序表和链表是两种常见的线性结构，它们在不同的场景下发挥着重要作用。

一、线性表

线性表是由 n 个具有相同特性的数据元素组成的有限序列。常见的线性表有顺序表、链表、栈、队列、字符串等。线性表在逻辑上是线性结构，通常以数组和链式结构的形式在物理上存储。

二、顺序表

1. 概念与结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。顺序表是对数组的封装，实现了常用的增删改查等接口。

2. 分类

• 静态顺序表：使用定长数组存储元素，存在空间给少了不够用、给多了造成空间浪费的缺陷。
• 动态顺序表：按需申请空间，更加灵活。

3. 动态顺序表的实现

以下是动态顺序表的相关代码实现：

#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int size; // 有效数据个数int capacity; // 空间容量
}SL;// 初始化
void SLInit(SL* ps) {// 初始化代码
}// 销毁
void SLDestroy(SL* ps) {// 销毁代码
}// 打印
void SLPrint(SL* ps) {// 打印代码
}// 扩容
void SLCheckCapacity(SL* ps) {// 扩容代码
}// 头部插入
void SLPushFront(SL* ps, SLDataType x) {// 头部插入代码
}// 头部删除
void SLPopFront(SL* ps) {// 头部删除代码
}// 尾部插入
void SLPushBack(SL* ps, SLDataType x) {// 尾部插入代码
}// 尾部删除
void SLPopBack(SL* ps) {// 尾部删除代码
}// 指定位置之前插入
void SLInsert(SL* ps, int pos, SLDataType x) {// 插入代码
}// 指定位置删除
void SLErase(SL* ps, int pos) {// 删除代码
}int SLFind(SL* ps, SLDataType x) {// 查找代码
}

4. 顺序表算法题

• 移除元素：LeetCode 链接。
• 删除有序数组中的重复项：LeetCode 链接。
• 合并两个有序数组：LeetCode 链接。

5. 顺序表问题与思考

• 中间或头部的插入删除操作，时间复杂度为 O(N)。
• 增容需要申请新空间、拷贝数据和释放旧空间，会有不小的消耗。
• 增容一般是呈 2 倍增长，会有一定的空间浪费。

思考如何解决这些问题呢？可以考虑更智能的扩容策略或者使用其他数据结构来优化特定场景下的操作。

三、单链表

1. 概念与结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.1 结点

链表中的每节“车厢”都是独立申请下来的空间，称为“结点”。结点由当前结点要保存的数据和保存下一个结点地址的指针变量组成。

例如，当保存的结点为整型时：

struct SListNode
{int data; // 结点数据struct SListNode* next; // 指针变量用保存下一个结点的地址
};

1.2 链表的性质

• 链式结构在逻辑上是连续的，在物理结构上不一定连续。
• 结点一般是从堆上申请的。
• 从堆上申请来的空间，按照一定策略分配，每次申请的空间可能连续，可能不连续。

1.3 链表的打印

给定链表结构，如何实现结点从头到尾的打印呢？当保存的数据类型为字符型、浮点型或其他自定义类型时，需要相应地修改结点结构体中的数据类型。

2. 实现单链表

以下是单链表的相关代码实现：

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; // 结点数据struct SListNode* next; // 指针保存下一个结点的地址
}SLTNode;void SLTPrint(SLTNode* phead) {// 打印代码
}// 头部插入
void SLTPushFront(SLTNode** pphead, SLTDataType x) {// 头部插入代码
}// 尾部插入
void SLTPushBack(SLTNode** pphead, SLTDataType x) {// 尾部插入代码
}// 头部删除
void SLTPopFront(SLTNode** pphead) {// 头部删除代码
}// 尾部删除
void SLTPopBack(SLTNode** pphead) {// 尾部删除代码
}// 查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {// 查找代码
}// 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {// 插入代码
}// 删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos) {// 删除代码
}// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {// 插入代码
}// 删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos) {// 删除代码
}// 销毁链表
void SListDestroy(SLTNode** pphead) {// 销毁代码
}

3. 链表的分类

链表结构多样，但实际中最常用的是单链表和带头双向循环链表。

• 无头单向非循环链表：结构简单，一般作为其他数据结构的子结构，或在笔试面试中出现。
• 带头双向循环链表：结构复杂，但在单独存储数据时很常用，实现后会发现其有很多优势。

4. 单链表算法题

• 移除链表元素：LeetCode 链接。可使用 VS 调试技能排查代码问题。
• 反转链表：LeetCode 链接。
• 链表的中间结点：LeetCode 链接。
• 合并两个有序链表：LeetCode 链接。
• 链表分割：牛客网链接。
• 链表的回文结构：牛客网链接。
• 相交链表：LeetCode 链接。
• 环形链表 I：使用快慢指针判断链表是否有环。慢指针一次走一步，快指针一次走两步，在带环链表中一定会相遇。对于快指针一次走多步的情况也进行了分析。
• 环形链表 II：结论是让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针最终会在入口点相遇，并进行了证明。
• 随机链表的复制：LeetCode 链接。

四、双向链表

1. 概念与结构

双向链表带有“哨兵位”的头结点，不存储任何有效元素，只是起到“放哨”的作用。

2. 实现双向链表

以下是双向链表的相关代码实现：

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next; // 指针保存下一个结点的地址struct ListNode* prev; // 指针保存前一个结点的地址LTDataType data;
}LTNode;LTNode* LTInit() {// 初始化代码
}void LTDestroy(LTNode* phead) {// 销毁代码
}void LTPrint(LTNode* phead) {// 打印代码
}bool LTEmpty(LTNode* phead) {// 判断是否为空代码
}void LTPushBack(LTNode* phead, LTDataType x) {// 尾部插入代码
}void LTPopBack(LTNode* phead) {// 尾部删除代码
}void LTPushFront(LTNode* phead, LTDataType x) {// 头部插入代码
}void LTPopFront(LTNode* phead) {// 头部删除代码
}void LTInsert(LTNode* pos, LTDataType x) {// 在 pos 位置之后插入数据代码
}void LTErase(LTNode* pos) {// 删除 pos 位置代码
}LTNode *LTFind(LTNode* phead,LTDataType x) {// 查找代码
}

五、顺序表与链表的分析

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持 O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低 O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容和空间浪费	没有容量的概念，按需申请释放，不存在空间浪费
应用场景	元素高效存储+频繁访问	任意位置高效插入和删除

总之，顺序表和链表各有其特点和适用场景。在实际编程中，需要根据具体需求选择合适的数据结构，以提高程序的性能和效率。