algorithm - 为什么redis命令'LLEN'具有恒定的时间复杂度而不是O（n）？

Question

我知道redis列表是由引擎盖下的链表实现的。但是在计算列表长度的时间复杂度时，不应该是O(n)吗？</p>

标签： algorithmdata-structuresredistime-complexitybig-o

Answer 1

您可以在https://github.com/redis/redis/blob/unstable/src/adlist.h找到列表类型的声明。如果您查看第 50 行附近的部分，您会发现：

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;

请注意，unsigned long len它存储列表的长度。这就是为什么O(1)。