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