摘要：双向链表双向链表作为在日常开发中最常用的数据结构之一，应用十分广泛，在诸多著名开源项目中如的结构，的中均是核心实现。
双向链表
双向链表作为在日常开发中最常用的数据结构之一，应用十分广泛，在诸多著名开源项目中如redis的list结构， groupcache的lru中均是核心实现。在设计此类数据集合的时候，外面看上去链表似乎与数组相似，但链表是一个非连续性内存的存储方案，提供了高效的节点重排能力与顺序访问方式，对比与操作数组，只需知道给定项的地址和位置的链接就能在内存中找到它，并且可以通过增减节点的方式来灵活的调整长度。反而数组，比如插入一个新的元素，那么该位置后的元素都要往后移动一位。
标准的双向链表实现redis 中的双向链表
golang 中的双向链表
其结构如图
在双向链表中头结点的前指针为空，尾节点的后指针为空, 对头尾的操作十分简单, 插入头节点只需要将新节点的next设置为当前链表的头节点， 当前列表的prev为新节点， 并与之交换位置即可， 插入尾部反之
在节点中间按游标插入的话则需要考虑正向反向的问题, 下图当i 为正数表示正向插入，负数反向插入, 其实不管是只操作头尾节点还是中间节点，其核心就是交换当前节点与前一个和后一个节点之间的链接
将某个节点移动至头部跟插入头部动作多了一步交换当前节点前后节点链接的操作
而删除某个节点就只需要将其前后节点的链接互相相连，使其不被引用，它会自动被回收掉
LRU全称Least Recently Used, 直译为“最近最少使用”, 其对于内存管理方面十分有效，比如容量只有十的一个集合，当写入第十一条数据时候，最少使用的那个数据将会被淘汰，故此方法很适用于对有给定容量限制的热数据做缓存管理
在开源项目groupcache中, 缓存的过期没有设置过期时间而是依赖于LRU淘汰机制，那么其用来实现LRU的核心就是一个双向链表, 为了保证效率， 缓存数据被保存在一个Map中使每次缓存的存取时间复杂度为O(1), 而双向链表则负责管理内存的容量以及实现淘汰机制
在写入新的缓存项时，会把其插入至链表的头部， 并且判断如果当前链表长度大于给定长度时，删除链表尾部的元素，同时删除其在map中的key
每当有访问命中缓存时, 会将命中的缓存移至链表头部
上述插入和命中时将其放到链表头部的策略，使得链表尾部的元素永远是使用得最少的那个缓存，故新缓存进来时就将其淘汰。
本文说明了双向链表的实现以及其实际应用，但是在真实应用中，golang 的双向链表是非线程安全的，如遇到并发情况操作链表则会因为找不到地址而报错， 所以groupcache项目在从LRU策略中获取缓存的时候，在外部包了一个带读写锁的结构体来保证其并发安全
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/62056.html
摘要：双向链表用于管理缓存数据结点的顺序，新增数据和缓存命中最近被访问的数据被放置在结点，尾部的结点根据内存大小进行淘汰。 了解 LRU 之前，我们应该了解一下缓存，大家都知道计算机具有缓存内存，可以临时存储最常用的数据，当缓存数据超过一定大小时，系统会进行回收，以便释放出空间来缓存新的数据，但从系统中检索数据的成本...
摘要：散列表其实是基于数组实现的，可以说，没有数组就没有散列表。根据下图你更能理解散列表哈希函数结合上面的理解，你应该可以想到，其实散列表的关键就在于哈希函数的实现。 1. 什么是散列表？ 散列表（Hash Table）又叫做哈希表，是一种很常用的数据结构。散列表其实是基于数组实现的，可以说，没有数组就没有散列表。先来举一个简单的例子，来认识一下什么是散列表。 假如在学校的运动会上，每个运动...
摘要：剑指缓存实现声明文章均为本人技术笔记，转载请注明出处解题思路缓存两种功能获取的对应，不存在返回版本版本设置缓存已满，删除最近最久未被使用的节点，添加新节点进缓存缓存未满，节点存在，修改节点不存在，添加新节点进缓存解题思路由于缓存插入和删除 剑指offer/LeetCode146/LintCode134_LRU缓存实现 声明 文章均为本人技术笔记，转载请注明出处[1] https://s...
阅读 2911·2021-11-24 10:22
阅读 2991·2021-11-23 10:10
阅读 1253·2021-09-28 09:35
阅读 1692·2019-08-29 13:16
阅读 1356·2019-08-26 13:29
阅读 2744·2019-08-26 10:27
阅读 650·2019-08-26 10:09
阅读 1397·2019-08-23 18:05
