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

双向链表在Python里挺实用的，主要用在需要频繁在任意位置插入/删除的场景。

比如实现LRU缓存淘汰算法时，用collections.OrderedDict（内部就是双向链表）能快速把最近访问的节点移到头部，淘汰尾部节点。

再比如实现一个带“撤销”功能的编辑器，每次操作记录成节点，用双向链表可以方便地向前/向后遍历操作历史。

音乐播放器的播放列表也常用双向链表，方便上一曲/下一曲切换。

简单写个LRU的示意结构：

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        p, n = node.prev, node.next
        p.next, n.prev = n, p

    def _add_to_head(self, node):
        n = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = n
        n.prev = node

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_head(node)
            return node.val
        return -1

    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add_to_head(node)
        self.cache[key] = node
        if len(self.cache) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

总结：双向链表适合需要前后遍历操作的场景。

面试?

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


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

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

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

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

翻倍翻倍翻倍……你们既然都知道翻倍了，两个问题先自己去想清楚了再过了。我发现我们很难交流……

1. 既然空间翻倍了，那翻倍的空间从哪里来？ a) 把内存条从数组的尾端掰断然后再加一段吗？这怕不是要实现边长数组，这是要实现变长内存条，还是能从中间拉长的那种。b) 开一片新内存然后把旧的全部复制过去？嗯，小数组还好，大数组真是酸爽……

2.既然你们都知道翻倍了，那翻倍隐含的 log2(N) 被怪物吃了吗？想想这个 log2(N) 去哪里了……

只会喊些什么，翻倍，O(1)。翻倍怎么翻？ O(1) 怎么来的？想过吗？