不了解Redis双向链表，还说精通Redis？今天就为你讲透这面试盲区

这篇文章距离上次修改已过238天，其中的内容可能已经有所变动。

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;

不了解Redis双向链表，还说精通Redis？今天就为你讲透这面试盲区

评论已关闭

推荐阅读