线性表是一个序列，
存储方法：顺序存储和链式存储。
基本操作：插入、删除和查找
（一）线性表定义
线性表是n个元素的有限序列（n>0）
（二）线性表存储结构
存储结构 | 说明 | 备注 | 优缺点 | |
1 | 顺序存储 | 用一组地址连续的存储单元依次存储数据元素，使逻辑相邻的两个元素在物理位置上也相邻 | 无需占用额外空间来存储元素间的逻辑关系 | 优点：可随机存取元素，按序号查找速度很快 缺点：插入和删除操作需要移动元素 |
2 | 链式存储 | 基本结点结构：
数据域（存储数据元素值） 指针域（存储指针或链）：存储当前元素直接前驱或后继元素位置信息 | ||
用结点来存储数据元素，元素结点地址可以连续或不连续 | 必须存储元素之间的逻辑关系 结点空间按需申请，无须事先分配 在链式存储结构下进行插入和删除，其实质都是对相关指针的修改 | 优点：插入和删除操作不需要移动元素。 缺点：只能顺序地访问元素，不能对元素进行随机存取 | ||
（1）随机访问
数组在内存中连续存储，可以通过简单计算得到任意元素的内存地址，可以直接访问数组中的任何元素，而不需要遍历整个数组。这种直接访问的能力使得数组下标访问具有 O(1) 的时间复杂度。
element_address = base_address + (index * element_size)
注：数组首地址（base_address）；元素大小（element_size），数组元素下标index
（2）单链表插入和删除结点
typedef struct node {
int data;/*数据域*/
struct node *next;/*指针域*/
}NODE,*LinkList;
插入结点：
s→next=p→next;
p→next = s;
删除结点：
q=p→next;
p→next=p→next→next;
free(q);
（二）线性表分类
根据结点中指针信息的实现方式
分类 | 说明 | |
1 | 单向链表 | n个结点通过指针连成一个链表，结点中只有一个指针域 |
2 | 双向链表 | 每个结点包含两个指针，分别指明当前元素的直接前驱和直接后继信息，可在两个方向上遍历元素 |
3 | 循环链表 | 表尾结点指针指向表中第一个结点，可从表中任意结点开始遍历整个链表 |
4 | 静态链表 | 借助数组来描述线性表的链式存储结构 |
