线性表

线性表就是存储相同数据元素的有限序列。这个关系是逻辑上的关系，而非物理上的关系。例如下面几个数据结构，都是属于线性表。在逻辑上，它们是紧密连接的，一个元素挨着一个元素，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。只要符合这种关系，那它就是线性表

数组

数组是线性表的顺序存储，它的主要特点是在逻辑上相邻的元素，在实际的物理内存中也是相邻的。 所以利用这一特性我们可以很方便的进行数据的快速存取。在创建数组时，系统会记录下数组首地址的指针和数组的数据类型，这样当我们利用数组下标访问数组元素时，系统就会用首地址的下标加上数据类型的大小*下标。

a[i]_address = base_address + i * data_type_size复制代码

这样的特性造成了数组的高效访低效的插入和删除。数组中如果想要插入一个元素，你就需要把想要插入位置后的元素依次往后移一位，这对性能是极大地损失。

链表

链表是线性表的链式存储，它的主要特点是在逻辑上相邻的元素，在实际的物理内存中可以是相邻或者不相邻的。 由于在物理位置上的不确定性，所以链表在查找时会耗费大量时间。一个标准的链表元素必须要有一个存放数据的数据域，和一个指向下个链表元素的指针域，所以利用这一特性我们可以很方便的进行数据的快速删除或增加。当你需要增加一个新的链表元素时，你只需要把当前链表元素中的指针域赋值给将要添加进来的链表元素的指针域，然后再将当前链表元素的指针域指向添加进来的链表元素。