个人中心
gpt4 book ai didi

详解Redis中的双链表结构

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 29 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章详解Redis中的双链表结构由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

Redis中双链表实现的基本结构： 1.节点结构 。

?
1
2
3
4
5
typedef struct listNode {
   struct listNode *prev; //前向节点
   struct listNode *next; //后向节点
   void *value;       //该节点的值
} listNode;

2.双向链表结构 。

?
1
2
3
4
5
6
7
8
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;

3.双向链表遍历器 。

?
1
2
3
4
5
6
7
8
9
typedef struct listIter {
   listNode *next;  //下一个节点
   int direction;
} listIter;
 
  方向定义
 
   #define AL_START_HEAD 0 //向前查找
   #define AL_START_TAIL 1  //向后查找

4.宏定义函数 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)
 
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
 
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

5.定义函数 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
list *listCreate( void ); //创建一个新的链表。该链表可以使用AlFree（）方法释放。
 
                //但使用AlFree（）方法前需要释放用户释放私有节点的值。
 
                //如果没有创建成功，返回null；创建成功则返回指向新链表的指针。
 
 
void listRelease(list *list); //释放整个链表，此函数不会执行失败。调用zfree(list *list)方法,定义在Zmalloc.c中。
 
 
list *listAddNodeHead(list *list, void *value); //向链表头部中增加一个节点
 
 
list *listAddNodeTail(list *list, void *value);  //向链表尾部增加一个节点
 
 
list *listInsertNode(list *list, listNode *old_node, void *value, int after); //向某个节点位置插入节点 after为方向
 
 
void listDelNode(list *list, listNode *node); //从链表上删除特定节点，调用者释放特定私用节点的值。
 
                               //该函数不会执行失败
listIter *listGetIterator(list *list, int direction); //返回某个链表的迭代器。
 
                                  //迭代器的listNext（）方法会返回链表的下个节点。direction是方向
 
                                 //该函数不会执行失败。
 
 
listNode *listNext(listIter *iter);       
 
 
void listReleaseIterator(listIter *iter);      //释放迭代器的内存。
 
 
list *listDup(list *orig);                //复制整个链表。当内存溢出时返回null，成功时返回原链表的一个备份
 
                                 //不管该方法是否执行成功，原链表不会改变。
 
 
listNode *listSearchKey(list *list, void *key); //从特定的链表查找key。成功则返回第一个匹配节点的指针
 
                                 //如果没有匹配，则返回null。
 
 
listNode *listIndex(list *list, long index);   //序号从0开始，链表的头的索引为0.1为头节点的下个节点。一次类推。
 
                             //负整数用来表示从尾部开始计数。-1表示最后一个节点，-2倒数第二个节点
 
                              //如果超过链表的索引，则返回null
 
 
void listRewind(list *list, listIter *li) {
   li->next = list->head;
   li->direction = AL_START_HEAD;
}
 
void listRewindTail(list *list, listIter *li) {
   li->next = list->tail;
   li->direction = AL_START_TAIL;
}
 
 
void listRotate(list *list);         //旋转链表，移除尾节点并插入头部。

  。

list结构和listNode结构的API list和listNode都有它们自己的一族API，这里贴出来学习一下redis的源码(ps:下面的代码都是我仿照redis改写能直接编译运行的代码) 。

list *listCreate(void) 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * 创建一个新列表
  *
  * T = O(1)                                                              
  */
list *listCreate(void)
{
   struct list *list;
 
   // 为列表结构分配内存
   list = (struct list *)malloc(sizeof(struct list));
   if (list == NULL)
     return NULL;
 
   // 初始化属性
   list->head = list->tail = NULL;
   list->len = 0;
   list->dup = NULL;
   list->free = NULL;
   list->match = NULL;
 
   return list;
}

void listRelease(list *list) 。

  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * 释放整个列表
  *
  * T = O(N), N为列表长度
  */
void listRelease(list *list)
{
   unsigned long len;
   listNode *current, *next;
 
   current = list->head;
   len = list->len;
 
   while (len --) {
     next = current->next;
     // 如果列表有自带的free方法，那么先对节点值调用它
     if (list-> free ) list-> free (current->value);
     // 之后释放节点
     free (current);
     current = next;
   }
   free (list);
}

list *listAddNodeHead(list *list, void *value)
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
  * 新建一个包含给定value的节点，并将它加入到列表的表头
  *
  * T = O(1)                                                              
  */
list *listAddNodeHead(list *list, void *value)
{
   listNode *node;
 
   node = (listNode *) malloc ( sizeof (listNode));
   if (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;
}

list *listAddNodeTail(list *list, void *value) 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
  * 新建一个包含给定value的节点，并把它加入到列表的表尾
  *
  * T = O(1)
  */
list *listAddNodeTail(list *list, void *value)
{
   listNode *node;
   
   node = (listNode *) malloc ( sizeof (listNode));
   if (node == NULL)
     return NULL;
 
   if (list->len == 0) {
     // 第一个节点
     list->head = list->tail = node;
     node->prev = node->next = NULL;
   } else {
     // 不是第一节点
     node->prev = list->tail;
     node->next = NULL;
     list->tail->next = node;
     list->tail = node;
   }
 
   list->len ++;
 
   return list;
}

list *listInsertNode(list *list, listNode *old_node, void *value, int after) 。

  。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
  * 创建一个包含值value的节点
  * 并根据after参数的指示，将新节点插入到old_node的之前或者之后
  *
  * T = O(1)
  */
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
{
   listNode *node;
 
   node = (listNode *) malloc ( sizeof (listNode));
   if (node == NULL)
     return NULL;
 
   if (after) {
     // 插入到old_node之后
     node->prev = old_node;
     node->next = old_node->next;
     // 处理表尾节点
     if (list->tail == old_node) {
       list->tail = node;
     }
   } else {
     // 插入到old_node之前
     node->next = old_node;
     node->prev = old_node->prev;
     // 处理表头节点
     if (list->head == old_node) {
       list->head = node;
     }
   }
 
   // 更新前置节点和后继节点的指针(这个地方很经典，节约代码)
   if (node->prev != NULL) {
     node->prev->next = node;
   }
   if (node->next != NULL) {
     node->next->prev = node;
   }
 
   // 更新列表节点
   list->len ++;
 
   return list;
}

void listDelNode(list *list, listNode *node) 。

   。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
   * 释放列表中给定的节点
   *
   * T = 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;
    }
  
    // 释放节点值
    if (list-> free ) list-> free (node->value);
  
    // 释放节点
    free (node);
  
    // 更新列表节点数目
    list->len --;
  }

迭代器 其实我对迭代器的概念非常陌生，因为我是纯c程序员，不会c++，这里直接跟着学了！ 。

Redis针对list结构实现了一个迭代器，用于对链表进行遍历 。

迭代器的结构定义如下:

?
1
2
3
4
5
6
7
8
9
10
/**
  * 链表迭代器
  */
typedef struct listIter {
   // 下一节点
   listNode *next;
 
   // 迭代方向
   int direction;
} listIter;

direction决定了迭代器是沿着next指针向后迭代，还是沿着prev指针向前迭代，这个值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量:

?
1
2
#define AL_START_HEAD 0
#define AL_START_TAIL 1

学习一下迭代器的api实现:

listIter *listGetIterator(list *list, int direction) 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
  * 创建列表list的一个迭代器，迭代方向由参数direction决定
  *
  * 每次对迭代器listNext(),迭代器返回列表的下一个节点
  *
  * T = O(1)
  */
listIter *listGetIterator(list *list, int direction)
{
   listIter *iter;
 
   iter = (listIter *) malloc ( sizeof (listIter));
   if (iter == NULL)
     return NULL;
 
   // 根据迭代器的方向，将迭代器的指针指向表头或者表尾
   if (direction == AL_START_HEAD) {
     iter->next = list->head;
   } else {
     iter->next = list->tail;
   }
 
   // 记录方向
   iter->direction = direction;
 
   return iter;
}

void listRewind(list *list, listIter *li) 。

?
1
2
3
4
5
6
7
8
9
10
/**
  * 将迭代器iter的迭代指针倒回list的表头
  *
  * T = O(1)
  */
void listRewind(list *list, listIter *li)
{
   li->next = list->head;
   li->direction = AL_START_HEAD;
}

void listRewindTail(list *list, listIter *li) 。

?
1
2
3
4
5
6
7
8
9
10
/**
  * 将迭代器iter的迭代指针倒回list的表尾
  *
  * T = O(1)
  */
void listRewindTail(list *list, listIter *li)
{
   li->next = list->tail;
   li->direction = AL_START_TAIL;
}

listNode *listNext(listIter *iter) 。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * 函数要么返回当前节点，要么返回NULL，因此，常见的用法是：
  * iter = listGetIterator(list, <direction>);
  * while ((node = listNext(iter)) != NULL) {
  *   doSomethingWith(listNodeValue(node));
  * }
  *
  * T = O(1)
  */
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;
}

最后此篇关于详解Redis中的双链表结构的文章就讲到这里了,如果你想了解更多关于详解Redis中的双链表结构的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

29 4 0
文章推荐： 利用Redis实现SQL伸缩的方法
文章推荐： Redis中的动态字符串学习教程
文章推荐： Redis sort 排序命令详解
文章推荐： mac下设置redis开机启动方法步骤
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com