h*****n
发帖数: 209 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
e***l
发帖数: 710 | 2 为了删除节点的操作是o (1). 不然就成o (n)了 |
h*****n
发帖数: 209 | 3 【 以下文字转载自 Programming 讨论区 】
发信人: hanuman (天竺神猴), 信区: Programming
标 题: 为什么Cache LRU多用doubly linked list而不是single linked list来实现呢?
发信站: BBS 未名空间站 (Thu Oct 23 16:56:37 2014, 美东)
在Cache LRU实现的时候，为什么都是用doubly linked list而不是single linked
list呢？
请大牛赐教。 |
e***l
发帖数: 710 | 4 为了删除节点的操作是o (1). 不然就成o (n)了 |
h*****n
发帖数: 209 | 5 还想问一下，直接就用一个简单的circular buffer是不是也可以实现cache LRU啊？为
啥非要弄doubley linked list呢？ |
c****p
发帖数: 6474 | 6 想像一下这个场景：
1234，3被hit。如果用buffer/数组的话，需要把3放到第一个，把1和2向后移。最坏情
况下的代价是O(n)，代价太高。带hash的双链表能保证查找、增删和改变顺序的代价都
是常数时间的。
【在 h*****n 的大作中提到】
: 还想问一下，直接就用一个简单的circular buffer是不是也可以实现cache LRU啊？为
: 啥非要弄doubley linked list呢？
|
