redis-adlist

[ohye3166]

https://ohye3166.github.io/redis-adlist/

简介：

链表作为一种常用的数据结构，链表内置在很多高级的编程语言里面，但C语言没有，所以Redis构建了自己的链表实现。链表在redis中的应用非常广泛，比如列表键包含了比较多元素，或者列表中包含的元素都是比较长的字符串时，redis就会用链表作为列表键的底层实现。Redis中的链表叫adlist（A generic doubly linked list implementation 一个通用的双端链表实现）,和普通单链表相比，它的方向可以向前或者向后，这是由于数据结构中定义了next和prev两个指针决定的，下面看下它的数据结构实现。

数据结构：

节点:

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

多个节点通过prev和next指针组成双端链表

链表：

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

特性：

1.双端：节点都带有prev和next指针，获取某个节点的前置节点和后置节点的负责度都是O(1)

list listAddNodeHead(list list, void value) { listNode node;

if ((node = zmalloc(sizeof(*node))) == NULL)
    return NULL;
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 list;

}

2.无环：表头节点的prev指针和表尾节点指针的next都指向NULL，对链表的访问以NULL为终点

list listCreate(void) { struct list list;

if ((list = zmalloc(sizeof(*list))) == NULL)
    return NULL;
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;

}

3.带表头和表尾指针：获取链表表头表尾复杂度为O(1)

/ Remove all the elements from the list without destroying the list itself. / void listEmpty(list list) { unsigned long len; listNode current, *next;

current = list->head;
len = list->len;
while(len--) {
    next = current->next;
    if (list->free) list->free(current->value);
    zfree(current);
    current = next;
}
list->head = list->tail = NULL;
list->len = 0;

}

4.带链表长度计数器：获取数量的负责度为O(1)

define AL_START_HEAD 0

define AL_START_TAIL 1

typedef struct listIter { listNode *next; int direction; } listIter;

listIter listGetIterator(list list, int direction) { listIter *iter;

if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
    iter->next = list->head;
else
    iter->next = list->tail;
iter->direction = direction;
return iter;

}

listNode listNext(listIter iter) { listNode *current = iter->next;

if (current != NULL) {
    if (iter->direction == AL_START_HEAD)
        iter->next = current->next;
    else
        iter->next = current->prev;
}
return current;

}

5.多态：链表节点使用void保存value，链表可以保存不同类型的值

[Alanaone]

( ﹡ˆoˆ﹡ )