线性表

线性表是具有相同数据类型的n个数据元素的有限序列。

除了第一个元素外，每个元素有且仅有一个直接前驱；除了最后一个元素之外，每个元素有且只有一个直接后继元素

顺序存储

顺序表

1. 可以进行随机访问
2. 存储密度高
3. 删除和插入需要移动大量的元素
4. 顺序存储分配需要一段连续的存储空间

线性表的顺序存储结构是一种随机存取的存储结构

一维数组可以不连续，所以和顺序表在逻辑结构上有所不同

存取方式是指读/写方式

链式存储

单链表

头节点和头指针的关系：不管带不带头节点，头指针都始终指向链表的第一个结点，而头节点是带头节点的链表中的第一个结点。

双链表

struct node{
	struct node* prev;
	int data;
	struct node* next;
};

循环链表

这里判断是否为空不是看指针为NULL，而是看指针是否指向头节点本身。

1. 循环单链表：最后一个结点的指针指向头节点
2. 循环双链表

静态链表（数组实现）

预先分配一段连续的内存空间。

顺序表和链表对比

1. 存取方式：顺序表可以顺序存取也可以随机存取，链表只能从表头开始依次顺序存取。
2. 逻辑结构和物理结构
3. 查找、插入和删除操作：时间复杂度
4. 空间分配：存储密度，预先分配