数据结构之链表
数据结构之链表
zyan“正规军”和“地下党”
如果说数组是纪律严明的 🪖 “正规军”,那么链表就是灵活多变的“地下党”。
地下党借助 📞 单线联络的方式,灵活隐秘地传递着各种重要信息。在计算机科学领域里,有一种数据结构也恰恰具备这样的特征,这种数据结构就是 ⛓️ 链表。
单向链表
链表是什么样子的?为什么说它像地下党呢?我们先来看看单向链表的结构。
链表是一种在物理上非连续、非顺序的数据结构,由若干节点所组成。
单向链表的每一个节点包含两部分,一部分是存放数据的的变量data,另一部分是指向下一个节点的指针next。
1 | private static class Node{ |
链表的第一个节点被称为头节点,最后一个节点被称为尾节点,尾节点的next指针指向空。
与数组按照下标来随机寻找元素不同,对于寻找链表的其中一个节点X,我们只能根据头节点A的next指针来找到该节点的下一个节点B,再根据节点B的next指针来找到该节点的下一个节点C……
这正如地下党的联络方式,一级一级,单线传递。
相对于数组而言,链表因层级分明导致其繁杂低效,所以链表的查询效率是偏低的。
双向链表
在单向链表的机制中,地下党成员都只了解自己的下级信息,并不了解自己的上级信息。
要想让每个节点都能 ⬅️ 回溯到它的前置节点,我们可以使用双向链表。双向链表的每一个节点除了拥有data和next指针,还拥有指向前置节点的prev指针。
1 | private static class Node{ |
链表的存储方式
数组在内存中占用了连续完整的存储空间,所以它的存储方式成为顺序存储。而链表则采用了💉见缝插针的方式,链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。这样可以灵活有效地利用零散的 🧩 碎片空间。
我们看看下面这样图,对比一下数组和链表在内存中分配方式的不同。
巧克力黄色的格子代表空闲的存储单元,灰色的格子代表已占用的存储单元,而淡绿色的格子代表数据在内存中的位置,红色箭头代表链表节点的next指针。
链表的基本操作
查找节点
如前文所提到,在查找元素时,链表不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。最坏的时间复杂度是O(n)。
更新节点
如果不考虑查找节点的过程,链表的更新过程会像数组那样简单,直接把旧数据替换成新数据即可。
插入节点
尾部插入
尾部插入是最简单的情况,把最后一个节点的的next指针指向新插入的节点即可。
头部插入
头部插入分为两个步骤。
第1步,把新节点的next指针指向原先的头节点。
第2步,把新节点变为链表的头节点。
中间插入
中间插入同样分为两个步骤。
第1步,新节点的next指针指向插入位置的节点。
第2步,插入位置前置节点的next指针指向新节点。
删除节点
待完成……
参考文献:《小灰的算法之旅》—— 魏梦舒(@程序员小灰)