重学数据结构之链表篇

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

链表是怎么样的数据结构

链表，不需要连续的内存空间，通过“指针(引用)”将一组零散的内存块串联起来的数据结构。

内存块在链表中也叫“结点”，每个结点除了存储数据，还需要记录链上的下一个或者上一个结点的地址。

链表的特点

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个技巧

理解指针或引用的含义

警惕指针丢失和内存泄漏

利用哨兵简化实现难度

重点留意边界条件处理

举例画图、辅助思考

多写多练