逻辑结构

相同数据类型的n个数据元素的有限序列。
n为表长，n=0时是空表。
除第一个元素外，每个元素都有一个直接前驱。
除最后一个元素外，每个元素都有一个直接后继。

线性表特点

元素个数有限
逻辑上有序
元素都是数据元素（即单个元素）
元素数据类型相同（意味着每个元素占有的存储空间相同）

顺序表和链表是存储结构。
线性表是逻辑结构。
两者是不同层面。

物理结构

顺序存储结构

顺序表

顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素。
通常使用数组来描述顺序表。

静态分配：指定长度，超出就会溢出。
动态分配：超出长度后，自动开辟一块新的区域，复制过去。

动态分配不是链式存储，仍是顺序存储。

特点

顺序表的特点就是逻辑顺序与物理顺序相同、任一数据元素都可以随机存取。
存储密度高，结点只存储数据元素。
增删都需要移动大量结点。

操作复杂度

查找
- 按值：O(n)
- 按下标：O(1)
插入：O(n)
删除：O(n)

链式存储结构

单链表

不需要连续的地址空间。
通常使用头指针来标识一个单链表，为了操作上的方便，有时头指针指向的是头结点。

引入头结点后带来的好处

链表第一个元素的操作与其他元素的操作别无二致

空表和非空表的处理也得到了统一

操作复杂度

头插法建立单链表：O(n)
尾插法建立单链表：O(n)

头插法读入数据的顺序与单链表中顺序是反的

查找
- 按值：O(n)
- 按下标：O(n)
插入
- 给定结点后插：O(1)
- 给定节点前插：如果不是尾结点，O(1)
删除
- 按下标删除：O(n)
- 删除给定结点：如果不是尾结点，O(1)
求表长：O(n)

双链表

对于单链表，访问给定结点的前驱和后继分别需要O(n)和O(1)
对于双链表则都是O(1)

操作复杂度

插入
- 给定结点：O(1)
删除
- 给定结点：O(1)

循环链表

循环链表与单链表的差别：尾结点的指针域指向的不是NULL，而是头结点。
若要遍历整个链表，单链表只能从表头开始遍历，而循环链表可以从任意结点开始。
若常在表头和表尾进行操作，则不设头指针，仅设尾指针效率更高。因为如果在表尾操作，则需要遍历整个链表；而通过尾指针可以直接操作表尾，当然也可以直接操作表头。

循环双链表
除了尾结点的后继指针指向头结点；
头结点的前驱指针也要指向尾结点；
当循环链表为空表时，头结点的前驱和后继指针都指向自己。

静态链表

借助数组来实现，结点同样由data域和指针域构成，不过指针域的值不是地址，而是后继结点的数组下表（游标）。
与顺序表一样，静态链表也需要预先分配一块连续的存储空间（数组用）。

next == -1 意为尾结点。

顺序存储 vs 链式存储

存取方式

顺序表可以随机存取；只需一次访问；
链表只能遍历存取；需要n次访问；

与逻辑结构的对应关系

顺序表逻辑上相邻的元素，物理上也相邻；
链表逻辑上相邻的元素，物理上不一定相邻；

插入、删除与查找
- 按值查找
  - 链表与顺序表都是_O(n)（顺序表有序时，可以优化到_O(logn)）
- 按下标查找
  - 链表_O(n)，顺序表_O(1)
- 插入删除
  - 按下标，都是_O(n)_；链表是因为要遍历得到目的结点，顺序表是因为移动结点
  - 给定结点，链表是_O(1)，顺序表是_O(n)
空间分配