Describe the Redis List type: which commands you use to add and remove elements, how you read a range out of it, and how the cost of those operations differs between the ends of the list and the middle.
answer
- ordered, duplicates allowed, insertion order
- LPUSH/RPUSH/LPOP/RPOP = O(1) ends
- LRANGE = O(S+N); LINDEX/LSET/LINSERT = O(N)
- quicklist: linked list of listpack nodes
- emptying a list deletes the key
basics
~20 sAn ordered sequence of strings with fast ends. LPUSH/RPUSH add at head/tail, LPOP/RPOP remove there, all O(1). LRANGE reads a slice; LINDEX/LSET/LINSERT/LREM touch the middle and are O(N) because Redis walks the list. Duplicates are allowed, order is insertion order, and an emptied list key is deleted.
solid answer
~50 sA Redis List is an ordered collection of string elements that allows duplicates and preserves insertion order. LPUSH and RPUSH prepend and append (both variadic), LPOP and RPOP remove and return from the head and tail, and all four are O(1). LRANGE key start stop returns a slice with inclusive, optionally negative indexes, so LRANGE key 0 -1 is the whole list; its cost is O(S+N) — the offset to reach the range plus the elements returned. Anything positional in the middle is O(N): LINDEX, LSET, LINSERT, LREM, and LTRIM's cost scales with what it removes. The underlying quicklist is a linked list of packed nodes, so Redis reaches either end immediately but must walk to reach index 500,000. When the last element is popped the key is deleted automatically, so an empty list never exists — which is why LLEN on a missing key returns 0 rather than erroring.
code
text · 6 linesRPUSH jobs j1 j2 j3
LPOP jobs # "j1" - FIFO
LPUSH feed:42 post9
LRANGE feed:42 0 9 # ten newest, newest first
LLEN feed:42 # O(1)go deeper
Name the four push/pop commands, LRANGE with negative indexes, and that the ends are fast while the middle is not.
Give the complexities precisely (O(1) ends, O(S+N) for LRANGE, O(N) positional) and tie them to the quicklist layout.
Discuss operational consequences: huge LRANGE replies, iterating in windows, and when a Sorted Set is the right structure instead.
Frame the structure choice against access patterns and growth, including where a List stops scaling and a different Redis structure or external queue takes over.
## What a List is A Redis List is an ordered sequence of string values addressed by position. It permits duplicates, preserves insertion order, and has no size limit other than memory (up to 2^32-1 elements). It is the natural fit for queues, stacks, activity feeds and recent-item buffers. ## The core commands - LPUSH key v [v ...] and RPUSH key v [v ...] add at the head and tail. Both are variadic; note LPUSH a b c leaves the list as c, b, a because each value is pushed in turn. - LPOP key [count] and RPOP key [count] remove and return from the head and tail; the optional count arrived in Redis 6.2. - LLEN key returns the length in O(1). - LRANGE key start stop returns an inclusive range; indexes are zero-based and negatives count from the end, so -1 is the last element. Out-of-range values are clamped rather than erroring. - LINDEX, LSET, LINSERT and LREM operate positionally or by value. LPOS (Redis 6.0.6) finds the index of a matching element. - LMPOP and BLMPOP (Redis 7.0) pop from the first non-empty of several keys. Pushing and popping at the same end gives a stack; pushing at one end and popping at the other gives a FIFO queue — the classic RPUSH plus LPOP job queue. ## Why the ends are fast and the middle is not The implementation is a quicklist: a doubly linked list whose nodes each hold a compact listpack of several elements. Redis keeps pointers to the head and tail nodes, so pushing or popping at either end is constant time regardless of length. Reaching index i means walking nodes from the nearer end until the offset is covered — linear in the distance. Hence LINDEX and LSET are O(N), LINSERT is O(N), and LREM is O(N) because it scans for matches. LRANGE is documented O(S+N): S is the offset from the nearer end to the start of the range, N the number of elements returned. LRANGE key 0 10 on a huge list is cheap; LRANGE key 500000 500010 is not; and LRANGE key 0 -1 on a million-element list is expensive twice over — it walks everything and materialises a reply containing everything. Iterate large lists in small windows instead. ## Practical consequences Because middle access is linear, a List is the wrong structure when you need lookup by value, membership tests, or ordering by score — those are Sets and Sorted Sets. Use a List when access is at the ends: newest-first feeds, work queues, bounded logs. Remember the auto-delete rule too. Popping the final element removes the key entirely, so a list-shaped queue disappears when drained and reappears on the next push. Code should treat a missing key and an empty list as the same state, and any TTL is lost when the key is deleted and later recreated by a push. ## Small worked example RPUSH queue j1 j2 j3 then LPOP queue yields j1, giving FIFO. LPUSH feed post9 then LRANGE feed 0 9 yields the ten newest items, newest first — the standard timeline read.
- Why is LRANGE key 0 -1 discouraged on a large list?It walks every element and materialises the entire list into one reply, so CPU and output buffer both scale with list length. On a million-element list that is a multi-megabyte reply produced by a single command. Read in bounded windows such as LRANGE key 0 99 instead.
- What happens to a Redis List key when the last element is popped?The key is deleted automatically, because Redis never keeps empty aggregate keys. EXISTS then returns 0, LLEN returns 0, and any TTL previously set on the key is gone. A later push recreates the key with no expiry.
saying these in an interview costs you the question
- Claiming LINDEX or LSET is O(1) like an array index
- Calling LRANGE key 0 -1 routinely on large lists
- Expecting an empty list key to persist after the last pop
- Using a List for membership checks or de-duplication instead of a Set
- Thinking LPUSH a b c leaves the list in the order a, b, c