一、定义
假设我们有 n 个同类型数据元素的有限序列，记为：
L = (a1, a2, a3, ..., ai, ..., an)
它就构成了一个线性表。前面说过任何一种逻辑结构都可以使用两种存储结构（顺序存储，链式存储）来实现，使用顺序存储时，会在内存中分配连续的空间来存储数据元素，在程序代码中经常使用数组来实现。但问题来了，很多时候我们无法知道到底预先分配多大的空间合适，如果数据量较大时，内存中不存在那么大的连续空间，所以会导致内存分配失败。这个时候，就可以使用链式存储来实现，具体选用哪种方案根据需求决定。
链式存储可以使用任何地址的空间存放数据元素，也就是可以空间不连续，它的实现也很简单，就是在存放每个数据结点，里面包含数据元素和一个指向后一个数据元素的引用（或指针）。
使用顺序存储实现的线性表叫做顺序表，使用链式存储实现的线性表叫做链表。
二、线性表基本操作分析
前面章节说到，分析数据结构要分析各种结构的基本操作，我们首先定义线性表的一组基本操作，然后编写代码来实现。首先分析线性表的插入、删除、查找、遍历等基本操作，再使用不同的存储结构来实现。
1. 插入
我们已经创建了两种存储结构的线性表，数据元素为 (a1, a2, a3, a4, a5)，现在需要在 a2 的的后面插入一个新的数据元素 a6，在使用顺序存储实现时，我们需要将 a2 后面的数据 a3, a4, a5 都要往后移动才能插入。在使用链式存储时，而只需要定位到 a2，然后把 a2.next 赋给新结点 a6.next，再把新结点 a6 赋给 a2.next，通过引用的交换就可以将新数据插入到链表中，由此可看出链表比顺序表的插入效率要高。
2. 删除
如果我们要删除线性表中的一个数据元素，和插入有点类似，比如需要在给定线性表 (a1, a2, a3, a4, a5) 中删除第三个元素 a3，在顺序结构中，需要把 a3 后面的数据 a4, a5 都要往前移动，再把最后一个数据元素清空。在链式结构中，只需要定位到 a3 前一个元素 a2，然后把 a2.next.next 赋值给 a2.next 就可以删掉链表中的 a3，所以，链表的删除操作不需要移动后面的元素，效率比顺序表要高。
3. 查找
如果我们需要在线性表中通过下标查找数据元素，在顺序存储中，因为数据是有序存放在一个内存段中的，所以直接可以使用下标来获取，而在链式存储中，数据是无序的，所以要从头结点开始遍历来找到对应下标的数据元素，由此可知，链表的查找效率低于顺序表。
4. 遍历
当我们要对一个线性表进行遍历时，虽然不管是使用顺序存储还是链式存储，都要对所有元素进行读取，效率看上去不相上下，但不要忘了，顺序表是存在连续空间上的，所以在遍历的时候只需要进行地址偏移就可以读取到所有元素，而链表每读取元素的后一个元素，都要进行一次寻址操作，所以效率也是低于顺序表的。
下面新建一个线性表常规操作的接口，然后我们用顺序结构（数组）和链式结构来实现这个接口，来实现对线性表的操作，读者可以分别对两种存储结构实现的接口的时间复杂度进行分析。
public interface LinearTable<T> { /** * 初始化线性表数据 */ LinearTable<T> init(T... t); /** * 判断线性表是否为空 */ boolean empty(); /** * 清空线性表 */ boolean clear(); /** * 返回线性表的大小 */ int size(); /** * 插入数据元素 */ boolean insert(int pos, T t); /** * 删除数据元素 */ boolean delete(int pos); /** * 通过位置查找数据元素 */ T findElement(int pos); /** * 通过数据元素查找位置 */ int findPosition(T t); /** * 打印线性表所有数据 */ void print(); }
三、线性表基本操作实现
顺序结构使用数组来存储数据，链式结构使用结点来存储数据。
1. 顺序存储实现
public class ArrayLinearTable<T> implements LinearTable<T> { private Object[] elementData; public ArrayLinearTable(int size) { elementData = new Object[size]; } @Override public LinearTable<T> init(T... t) { elementData = t; return this; } @Override public boolean empty() { return elementData.length == 0; } @Override public boolean clear() { for (int i = 0; i < elementData.length; i++) { elementData[i] = null; } return true; } @Override public int size() { return elementData.length; } @Override public boolean insert(int pos, T t) { if (pos > elementData.length - 1) { throw new ArrayIndexOutOfBoundsException(); } for (int i = pos; i < elementData.length - 1; i++) { elementData[i + 1] = elementData[i]; } elementData[pos] = t; return true; } @Override public boolean delete(int pos) { if (pos > elementData.length - 1) { throw new ArrayIndexOutOfBoundsException(); } for (int i = pos; i < elementData.length - 1; i++) { elementData[i] = elementData[i + 1]; } elementData[elementData.length - 1] = null; return true; } @SuppressWarnings("unchecked") @Override public T findElement(int pos) { return (T) elementData[pos]; } @Override public int findPosition(T t) { if (t == null) { return -1; } for (int i = 0; i < elementData.length; i++) { if (t.equals(elementData[i])) { return i; } } return -1; } @Override public void print() { System.out.println(Arrays.toString(elementData)); } }
2. 链式存储实现
public class LinkedLinearTable<T> implements LinearTable<T> { private Node head; private int size = 0; private class Node { private T t; private Node next; public Node() { } public Node(T t, Node next) { this.t = t; this.next = next; } } @Override public LinearTable<T> init(T... t) { if (t == null || t.length == 0) { return this; } head = new Node(t[size++], null); Node pre = head; for (int i = 1; i < t.length; i++) { pre.next = new Node(t[i], null); pre = pre.next; size++; } return this; } @Override public boolean empty() { return head == null; } @Override public boolean clear() { head = null; return true; } @Override public int size() { return size; } @Override public boolean insert(int pos, T t) { if (pos > size) { throw new OutOfMemoryError(); } Node n = new Node(t, null); if (pos == 0) { n.next = head; head = n; } else { Node pre = head; for (int i = 0; i < pos - 1; i++) { pre = pre.next; } n.next = pre.next; pre.next = n; } size++; return true; } @Override public boolean delete(int pos) { if (pos > size - 1) { throw new OutOfMemoryError(); } if (pos == 0) { head = head.next; } else { Node pre = head; for (int i = 0; i < pos - 1; i++) { pre = pre.next; } pre.next = pre.next.next; } size--; return true; } @Override public T findElement(int pos) { Node n = head; for (int i = 0; i < pos; i++) { n = n.next; } return n.t; } @Override public int findPosition(T t) { int i = 0; Node n = head; while (n != null && !t.equals(n.t)) { i++; n = n.next; } return i; } @Override public void print() { Node n = head; while (n != null) { System.out.print(n.t + ","); n = n.next; } System.out.println(); } }
四、链式存储扩展
前面讲到的链式结构实现的线性表都是单向链表，我们还可以增加结点的引用来创建更多的链表结构，比如双向链表、单向循环链表和双向循环链表等，只需要掌握一种最简单最基础的单向链表，就可以举一反三搞懂其他各种特殊链表结构。
