redis列表底层实现之一——链表教程

注意标题中的“之一”，那么什么情况下，列表会使用链表作为其数据结构呢？

答案就是——列表键包含了大量的元素，或者列表中包含的元素都是比较长的字符串。

Ok，由于链表大家都比较熟悉，接下来就直接给出链表和链表节点的实现。

链表节点：

typedef struct listNode { // 由定义可以看出此链表为双向链表

struct listNode* prev;

struct listNode* next;

void *value;

}listNode;

链表：

typedef struct list {

listNode *head, *tail;

unsigned long len;

void* (*dup)(void *ptr); // 节点值复制函数

void (*free)(void *ptr); // 节点值释放函数

void (*match)(void *ptr, void *key); // 节点值比较函数

}list;

首先先说明listNode 和 list的大小。sizeof(listNode) = 12, sizeof(list) = 24。别忘了list中还有三个函数指针。下面给出在vs中的测试：

图中的信息很明显了，listT中的只是成员函数，而list中的是函数指针。

上图就是一个list结构了。

最后再多说一句，为什么listNode中的value要定义为void*？

value设置为void*，是因为这样可以保存各种不同类型的值，这就形成了一种多态，使得list中的dup、free、match函数都可以根据节点值来设置类型特定函数。