Python 用 list 来模拟循环双链表有什么好处么？

[geeti]

比如在 lib/functools.py 的 lru_cache 中，
用
root = []
root[:] = [root,root,None,None]
root 作为循环双链表的一个点。这样做的好处是啥？
如果定义链表的 class ，感觉应该更省内存吧？

[zonghua]

实际上是作为循环队列， LRU 就是最少使用缓存算法，队列里把最少用到的排挤掉。用数组每次插入只要从新标志队头和队尾。

[geeti]

@zonghua 我知道这是 lru 的原理。

我想问的是，这里就用一个 list ，而不是定一个 class node(),然后写成链表。后者貌似更省内存

[geeti]

刷题感想。 leetcode 的 LRU 那道题，大家都是定义 linked list,但我发现 functools 里边直接使用 list ，特别简洁。但好像一个 list 比同样一个 node object 要耗内存

[wodesuck]

python 的 object 并不省内存，里面还有__dict__。。

[SlipStupig]

@wodesuck 定义一下 __slots__就好了

[langyu]

意义不大， 就像用汽车来模拟自行车一样。

[wizardforcel]

离散序列结构在插入和删除上省时间，在随机访问上花费时间。

lru 并不需要随机访问，删除倒是很频繁。

[hitmanx]

有没有比较过两者的效率？可以写个测试 perf 一下。倒是很多在直觉上应该由链表完成的东西，在实际 os 内核的实现里用的都是 array ，就是因为局部性原理带来的效率提升。