Redis的双向链表通常用于构建复杂的数据结构,比如有序集合。在Redis内部,双向链表是一种非常基本的数据结构,它可以用来有效地实现各种功能,比如列表键、发布/订阅系统等。
在Redis中,双向链表节点的结构体定义如下:
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
其中,prev指针指向前一个节点,next指针指向后一个节点,value是节点的值。
双向链表的结构体定义如下:
typedef struct list {
listNode *head;
listNode *tail;
void (*free)(void *ptr);
unsigned long len;
} list;
其中,head指针指向链表的表头节点,tail指针指向链表的尾节点,free是链表节点值的释放函数,len是链表的长度。
在Redis中,双向链表的主要操作有:创建链表、添加节点、删除节点、查找节点等。
创建链表:
list *listCreate(void) {
struct list *list;
list = zmalloc(sizeof(*list));
list->head = list->tail = NULL;
list->len = 0;
list->free = NULL;
return list;
}
添加节点:
int listAddNodeHead(list *list, void *value) {
listNode *node;
node = zmalloc(sizeof(*node));
node->value = value;
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++;
return 0;
}
删除节点:
void listDelNode(list *list, listNode *node) {
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}
查找节点:
listNode *listSearchKey(list *list, void *key) {
listNode *node;
listIter *iter;
void *k;
if (list->match) {
iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
k = listNodeValue(node);
if (list->match(key, k)) {
listReleaseIterator(iter);
return node;
}
}
listReleaseIterator(iter);
} else {
node = list->head;
while (node) {
if (key == node->value) {
return node;
}
node = node->next;