什么是链表？链表是一种线性表，但并不会按线性的顺序存储数据，而是在每一个节点里存储到下一个节点的指针 (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;删除指定节点 dE 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)。PS: 清山绿水始于尘，博学多识贵于勤。 我有酒，你有故事吗？ 公众号：「清尘闲聊」。 欢迎一起谈天说地，聊代码。