一、定义
假设有 个同类型数据元素的有限序列，记为：
它构成一个线性表，任何一种逻辑结构都可以使用顺序存储和链式存储来实现，使用顺序存储时，会在内存中分配连续的空间来存储数据元素，在程序中经常使用数组来实现。
但很多时候无法知道预先分配多大的空间合适，如果数据量较大时，内存中不存在那么大的连续空间，所以会导致内存分配失败，此时就可以使用链式存储来实现。
链式存储可以使用任何地址的空间存放数据元素，可以空间不连续，它存放的数据结点，里面包含数据元素和指向另一个数据元素的引用（或指针）。
二、线性表基本操作
数据结构包含数据的基本操作，使用不同的存储结构来实现线性表的插入、删除、查找、遍历等基本操作。
1. 插入
初始化一组数据 ，然后在 后面插入数据 。
顺序存储中，定位到 ，需要将 往后移动才能插入。
链式存储中，定位到 ，然后把 的指针指向 ，再把 的指针指向 就完成了新节点的插入。
由此可得链表比顺序表插入的效率高。
顺序存储需要预先分配内存空间，在插入时初始化的空间不够会抛异常。
2. 删除
初始化一组数据 ，然后删除数据 。
顺序存储中，定位到 删除并释放内存，然后将 往前移动。
链式存储中，定位到 ，然后把 的指针指向 ，释放内存即可删除。
由此可得链表比顺序表删除的效率高。
3. 查找
初始化一组数据 ，然后查找数据 。
顺序存储中，数据在内存中是连续的，如果已知 的下标，可以直接获取到该数据元素。
在下标未知的情况下，也可以通过遍历来查找。
链式存储中，数据在内存中是无序的，不能通过下标查找，只能通过遍历来查找数据。
而链式存储在遍历的时候，会增加寻址的操作。
由此可得顺序表比链表查找的效率高。
4. 遍历
初始化一组数据 ，然后遍历所有数据 。
顺序存储中，遍历连续内存空间上的数据元素。
链式存储中，通过地址引用来找到下一个数据元素，来遍历所有数据。
链式存储增加了寻址的操作，所以遍历的效率低于顺序存储。
三、链式存储扩展
前面讲的链式结构实现的线性表都是单向链表，可以增加结点的引用来创建更多的链表结构，比如：双向链表、单向循环链表和双向循环链表等。
四、代码示例
具体的代码实现如下：
