面试题：Redis链表与传统单向链表在数据结构设计上的主要差异

节点结构差异

Redis链表节点：Redis链表节点结构为adlist.h/listNode，每个节点除了保存自身数据外，还包含前驱和后继指针。结构如下：

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

这种结构使得Redis链表是双向链表。

传统单向链表节点：传统单向链表节点通常只包含后继指针和数据，结构类似：

typedef struct SingleListNode {
    struct SingleListNode *next;
    void *value;
} SingleListNode;

指针指向方式差异

Redis链表：每个节点有前驱指针prev和后继指针next，能在O(1)时间复杂度内访问前驱和后继节点。
传统单向链表：节点只有后继指针next，访问前驱节点需从头遍历，时间复杂度为O(n)。

链表操作实现差异

Redis链表：
- 插入操作：插入新节点时，利用前驱和后继指针，可快速定位插入位置并调整指针，时间复杂度为O(1)。例如向链表头部插入新节点，代码如下：

list *listAddNodeHead(list *list, void *value) {
    listNode *node = zmalloc(sizeof(*node));
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->next = list->head;
        node->prev = NULL;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}

- **删除操作**：删除节点时，通过前驱和后继指针可直接定位并删除，时间复杂度为O(1)。

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;
    zfree(node);
    list->len--;
}

传统单向链表：
- 插入操作：向链表头部插入新节点较简单，时间复杂度为O(1)；但向链表中间或尾部插入时，需先遍历找到插入位置，时间复杂度为O(n)。

SingleListNode* insertAtHead(SingleListNode* head, void* value) {
    SingleListNode* newNode = (SingleListNode*)malloc(sizeof(SingleListNode));
    newNode->value = value;
    newNode->next = head;
    return newNode;
}

- **删除操作**：删除节点时需先遍历找到待删除节点的前驱节点，时间复杂度为O(n)。

SingleListNode* deleteNode(SingleListNode* head, void* value) {
    SingleListNode* current = head;
    SingleListNode* prev = NULL;
    while (current && current->value != value) {
        prev = current;
        current = current->next;
    }
    if (!current) return head;
    if (!prev) {
        head = current->next;
    } else {
        prev->next = current->next;
    }
    free(current);
    return head;
}

性能影响

Redis链表：双向链表结构使得在执行插入、删除操作以及遍历链表时，无论从哪个方向都能高效进行，时间复杂度多为O(1)。但由于每个节点需要额外保存前驱指针，会占用更多内存空间。
传统单向链表：单向链表结构简单，内存占用相对较小。但在执行需要频繁查找前驱节点的操作时，时间复杂度为O(n)，性能较差。

应用场景影响

Redis链表：适用于需要频繁插入、删除节点，且需要双向遍历链表的场景，如实现Redis的发布/订阅功能，消息队列等。
传统单向链表：适用于数据插入和删除主要在头部进行，且不需要频繁查找前驱节点的场景，如实现栈结构（通过在链表头部操作实现入栈和出栈）。

星途面试题库

面试题：Redis链表与传统单向链表在数据结构设计上的主要差异

知识考点

面试题答案

节点结构差异

指针指向方式差异

链表操作实现差异

性能影响

应用场景影响