0.定义

数据结构中的逻辑结构分为线性结构和非线性结构。简单地说，线性结构是n个数据元素的有序（次序）集合，它有下列几个特征：

1．集合中必存在唯一的一个"第一个元素"；

2．集合中必存在唯一的一个"最后的元素"；

3．除最后元素之外，其它数据元素均有唯一的"后继"；

4．除第一元素之外，其它数据元素均有唯一的"前驱"。

一般地，一个线性表可以表示成一个线性序列：k1，k2，…，kn，其中k1是开始结点，kn是终端结点。

1. 线性表的顺序表示和实现

线性表的顺序表示指的是用物理上的一段连续的地址来存储数据元素，如下图所示。如果第一个元素的在内存上的地址为a1，每个元素占用的空间是l，那么第n个元素的地址就是a1+(n-1) x l。

只要确定了第一个元素的地址，那么我们可以对线性表中的任一元素随机存取。由于编程语言中的数组也有随机存取的特点，所以可以用数组来描述线性表的顺序存储结构。

2. 线性表的链式表示

线性表的顺序存储结构是逻辑位置和物理位置都相邻，而链式存储结构是逻辑位置相邻，但物理位置不一定相邻，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了增加和删除元素的效率。

链式存储结构除了单链表之外，还有循环链表和双向链表。