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

Question

我知道redis列表是通过底层的链表实现的。但是，在计算列表长度的时间复杂度时，\xe2\x80\x99t 应该是 O(n)\xef\xbc\x9f

\n

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)。