一、线性表的基本概念

线性表是具有相同数据类型的n(n>=0)个数据元素的有序序列，其中n为表长，当n=0的时候线性表是一个空表。

1.线性表是最基本且最常用的一种线性结构

2.线性结构的基本特点：除第一个元素无直接前驱，最后一个元素无直接后继外，其他每个元素都有一个前驱和后继。

二、线性表的存储结构/物理结构

线性表的存储结构/物理结构分为：顺序表（顺序存储）、链表（链式存储）
在这里插入图片描述

三、线性表的顺序表示/顺序存储

3.1顺序表的定义

线性表的顺序存储又称为顺序表
线性表的顺序表示：指的是用一组地址连续的存储单元依次存储线性表的数据元素

注意：
1.线性表中元素的位序从1开始，而数组元素的下标是从0开始的

3.2顺序表特点

顺序表最主要的特点就是随机访问，即通过首地址和元素序号可在时间O（1）内找到制定的元素
顺序表的存储密度高，每个节点置存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除需要移动大量的元素
表中元素的逻辑顺序与物理顺序相同

四、线性表的链式存储

- 单链表：

- 对于每个链表结点除了存放元素自身的信息之外，还需要存放一个指向后继的指针；(一个数据域data,一个指针域next)
	- 缺点：1.单链表结点只有一个指向后继的结点，使得单链表只能从头结点依次顺序地向后遍历
	- 缺点：2.要访问某个**节点**的前驱结点时，只能从头开始遍历O(n),访问后继结点时O(1)

- 双链表：

- 为了克服单链表的缺点，双链表结点中有两个指针域(prior,next)
- 分别指向其前驱结点，后继节点

- 循环链表：分为循环单、双链表

- 与单链表不同的是，表中最后一个结点不是null
- 而是指向头节点从而整个链表形成一个环
- 分别指向其前驱结点，后继节点
- 从表中任一一个结点出发都能找到线性表中的其他结点

- 静态链表：

- 与线性表一样，都需要预先分配一块连续的内存
- 结点有数据域data，指针域next(此处指针的结点是相对地址，是数组下标，又称为游标)

五、链式存储表示

5.1 单链表的定义

1.单链表由表头唯一确定，因此单链表可以用头指针的名字来命名
2.若头指针名字为L，则把链表成为表L
3.指针变量p：表示结点地址
结点变量*p：表示一个结点

5.2链表的存储表示

在这里插入图片描述

六、顺序表与链表的比较

存取（读写）方式
顺序表可以顺序存储，也可以随机
链表只能从表头顺序存取元素
逻辑结构和物理结构
顺序存储：逻辑上相邻的元素，物理存储位置也相邻
链式存储：逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的
查找、插入和删除操作
按值查找：顺序表无序，二者都是O(n)
若有序，可以采用折半查找，时间复杂度为O（log2n)
按序号查找：顺序表支持随机存储O(1),链表平均时间复杂度O(n)
空间分配
顺序存储在静态存储分配情况下，一旦分配好就不能扩充，因此需要预先分配大量空间
链式存储只在需要时神情分配即可，内存有空间就可以分配，更高效、操作灵活