CODEWITHSUNDEEP
data-structuresredis
Walton
Walton

Reputation: 187

How does a Redis List allow both indexing and left and right push/pop with constant time?

What kind of internal data structure does a redis list implement to allow this? A linked list would require O(n) indexing, and an array would require O(n) left/right push/pop.

Upvotes: 1

Views: 1100

Answers (1)

Ersoy
Ersoy

Reputation: 9624

According to the official documentation they are implemented as 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).

Because of that LPOP/RPOP or LPUSH/PUSH time complexity's are O(1) since they are dealing with heads/tails. Whereas LINDEXs time complexity is O(N).

Upvotes: 3

Related Questions