data-structures - Redis列表如何允许索引和恒定时间的左右推送/弹出？

Question

Redis列表实现了哪种内部数据结构以实现这一目的？链表将需要O(n)索引，而数组将需要O(n)左/右推/弹出。

Answer 1

根据official documentation，它们被实现为linked list。

Redis lists are implemented via Linked Lists. This means that even if you have millions of elements inside a list, the operation of adding a new element in the head or in the tail of the list is performed in constant time. The speed of adding a new element with the LPUSH command to the head of a list with ten elements is the same as adding an element to the head of list with 10 million elements.

What's the downside? Accessing an element by index is very fast in lists implemented with an Array (constant time indexed access) and not so fast in lists implemented by linked lists (where the operation requires an amount of work proportional to the index of the accessed element).

由于 LPOP / RPOP或 LPUSH / PUSH，时间复杂度就是 O(1)，因为它们处理的是头/尾。而 LINDEX的时间复杂度是 O(N)。