Redis List Deep Dive: Interview Questions, Encodings, and Performance Insights

List Interview Points Analysis

List is a fundamental Redis object that attracts many interview questions. Interviews focus on common List operations and the underlying implementation details. Candidates must master List operations and understand its encoding schemes and internal structures.

Interview Questions

1. Is List strictly first‑in‑first‑out?

Analysis

The phrase “strictly first‑in‑first‑out” implies only enqueue at the tail and dequeue at the head. Since List is a double‑ended data structure, it can also operate as last‑in‑first‑out.

Answer

List is double‑ended, so it is not strictly FIFO; it can also be LIFO.

2. What are the underlying encoding methods for List objects?

Analysis

Before Redis 3.2 and after, List uses different encodings. Knowing the differences across Redis versions is a plus in interviews.

Answer

Before version 3.2, List uses ZIPLIST for small, short elements and LINKEDLIST otherwise. Starting with version 3.2, List is implemented with QUICKLIST , a compressed list of doubly linked nodes; newer versions further optimize ZIPLIST into PACKLIST .

3. How does ZIPLIST compress data?

Analysis

ZIPLIST is designed for memory efficiency. Its structure can be described in three parts.

* The general layout of the ziplist is as follows:
* <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

The entry structure is:

<prevlen> <encoding> <entry-data>

1. Header: fields zlbytes, zltail, zllen. 2. Data part: a list of entries, each containing prevlen, encoding, and the actual data. 3. Footer: a single byte zlend marking the end.

Answer

ZIPLIST consists of a header, the entry list, and a footer. The header records total bytes, tail offset, and entry count; each entry stores the previous node length, encoding, and data; the footer is a one‑byte terminator.

4. Can a List backed by ZIPLIST be traversed backward?

Analysis

Since List is double‑ended, any encoding must support reverse traversal. ZIPLIST achieves this because each entry records the length of the previous node.

Answer

Yes. ZIPLIST stores the length of the previous node in each entry, allowing the iterator to move backward by subtracting that length from the current address.

5. What is the time complexity of querying the node count in a ZIPLIST?

Analysis

The ZIPLIST header contains the zllen field, which normally allows O(1) retrieval. However, zllen is a 2‑byte field; if the list exceeds 65,535 entries, the field overflows and a full scan is required.

Answer

Typically O(1) using the header’s zllen field, but when the number of nodes exceeds 65,535 the field is invalid and the count must be obtained by O(n) traversal.

6. What is the time complexity of querying the node count in a LINKEDLIST?

Analysis

The LINKEDLIST header defines a len field that stores the number of nodes.

// from Redis 5.0.5
typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

Answer

O(1), because the len field in the header directly provides the node count.

Summary

List is a basic Redis data object with multiple encoding strategies. Redis continuously optimizes these structures to save memory and improve performance, which is a key factor behind its efficiency.