重学数据结构之链表篇

本文是重学数据结构系列文章的第二篇，本文和大家一起探讨链表的相关知识。
重学数据结构之数组篇

文章目录

• • • 链表是怎么样的数据结构
    • 链表的特点
    • 常见的链表结构
    • • 单链表
      • 双向链表
      • 循环链表
      • 链表or数组
    • 链表的应用
    • 正确写出链表的6个技巧

链表是怎么样的数据结构

链表，不需要连续的内存空间，通过“指针(引用)”将一组零散的内存块串联起来的数据结构。
内存块在链表中也叫“结点”，每个结点除了存储数据，还需要记录链上的下一个或者上一个结点的地址。

链表的特点

1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。
2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常见的链表结构

单链表

1.只有一个方向，每个结点只存储下一个结点的地址,记录下一个结点的指针成为后继指针(next)
2.有两个特殊结点，头结点和尾结点。头结点用来记录链表的基地址；尾结点指向一个空地址NULL，表示链表的最后一个结点
3.链表的插入和删除操作，因为不考虑内存空间的连续性，只需要关注相邻结点的指针变化，所以时间复杂度为O(1)
4.链表的随机访问操作，因为内存空间的不连续性，需要指针一个结点一个结点的依次访问，直到找到对应的结点，所以时间复杂度为O(n)

双向链表

1.有两个方向，每个结点既有指向后面结点的后继指针next，也有指向前面结点的前驱指针prev, 因为需要同时存储前后两个指针，因此双向链表占用更多的内存存储空间
2.首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3.对于删除、插入操作可以实现比单链表更加高效的O(1)。对于删除操作，一般就是如下两种情况：

• a.删除结点中“值等于某个给定值”的结点；
• b.删除给定指针指向的结点。

对于第一种情况，无论单链表还是双向链表，都需要从头结点开始每个结点依次进行遍历，直到找到值等于某个给定值对应结点，进行删除，对于单纯的删除操作，时间复杂度为O(1)，但是对于遍历查找结点的操作时间负责就是O(n)，所以根据时间复杂度分析中的加法法则，第一种情况下链表操作的总时间复杂度为 O(n)。
而对于第二种情况，双向链表结点存储了前驱指针prev，直接就可以找到对应结点进行指针操作删除，所以其时间复杂度为O(1);而单链表因为没有前驱指针，依然需要从头开始遍历结点，直到p->next=q。说明p是q的前结点，因此这种情况下单链表的删除操作时间复杂度为O(n)
4.对于查询操作，双线链表也比单链表高效，因为我们可以记录上次上次的位置，再查询时只需要查询一半即可
5.LinkedHashMap的底层实现就是用的双向链表结构。

循环链表

1.循环链表是一种特殊的单链表，
2.尾结点指针是指向链表的头结点
3.处理环形结构数据时，使用用循环链表，比如注明的约瑟夫问题。

链表or数组

从时间复杂度分析性能

数组因为其需要内存空间的连续性，符合CPU的缓存机制，所以访问效率更高。
数组的缺点：
1.大小固定，申请需要整块的连续空间，如果空间不足，可能申请失败
2.无法动态扩容，如果申请空间不够，需要申请更大的空间，需要数据复制拷贝进入新的数组，非常耗时；而链表天然支持动态扩容，因为他不要内存空间的连续性
链表的缺点：
1.需要更多的内存空间来存储指向下一节点的指正
2.频繁的插入、删除操作，会导致内存的频繁申请和释放，容易造成内存碎片，Java中容易触发系统GC(Garbage Collection，垃圾回收)机制

链表的应用

链表的经典应用场景就是LRU 缓存淘汰算法。
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。
缓存大小是有限制的，在缓存空间满的时候，就需要使用一下策略进行清理，常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used)。
如何基于链表实现LRU 缓存淘汰算法？
首先，维护一个有序的单链表，规定越靠近尾部的数据时间越早，处理数据时：
1.如果数据已存在链表中，遍历结点，找到对应结点的数据进行删除，插入链表头部，时间复杂度为O(n)
2.如果数据不再链表中，分两种情况

• 如果此时缓存未满，则将此结点直接插入到链表的头部，时间复杂度为O(1)；
• 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部，时间复杂度为O(1)。

正确写出链表的6个技巧

• 理解指针或引用的含义
• 警惕指针丢失和内存泄漏
• 利用哨兵简化实现难度
• 重点留意边界条件处理
• 举例画图、辅助思考
• 多写多练

觉得文章不错的，给我点个赞哇，关注一下呗！
技术交流可关注微信公众号【君伟说】，加我好友一起探讨
微信交流群：加好友（备注技术交流）邀你入群，抱团学习共进步