redis|redis 链表 redis链表

链表的实现方式有很多种，常见的主要有三个，单向链表、双向链表、循环链表。 1、单链表
文章图片
1-1

结构：第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
优点：链表特性插入和删除方便，只需要考虑相邻节点指针的变化，因此为常数级时间复杂度O(1)
缺点：查找慢，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，因此时间复杂度为O(N)。

2、双向链表

文章图片
1-2

结构：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
优点：链表特性插入和删除方便

在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)，而双向链表可以双向遍历。

删除给定指针指向的结点。假设已经找到要删除的节点，要删除就必须知道其前驱节点和后继节点，单链表想要知道其前驱节点只能从头开始遍历，时间复杂度为0(n)，而双向链表由于保存了其前驱节点的地址，因此时间复杂度为0(1)。

缺点：查找慢，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。

3、循环链表

文章图片
1-3

结构：一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
优点：在于链尾到链头，链头到链尾比较方便适合处理的数据具有环型结构特点。获取第一个节点时间复杂度为O(1)，那么获取最后一个节点也为O(1) 如获取栈顶、栈底、队头、队尾等操作
缺点：和其他链表差不多

redis 的链表结构（adlist.h）

//节点 typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode; //迭代器 typedef struct listIter { listNode *next; int direction; } listIter; //list 结构 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;

从上面代码可以看出redis 链表是双向链表

/* Add a new node to the list, to head, containing the specified 'value' * pointer as value. * * On error, NULL is returned and no operation is performed (i.e. the * list remains unaltered). * On success the 'list' pointer you pass to the function is returned. */ list *listAddNodeHead(list *list, void *value) { listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = https://www.it610.com/article/value; if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { // 将头节点的prev赋值为NULL node->prev = NULL; node->next = list->head; list->head->prev = node; list->head = node; } list->len++; return list; } /* Add a new node to the list, to tail, containing the specified 'value' * pointer as value. * * On error, NULL is returned and no operation is performed (i.e. the * list remains unaltered). * On success the 'list' pointer you pass to the function is returned. */ list *listAddNodeTail(list *list, void *value) { listNode *node; if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; node->value = https://www.it610.com/article/value; if (list->len == 0) { list->head = list->tail = node; node->prev = node->next = NULL; } else { node->prev = list->tail; // 将头节点的next赋值为NULL node->next = NULL; list->tail->next = node; list->tail = node; } list->len++; return list; }

从listAddNodeTail 和listAddNodeHead 可以看出redis 双向链表是无环的。结构特性如下：（网上都这么说）

双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1)
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ，对链表的访问以 NULL 为终点。
带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。
带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O(1)。
多态：链表节点使用 void*（“无类型指针”，可以指向任何数据类型）指针来保存节点值，并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。