redis6.0源码学习（三）adlist

redis6.0源码学习（三）adlist

1、数据结构

下面是adlist主要结构体：

typedef struct listNode {struct listNode *prev; //prev指针，指向前一个节点struct listNode *next;//next指针，指向下一个节点void *value;
} listNode;
//迭代器
typedef struct listIter {listNode *next;int direction; //迭代器方向
} listIter;typedef struct list {listNode *head; //head指针指向链表头部listNode *tail; //head指针指向链表头部void *(*dup)(void *ptr); //自定义节点值的复制函数，如果不定义，默认策略的复制操作会让原链表和新链表共享同一个数据域void (*free)(void *ptr);//自定义节点free操作 int (*match)(void *ptr, void *key);//search操作的时候比较两个value是否相等，默认策略是比较两个指针的值unsigned long len; //记录链表的长度，获取长度操作可以O(1)返回
} list;

下面是插入了“hello“、”world“、”redis“ 三个元素的示意图：

2、创建

listCreate 创建一个空元素的链表, 结构体中元素都赋0值。

/* Create a new list. The created list can be freed with* AlFreeList(), but private value of every node need to be freed* by the user before to call AlFreeList().** On error, NULL is returned. Otherwise the pointer to the new list. */
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、插入节点

redis双向链表插入实现了三种插入方法，分别是头插入，尾插入，特定节点前后插入。下面分别来看下三种方法：

3.1 链表头插入

/* 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) //先申请一个新的node节点大小的内存给新node节点使用return NULL;node->value = value;if (list->len == 0) { //链表为空的情况list->head = list->tail = node; //step 1 对应下图中的圈1node->prev = node->next = NULL; //step 2 对应下图中的圈2} else {//链表不为空node->prev = NULL; //step1node->next = list->head; //step2list->head->prev = node; //step3list->head = node; //step4}list->len++;//更新链表长度return list;
}

下面是链表头插入两种情况的图示：

• 1、链表为空的情况

• 2、链表不为空的情况

3.2 链表尾插入

在链表尾部插入和在链表头部插入一样，也是分为两种情况：1、链表为空的情况， 2、链表不为空的情况。其中链表为空的情况时和在链表头插入一样。

list *listAddNodeTail(list *list, void *value)
{listNode *node;if ((node = zmalloc(sizeof(*node))) == NULL)//先申请一个新的node节点大小的内存给新node节点使用return NULL;node->value = value;if (list->len == 0) {list->head = list->tail = node;//和链表头插入逻辑一样node->prev = node->next = NULL;} else {node->prev = list->tail;//step1node->next = NULL; //step2list->tail->next = node;//step3list->tail = node;//step4}list->len++; //更新链表长度return list;
}

链表为空的示意图参考在头部插入的示意图，下图为链表不为空时在尾部插入的示意图：

3.3 链表某节点前后插入

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {listNode *node;if ((node = zmalloc(sizeof(*node))) == NULL) //先申请一个新的node节点大小的内存给新node节点使用return NULL;node->value = value;if (after) {//在指定节点后面插入node->prev = old_node; //让新节点prev指向旧节点node->next = old_node->next;//让新节点的next指向旧节点的nextif (list->tail == old_node) { //有可能是在尾节点后插入新的节点，退化成了尾节点后插入的情况，示意图见上图3list->tail = node;}} else {//默认在指定节点前面插入node->next = old_node;//step1node->prev = old_node->prev; //step2if (list->head == old_node) {//有可能是在首节点前插入新节点， 退化成了头节点前面插入的情况，示意图建上图2list->head = node;//step3}}if (node->prev != NULL) {//在指定节点后面插入时，更新旧节点的next指向新节点node->prev->next = node;}if (node->next != NULL) {//在指定节点前面插入时，更新旧节点的pre指向新节点node->next->prev = node;//step4}list->len++;//更新长度return list;
}

示意图如下，圈中的数字对应代码中的step

4、删除节点

/* Remove the specified node from the specified list.* It's up to the caller to free the private value of the node.** This function can't fail. */
void listDelNode(list *list, listNode *node)
{if (node->prev) //说明node不是第一个节点node->prev->next = node->next;elselist->head = node->next; //是第一个节点的情况if (node->next) //说明node不是最后一个节点node->next->prev = node->prev;elselist->tail = node->prev;//是最后一个节点的情况if (list->free) list->free(node->value);zfree(node);//释放内存list->len--;//更新长度
}

5、合并链表

/* Add all the elements of the list 'o' at the end of the* list 'l'. The list 'other' remains empty but otherwise valid. */
void listJoin(list *l, list *o) {if (o->head)o->head->prev = l->tail;if (l->tail)l->tail->next = o->head;elsel->head = o->head;if (o->tail) l->tail = o->tail;l->len += o->len;/* Setup other as an empty list. */o->head = o->tail = NULL;o->len = 0;
}

6、总结

看代码终究不如自己实现一遍，练习网站奉上，大家可以去这里练习一下，自己实现一遍。

https://leetcode-cn.com/problems/design-linked-list/