数据结构之「链表」
什么是链表？
链表是一种线性表，但并不会按线性的顺序存储数据，而是在每一个节点里存储到下一个节点的指针 (Pointer)。因此它不需要分配连续的存储空间，也不需要预先固定元素的大小，它可以动态的添加和删除元素，而且时间复杂度是 O(1)。只不过查找某个元素时，时间复杂度是 O(n)。
链表有多种不同的类型：单向链表，双向链表和循环链表。
单向链表
单向链表是最简单的一种，它包含两个域，一个信息域和一个指针域。这个指针域指向列表中的下一个节点，而最后一个节点则指向一个空值。
单向链表
双向链表
双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点。
双向链表
循环链表
循环链表是把链表的首节点和末节点连接在一起，形成一个环。这种方式在单向和双向链表中皆可实现。
循环链表
链表有什么作用？
根据链表的特性，动态的把元素加入到链表中，不需要预先指定链表长度，理论上链表可以无限长，直到内存耗尽。链表会存储下一个元素的地址，因此插入和删除会很方便，但查询指定元素时，最坏的情况是遍历整个链表。
链表该怎么使用？
这里我用 Java 语言来简单实现链表，可参考 JDK 的 LinkedList。
构建链表结构
//创建一个私有的静态的Node泛型对象
public class LinkedList<E> {
Node<E> first;//第一个节点
Node<E> last;//最后一个节点
private static class Node<E> {
E item;//存储元素
Node<E> next;//下一个元素
Node<E> prev;//上一个元素
//通过构造器设置值
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
在链表后插入元素，前面插入也类似
//中间变量存储链表的最后一个节点
Node<E> l = last;
//构建新节点，头节点指向链表的最后节点
Node<E> newNode = new Node<>(l, 5, null);
//把新节点当作最后一个节点
last = newNode;
//if 最后节点为空，说明是一个新链表
if (l == null)
first = newNode;
//否则把链表最后一个节点的 next 节点指向新节点
else
l.next = newNode;
删除指定节点 d
E element = d.item;
Node<E> next = d.next;
Node<E> prev = d.prev;
//if 当前节点的上一个节点为空，
//说明删除的是第一个节点，
//把当前节点的下一个节点置为第一个节点。
if (prev == null) {
first = next;
//否则把上一个节点的下一个节点指向当前节点的下一个节点，
//相当于跳过了当前节点，并把当前节点的上一个节点置空。
} else {
prev.next = next;
d.prev = null;
}
//if 当前节点的下一个节点为空，说明是最后一个节点。
//把最后一个节点置为上一个节点。
if (next == null) {
last = prev;
//否则把当前的上一节点指向当前的下一个节点，
//相当于跳过当前节点，在把当前节点的下一个节点置空。
} else {
next.prev = prev;
d.next = null;
}
//置空当前节点元素，帮助 GC 回收
d.item = null;
遍历链表
Node<E> d = first;
while (d != null && d.next != null) {
System.out.println(d.item);
d = d.next;
}
总结
数组需要初始化确定好长度，并且不能修改数组的长度。在有的场景下，是不知道有多少元素的，因此我们是不能准确的分配数组的长度。但也提供了数组扩容的方案，就是在现有的数组大小上，在按一定算法来创建一个新的数组，并把数组的数据拷贝进扩容后的数组里去，但数组的扩容是很影响性能的。因此需要一种新的数据结构来存储不能确定有多少元素的数据，这就是链表的应用场景。
但它也有缺点，每个节点多需要多的空间来存储下一个节点的地址，查询时最坏情况是遍历整个数组。
它的优点是不需要预分配固定大小，不限制元素个数，理论上可以直到内存耗尽，插入和删除时间复杂度是 O(1)。
