数据结构与算法系列--链表精讲

古城微笑少年丶 2022-02-23 04:10 226阅读 0赞

链表也是一种线性表数据结构，与数组不同在于，逻辑上连续，物理空间不连续。链表结构五花八门，重点介绍三种常见的链表结构：单链表，双向链表，循环链表，

## 1，单链表 ##

和数组相比，如何做到将零散的内存块串联起来？链表由结点组成，结点由data和next内存块组成。next存储着下一个结点的地址。  
![在这里插入图片描述][2019040614370328.png]  
插入结点  
![在这里插入图片描述][20190406143810702.png]  
删除结点  
![在这里插入图片描述][20190406143943497.png]  
**复杂度分析**  
插入删除操作O（1）  
对比数组，虽然插入和删除操作高效，但是链表不能随机访问，而是需要根据指针一个节点一个节点地依次遍历，直到找到相应的节点。时间复杂度为O（n）。  
而且，插入删除操作之前往往也要查找节点，那么其复杂度也为O（n）。有什么方法优化单链表吗？

## 2，循环链表 ##

![在这里插入图片描述][20190406144528627.png]  
有了单链表的基础，直接上图就够了。  
与单链表相比，**循环链表的优点**：从链尾到链头比较方便，当处理的数据具有环形结构时，特别适合循环链表。比如：约瑟夫问题。

## 3，双向链表 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]  
有图有真相。和单链表对比，每个节点需要两个额外的空间存储后继节点和前驱节点的地址。所以比单链表占更多的内存空间。但是，也带来了双向链表操作的灵活性。相比单链表，双向链表适合解决那种问题呢？

复杂度分析：  
双向链表找到前驱节点的时间复杂度O（1），也使其在某些情况下插入，删除等操作较单链表简单，高效。虽然单链表插入删除操作复杂度也是O（1），但实际开发中，往往不是这样。

删除操作：  
\-----无外乎分两种情况：

*  删除节点中“值等于某个给定值”的节点
 *  删除给定指针指向的节点

情况1：从头遍历查找待删除节点，复杂度为O（n）。双向链表和单链表都为O（n）。  
情况2：单链表不能直接获取前驱节点，所以，复杂度为O（n）。而双向链表中的节点保存了前驱和后继节点，不需要遍历，复杂度为O（1）。

同理，如果我们在链表的某个指定节点前面插入一个节点，双向链表O（1），而单向链表O（n）

这也是为什么双向链表较为常用。比如Java 中的LinkedHashMap的实现就用到了双向链表。

我理解的，双向链表是对单链表的一个优化，因为单链表的复杂度太不满意了。这就用到了数据结构里的一个重要的设计思想。即用空间换时间。当内存空间充足时，如果提升速度，那就可以选择空间复杂度较高，但时间复杂度较低的数据结构或算法。相反，内存不足，只能牺牲数据换取空间。即时间换空间。  
比如缓存，就是空间换时间的设计思想。学过操作系统或组员的学生可能明白。缓存技术，事先将数据加载到内存中，虽然耗费内存，但查询速度大大提升。

**所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡用哪种数据结构。**

如何基于链表实现LRU缓存淘汰算法？  
如何判断一个字符串是否是回文字符串（字符串是通过单链表存储）？  
如何基于循环链表实现约瑟夫问题？

[2019040614370328.png]: /images/20220223/56df1bc2ac03499e8d18475bda04dc13.png
[20190406143810702.png]: /images/20220223/df8539ba4de744319877cccf000e9f97.png
[20190406143943497.png]: /images/20220223/7be4a56706604be0a37adb67d84cddfd.png
[20190406144528627.png]: /images/20220223/1cd772e282c44c43a033e5c4be61b859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]: /images/20220223/e39d34d9445e4b34b424945ebe7250f9.png