链表从原理到实战

作者 : 开心源码 本文共2062个字,预计阅读时间需要6分钟 发布时间: 2022-05-12 共230人阅读

引言

? ? ? ? 链表是一种线性表结构,其特点是非顺序存储,可充分利用碎片化的空闲内存。链表中的元素称为结点,结点通过逻辑指针维护相邻结点间的位置关系。 链表作为基础数据结构之一有多种形式:单链表、循环链表、双向链表及双向循环链表、跳表等。


带头单链表

从上图可见,链表中每个结点包含数据域和指向下一个结点的指针域。比较特别的是开头和结尾两个结点。我们习惯上把开头结点叫头结点,结尾结点叫尾结点。其中头结点中有个头指针,头指针中存有链表结构遍历的基地址,是链表能够遍历的前提。而尾结点指向下一个结点的指针域是空地址NULL。

单链表常规操作:

链表反转

? ? ? ? a、迭代法:迭代链表中每一个结点,设置当前结点的next指针为其前驱结点。

? ? ? ? b、头插法:迭代链表中每一个结点,一一插入链表头部。

? ? ? ? c、递归法:递归查找其前驱结点。

链表中环的检测:快慢双指针法,假如有环存在,则两个指针势必会相遇;否则快指针遍历结束。

删除倒数第N个节点:将链表反转,删除正数第n个元素后再次反转。

GitHub地址: SolodanceMagicq/algorithm_practice/blob/master/src/java/linkedlist/LinkedListAlgo.java

链表与数组性能大比拼

链表VS数组


核心应用

如何基于链表实现缓存LRU淘汰策略?

? ? ? ?维护一个有序单链表,越早访问的元素越靠近链表的尾部存储,当有元素访问时,顺序遍历链表。????

? ? ? ?1、假如当前元素已经在缓存链表中了,则先遍历得到当前元素对应的结点,再将其从缓存中删除,而后将其插入到链表头部。

? ? ? ?2、假如当前元素不在缓存链表中,则分两种情况:

? ? ? ? ? ? ?a、 当前缓存未满,直接将当前元素插入到链表头部。

? ? ? ? ? ? ?b 、当前缓存已满,则链表尾结点删除,将当前元素插入到链表头部。

?GitHub地址: SolodanceMagicq/algorithm_practice/blob/master/src/java/linkedlist/LRUSingleLinkedList.java

JDK的集合类LinkedList

? ? ? ?LinkeList是一个基于双向链表实现的集合,同时实现了双端队列,使其具有了队列和栈的特点。采用空间换时间思想,减少元素搜索的时间复杂度。实现细节详见《ArrayList&LinkedList源码分析》https://www.songma.com/p/8f94e7694886

Redis中的有序集合

? ? ? ?Redis的有序集合即是跳表实现。跳表是一个由链表+多级索引组成的动态数据结构。其查询、插入、删除操作的时间复杂度均为O(logn),可实现准确查找、按区间查找等特性。比较值得一提的是传统意义上二分查找只能应用在顺序存储结构(数组)的有序数列上,像链表这样的非顺序的存储结构,通过多级索引巧妙的利用空间换性能(空间复杂度为O(n))实现了在查询操作上,相似数组的二分查找的时间复杂度O(logn)。

? ? ? ?跳表索引动态升级:作为一种动态数据结构跳表是通过“随机函数”来维护索引与原始链表大小的平衡,也就是说假如链表中结点多了,索引结点也相应的增多,避免复杂度退化,以及查找、插入、删除的性能下降。相对于红黑树、AVL树这样的平衡二叉树,是通过左右旋的方式保持左右子树的大小平衡。

流水线设计模式

PipeLine

? ? ? ? 设计思路:将一整件事情,分成多个流水线Line x ,每条流水线是由A、B、C、D、E等多个结点构成的一条单链表。其中链表的结点也称为流水线的解决环节,且前一个结点的输出是后一个结点的输入。流水线这个复合结点,负责设置并启动线上的各环节结点,解决任务。这样整个事情,横向上切分为三条线并发解决,纵向又被切分为N个阶段。每个阶段由N(流水线条数)个相同的解决任务,将各阶段的任务统一交由一个固定线程数的线程池解决。尽管横向上每个流水线的执行效率固定(各环节均要等待其前面的环节数据到来才开始解决自己的事情);但假如流水线数量多,各环节同类任务的解决效率就有了提升。因而流水线模式适合将大的问题拆分成大量流水线解决数据的场景,假如流水线数量少,各环节同类任务少,则整体性能表现不显著。


总结

? ? ? ?链表和数组都是非常基础的线性表结构。

? ? ? ?数组支持随机访问特性,可以充分利用CPU缓存行,通过寻址公式来高效访问内存中的元素时间复杂度是O(1),但因为数组要维护物理存储空间连续性,在大量插入、删除元素后迁移数据,时间复杂度是O(n)。

? ? ? ?链表不需要维护连续的内存空间,可以充分利用碎片化的空闲内存,但失去了对CPU缓存的支持。通过逻辑指保持相邻结点间的位置关系,因而只能从头遍历查找定位元素,时间复杂度是O(n)。但删除和插入操作不需移动元素,只是改变相邻元素的指针,时间复杂度是O(1)。

? ? ? ?随着对链表的扩展及基于链表衍生的新的数据结构,像双向链表、跳表等,都是采用空间换性能的方式,来降低链表的查询复杂度。

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 链表从原理到实战

发表回复