数据结构之链表

“正规军”和“地下党”

如果说数组是纪律严明的 🪖 “正规军”,那么链表就是灵活多变的“地下党”。

地下党借助 📞 单线联络的方式,灵活隐秘地传递着各种重要信息。在计算机科学领域里,有一种数据结构也恰恰具备这样的特征,这种数据结构就是 ⛓️ 链表

单向链表

链表是什么样子的?为什么说它像地下党呢?我们先来看看单向链表的结构。

单向链表结构图

链表是一种在物理上非连续、非顺序的数据结构,由若干节点所组成。

单向链表的每一个节点包含两部分,一部分是存放数据的的变量data,另一部分是指向下一个节点的指针next。

1
2
3
4
private static class Node{
int data;
Node next;
}

链表的第一个节点被称为头节点,最后一个节点被称为尾节点,尾节点的next指针指向空。

与数组按照下标来随机寻找元素不同,对于寻找链表的其中一个节点X,我们只能根据头节点A的next指针来找到该节点的下一个节点B,再根据节点B的next指针来找到该节点的下一个节点C……

这正如地下党的联络方式,一级一级,单线传递。

相对于数组而言,链表因层级分明导致其繁杂低效,所以链表的查询效率是偏低的。

双向链表

在单向链表的机制中,地下党成员都只了解自己的下级信息,并不了解自己的上级信息。

要想让每个节点都能 ⬅️ 回溯到它的前置节点,我们可以使用双向链表。双向链表的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev指针。

双向链表结构图

1
2
3
4
5
private static class Node{
Node prev;
int data;
Node next;
}

链表的存储方式

数组在内存中占用了连续完整的存储空间,所以它的存储方式成为顺序存储。而链表则采用了💉见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的 🧩 碎片空间。

我们看看下面这样图,对比一下数组和链表在内存中分配方式的不同。

巧克力黄色的格子代表空闲的存储单元,灰色的格子代表已占用的存储单元,而淡绿色的格子代表数据在内存中的位置,红色箭头代表链表节点的next指针。

数组内存分配示意图

链表内存分配示意图

链表的基本操作

查找节点

如前文所提到,在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。最坏的时间复杂度是O(n)。

更新节点

如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。

插入节点

尾部插入

尾部插入是最简单的情况,把最后一个节点的的next指针指向新插入的节点即可。

链表尾部插入步骤图

头部插入

头部插入分为两个步骤。

第1步,把新节点的next指针指向原先的头节点。

第2步,把新节点变为链表的头节点。

链表头部插入步骤图

中间插入

中间插入同样分为两个步骤。

第1步,新节点的next指针指向插入位置的节点。

第2步,插入位置前置节点的next指针指向新节点。

链表中间插入步骤图

删除节点

待完成……


参考文献:《小灰的算法之旅》—— 魏梦舒(@程序员小灰)