面试题：Redis链表在源码中的数据结构定义及基本操作

Question

请描述Redis链表在源码中是如何定义数据结构的？并简要说明插入和删除节点操作的大致实现思路。

Answer 1

Redis链表数据结构定义

在Redis源码中，链表相关数据结构定义在adlist.h文件中。

1. 链表节点：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

• prev指针指向前一个节点，next指针指向后一个节点，value指针指向节点存储的值，可以是任意类型。

2. 链表：

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
} list;

• head和tail分别指向链表头和链表尾节点。
• len记录链表节点数量。
• dup、free和match是函数指针，用于复制值、释放值以及比较值。

插入节点操作大致实现思路

1. 头插法：
   • 创建新节点，并分配内存空间。
   • 将新节点的next指针指向当前链表的head节点。
   • 如果链表不为空，将当前head节点的prev指针指向新节点。
   • 更新链表的head指针为新节点。
   • 如果链表为空，同时更新tail指针为新节点。
   • 更新链表长度len。
2. 尾插法：
   • 创建新节点，并分配内存空间。
   • 将新节点的prev指针指向当前链表的tail节点。
   • 如果链表不为空，将当前tail节点的next指针指向新节点。
   • 更新链表的tail指针为新节点。
   • 如果链表为空，同时更新head指针为新节点。
   • 更新链表长度len。

删除节点操作大致实现思路

1. 查找要删除的节点：通过遍历链表，根据match函数指针（如果设置了）找到要删除的节点。
2. 调整指针：
   • 如果要删除的节点是head节点，将head指针指向当前节点的next节点。如果next节点存在，将其prev指针设为NULL。
   • 如果要删除的节点是tail节点，将tail指针指向当前节点的prev节点。如果prev节点存在，将其next指针设为NULL。
   • 如果要删除的节点在链表中间，将当前节点的prev节点的next指针指向当前节点的next节点，当前节点的next节点的prev指针指向当前节点的prev节点。
3. 释放资源：
   • 使用free函数指针（如果设置了）释放节点中value指向的值的内存。
   • 释放节点本身的内存。
4. 更新链表长度：链表长度len减1。