【本节目标】

• 1. 线性表
• 2. 顺序表
• 3. 链表
• 4. 顺序表和链表的区别和联系

目录

• 【本节目标】
• 1.线性表
• 2.顺序表
  • 2.1 概念及结构
  • 2.2 接口实现
  • 2.3 数组相关面试题
  • 2.4 顺序表的问题及思考
• 3.链表
  • 3.1 链表的概念及结构
  • 3.2 链表的分类
  • 3.3 链表的实现
  • 3.4 链表面试题
  • 3.5 双向链表的实现
• 4.顺序表和链表的区别

1.线性表

线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态地分配空间大小，所以下面我们实现动态顺序表。

typedefintSLDataType;// 顺序表的动态存储typedefstructSeqList{SLDataType*array;// 指向动态开辟的数组size_tsize;// 有效数据个数size_tcapicity;// 容量空间的大小}SeqList;// 基本增删查改接口// 顺序表初始化voidSeqListInit(SeqList*psl);// 检查空间，如果满了，进行增容voidCheckCapacity(SeqList*psl);// 顺序表尾插voidSeqListPushBack(SeqList*psl,SLDataType x);// 顺序表尾删voidSeqListPopBack(SeqList*psl);// 顺序表头插voidSeqListPushFront(SeqList*psl,SLDataType x);// 顺序表头删voidSeqListPopFront(SeqList*psl);// 顺序表查找intSeqListFind(SeqList*psl,SLDataType x);// 顺序表在 pos 位置插入 xvoidSeqListInsert(SeqList*psl,size_tpos,SLDataType x);// 顺序表删除 pos 位置的值voidSeqListErase(SeqList*psl,size_tpos);// 顺序表销毁voidSeqListDestory(SeqList*psl);// 顺序表打印voidSeqListPrint(SeqList*psl);

2.3 数组相关面试题

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。OJ 链接
2. 删除排序数组中的重复项。OJ 链接
3. 合并两个有序数组。OJ 链接

2.4 顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)。
2. 增容需要申请新空间、拷贝数据、释放旧空间，会有不小的消耗。
3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到 200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。

**思考：**如何解决以上问题呢？下面给出了链表的结构来看看。

3.链表

3.1 链表的概念及结构

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

现实中：

数据结构中

3.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

1. 单向或者双向
   
2. 带头或者不带头
   
3. 循环或者非循环
   

虽然有这么多的链表结构，但是我们实际中最常用还是两种结构：

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

3.3 链表的实现

// 1、无头+单向+非循环链表增删查改实现typedefintSLTDateType;typedefstructSListNode{SLTDateType data;structSListNode*next;}SListNode;// 动态申请一个结点SListNode*BuySListNode(SLTDateType x);// 单链表打印voidSListPrint(SListNode*plist);// 单链表尾插voidSListPushBack(SListNode**pplist,SLTDateType x);// 单链表的头插voidSListPushFront(SListNode**pplist,SLTDateType x);// 单链表的尾删voidSListPopBack(SListNode**pplist);// 单链表头删voidSListPopFront(SListNode**pplist);// 单链表查找SListNode*SListFind(SListNode*plist,SLTDateType x);// 单链表在 pos 位置之后插入 x// 分析思考为什么不在 pos 位置之前插入？voidSListInsertAfter(SListNode*pos,SLTDateType x);// 单链表删除 pos 位置之后的值// 分析思考为什么不删除 pos 位置？voidSListEraseAfter(SListNode*pos);

3.4 链表面试题

1. 删除链表中等于给定值val的所有结点。203. 移除链表元素
2. 反转一个单链表。206. 反转链表
3. 给定一个带有头结点head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。876. 链表的中间结点
4. 输入一个链表，输出该链表中倒数第k个结点。面试题 02.02. 返回倒数第 k 个节点
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。21. 合并两个有序链表
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。CM11 链表分割
7. 链表的回文结构。OR36 链表的回文结构
8. 输入两个链表，找出它们的第一个公共结点。160. 相交链表

9. 给定一个链表，判断链表中是否有环。141. 环形链表

【思路】

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行。如果链表带环，则一定会在环中相遇，否则快指针就率先走到链表的末尾。比如：陪女朋友到操场跑步减肥。

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？

  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况。因此，在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

• 快指针一次走 3 步，走 4 步，……n 步行吗？

此时按照上述方法来绕环移动，每次快指针走 3 步，慢指针走 1 步，是永远不会相遇的，快指针刚好将慢指针套圈了，因此不行。

只有快指针走 2 步，慢指针走 1 步才可以，因为环的最小长度是 1，即使套圈了两个也在相同的位置。

10. 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回NULL。OJ 链接

【结论】

让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

【证明】

11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点或空结点。要求返回这个链表的深度拷贝。138. 随机链表的复制

3.5 双向链表的实现

// 2、带头+双向+循环链表增删查改实现typedefintLTDataType;typedefstructListNode{LTDataType _data;structListNode*next;structListNode*prev;}ListNode;// 创建返回链表的头结点ListNode*ListCreate();// 双向链表销毁voidListDestory(ListNode*plist);// 双向链表打印voidListPrint(ListNode*plist);// 双向链表尾插voidListPushBack(ListNode*plist,LTDataType x);// 双向链表尾删voidListPopBack(ListNode*plist);// 双向链表头插voidListPushFront(ListNode*plist,LTDataType x);// 双向链表头删voidListPopFront(ListNode*plist);// 双向链表查找ListNode*ListFind(ListNode*plist,LTDataType x);// 双向链表在 pos 的前面进行插入voidListInsert(ListNode*pos,LTDataType x);// 双向链表删除 pos 位置的结点voidListErase(ListNode*pos);

4.顺序表和链表的区别

备注：缓存利用率参考存储体系结构以及局部性原理。

与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell