redis数据结构实现(二)
2.链表和链表节点的实现
-
- *
每个链表节点由一个listNode实现
- *
typeof struct listNode{
//前置节点
struct listNode *prev;
//前置节点
struct listNode *next;
//值
void *value;
}listNode;
用list来持有链表
typeof struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表长度
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr);
//节点值释放函数
void (*free)(void *ptr)
//节点值对比函数
int (*match)(void *ptr,void *key)
}
redis链表的实现特性总结如下:
- 双端:链表节点带有prev和next指针
- 无环:表头节点的prev指针和表尾节点的next指针都指向null,访问链表以null为终点
- list中带头指针和表尾指针:通过list结构中的head和tail指针访问表头尾节点时间复杂度为O(1)
- 链表长度计数器:list结构中有len属性来记录链表长度,获取链表长度时间复杂度为O(1)
- 链表节点void* 指针来保存节点值,可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。