数据结构之链表
数据结构之链表
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指针指向新节点。
删除节点
待完成……
参考文献：《小灰的算法之旅》—— 魏梦舒（@程序员小灰）
