线性表
线性表
线性表的顺序存储结构
在数据元素的非空有限集中，1).存在唯一的一个被称为“第一个”的数据元素，2).存在唯一的一个被称作“最后一个”的数据元素，3).除第一个之外，集合中的每个数据元素均只有一个前驱；4).除最后一个之外，集合中每个数据元素均只有一个后继。
线性表的顺序存储结构逻辑关系上相邻的两个元素的物理位置上也相邻。
使用线性表时，我们可以用不同的方式进行数据存储，最常用的方式是用一组连续的地址依次存储线性表的数据元素。
假设线性表的每个元素需要占用L个存储单元，并以第一个单元的存储地址作为数据元素的存储位置，则线性表中的第i+1个数据元素的存储位置为LOC(ai+1)和第i个数据元素的存储位置LOC（ai）之间满足下列关系：
一般来说，线性表的第i个元素ai的存储位置为：
只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
顺序存储结构的缺点：容易造成存储结构的三个弱点：
- 操作增删时，需要移动大量的数据元素；
- 不能充分利用空间，因为在给长度变化较大的线性表预先分配空间时，必然会按最大的空间进行分配；
- 标的容量难以扩充。
线性表的链式存储结构
特点:可以在任意的存储单元存放线性表的数据元素(元素存储可以是连续的也可以是非连续的)，因此，为了表示数据元素ai的后继元素ai+1的逻辑关系，对元素ai来说，除了存储本身元素外还要再存储一个直接后继元素的位置信息，这两部分组成ai的出处映像，称为节点
两个域： 存储节点元素的称为数据域，存储后续元素位置的称为指针域；指针域中存储的信息称为指针或链，n个节点连接成一个链表，即为线性表的链式存储机构。又由于此链表中只包含一个指针域，故又称线性链表或单链表。
循环链表
特点：循环链表是另一种形式的链式存储结构，特点是，表中最后一个节点的指针域指向头结点，形成了一个环，因此，从表中任一一个节点出发均可找到表中其他的节点。
双向链表
特点：双向链表的节点中有两个指针域，其中一个指向直接后继，另一个指向直接前趋。
单向链表的缺点：单向链表的指针域指向的都是直接后驱，若想找到当前节点的直接前趋需要从头结点重新查找