双向链表有哪些比较实用的应用场景？

[miniyao]

平时用到双向链表的机会少，有哪些场景下使用双向链表是比较好的选择？

[linhanqiu]

面试必考？平常的时候写小东西时提高效率？

[swulling]

双向链表是很常用的数据结构啊，因为单向链表没啥实用价值，基本用的链表都是双向的


比如 Redis 的双向链表，http://redisbook.com/preview/adlist/implementation.html，具体的用处有发布订阅机制，客户端维护，列表键底层实现之一，等等

[vjnjc]

以前都喜欢自己写结构，tree，node，链表，后来发现都有现成实现。。。

[RubyJack]

和 hashmap 一起搞 lru

[BlockBlockBlock]

哦，原来在 python 节点下……那就怪不得有人不懂了……

[sohoer]

Queue

[aheadlead]

STL 的 deque 了解一下

[bumz]

@aheadlead deque 一般不是链表实现的

[bumz]

@bumz STL deque 不能用链表实现，因为 STL deque 的 random access 是 O(1)

[aheadlead]

@bumz 是我错了…应该是 list

[bumz]

@BlockBlockBlock 变长数组随机是 O(1)，不能用链表实现

变长数组一般用空间自动翻倍的数组实现

[BlockBlockBlock]

@bumz

翻倍的空间从哪里来？怎么管理？

[BlockBlockBlock]

@bumz
我不明白你是怎么脑补出来我说的链表每个节点是装着一个元素的？如果每个链表节点装的是一片内存空间呢？这是典型的内存片的管理方式你们大学时候上操作系统课不学的吗？

[vincenttone]

php 的 array，redis 的 list 等等等等

[safeoy]

LRU

[wcsjtu]

Django 的 lru cache 了解一下？

[snail1988]

@BlockBlockBlock 要求随机存取 O(1)的数据结构为什么用链表，上来就喷别人

[BlockBlockBlock]

@snail1988

请问你看懂我在说什么了吗？
如果没看懂我也不多做解释了……
我不是你计算机老师，不负责教你计算机基础知识……

[orangeade]

python 里多了去了，有空多看看 python 解释器，pypy 和官方库的源码

[hitmanx]

@snail1988 我觉得他说的可能是类似 std::deque 的实现,实际上本质是 fixed-sized 的 vector 的 list,通过把每个 vector(chunk)的首地址 cache 起来,是可以做到 O(1)的 random access 的.但是实际上这个 cache 首地址的数据结构,就是一个 vector

https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
http://en.cppreference.com/w/cpp/container/deque