2.线性表
线性表是由 n 个数据元素组成的有限序列. 数据元素的个数 n 为表的长度. 当 n 为 0 时称为空表.
逻辑特征:
- 有且仅有一个开始元素, 它没有前趋, 仅有一个直接后继.
- 有且仅有一个终端元素, 它没有后继, 仅有一个直接前趋.
- 其余元素称为内部元素, 它们都有且仅有一个直接前趋和一个直接后继.
- 这种相邻关系又称为线性关系, 可见线性表是一种典型的线性结构.
使用顺序存储的线性表称为顺序表. 它的特点是:
- 只要知道基地址和每个元素占用的单元数, 就可求出任一元素的地址.
- 任意元素都可随机存取 (存取某个位置的元素不必事先存取其前一个元素), 顺序表是一种随机存取结构.
缺点: 需要移动大量元素.
通常用数组来描述顺序表. 
链式存储不仅可以用来表示线性表, 还可以用来表示各种非线性的数据结构.
缺点: 链表的结点不可以随机存取.
假设定义链表元素由两部分组成:
- 数据域: 存储数据元素.
- 指针域: 存储直接后继地址. 终端结点的指针域为空, 即
NULL.
每个链表元素通过指针域指向下一个元素, 设立头指针指向开始结点. 用这种存储方式表示的线性表称为链表.
因为每个结点只包含一个指针域, 因此又称为单链表.
如果链表中一个结点都没有, 则为空链表. 此时头指针为 NULL.
一个单链表可由头指针唯一确定, 因此单链表可以用头指针的名字来命名.
为方便操作, 可以在开始结点之前附加一个头结点. 若链表带头结点时, 就应特别注意头结点和表头结点 (即开始结点) 的区别.
存取第 i 个结点时, 必须从表头结点开始搜索, 所以链表结构是非随机存取存储结构.
循环链表是链式存储的另一种形式, 它的特点是:
- 单链表中最后一个结点的指针域不为空, 而是指向链表的头结点, 使整个链表构成一个环.
- 从表中任一结点开始都可以访问表中的其他结点.
循环链表的形式可以有单循环链表, 还可以有多重链的循环链表.
为使空表和非空表的处理一致, 我们使用带头结点的单循环链表, 如下图: 
它的结点类型与单链表完全相同, 在操作上也与单链表基本一致, 差别仅在于算法中循环结束判断条件不再是 p 或 p->next 是否为空,
而是他们是否等于头指针.
实际应用中, 很多操作会在表尾进行, 此时可使用带尾指针的单链表以简化操作, 如下图: 
向单向链表的结点类型中, 增加一个指向其直接前趋的指针域, 这样形成的链表为双向链表. 双向链表可以从表中快速确定一个结点的直接前趋.
双链表中增设一个头结点, 将尾结点和头结点链接起来就构成了双向循环链表. 如下图: 