顺序表和链表

一.线性表

常见的线性表：顺序表、链表、栈、队列、字符串
线性表在逻辑上是线性结构，也就说是连续的一条直线，但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

二.顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改
静态顺序表：使用定长数组存储元素
动态顺序表：使用动态开辟的数组存储
一些相关oj题目：

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

三.链表

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

链表的分类

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

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

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

单链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.4 链表面试题
6. 删除链表中等于给定值 val 的所有结点题目链接
7. 反转一个单链表题目链接
8. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点题目链接
9. 输入一个链表，输出该链表中倒数第k个结点题目链接
10. 将两个有序链表合并为一个新的有序链表并返回，新链表是通过拼接给定的两个链表的所有结点组成的题目链接
11. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前题目链接
12. 链表的回文结构题目链接
13. 输入两个链表，找出它们的第一个公共结点题目链接
14. 给定一个链表，判断链表中是否有环题目链接

双链表的实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

四.顺序表和链表的区别和联系