引言
? ? ? ? 链表是一种线性表结构,其特点是非顺序存储,可充分利用碎片化的空闲内存。链表中的元素称为结点,结点通过逻辑指针维护相邻结点间的位置关系。 链表作为基础数据结构之一有多种形式:单链表、循环链表、双向链表及双向循环链表、跳表等。
带头单链表
从上图可见,链表中每个结点包含数据域和指向下一个结点的指针域。比较特别的是开头和结尾两个结点。我们习惯上把开头结点叫头结点,结尾结点叫尾结点。其中头结点中有个头指针,头指针中存有链表结构遍历的基地址,是链表能够遍历的前提。而尾结点指向下一个结点的指针域是空地址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)。
? ? ? ?随着对链表的扩展及基于链表衍生的新的数据结构,像双向链表、跳表等,都是采用空间换性能的方式,来降低链表的查询复杂度。