重学数据结构之链表篇

56次阅读

共计 1939 个字符,预计需要花费 5 分钟才能阅读完成。

本文是重新数据结构系列文章的第二篇,本文和大家一起探讨链表的相关知识。
@[toc]

链表是怎么样的数据结构

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

链表的特点

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

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

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

正文完
 0