服务器之家：专注于服务器技术及软件下载分享
分类导航

Mysql|Sql Server|Oracle|Redis|MongoDB|PostgreSQL|Sqlite|DB2|mariadb|Access|数据库技术|

服务器之家 - 数据库 - Redis - 详解Redis中的双链表结构

详解Redis中的双链表结构

2019-10-26 19:55zinss26914 Redis

这篇文章主要介绍了Redis中的双链表结构,包括listNode结构的API,需要的朋友可以参考下

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如何使用Redis锁处理并发问题详解

      如何使用Redis锁处理并发问题详解

      这篇文章主要给大家介绍了关于如何使用Redis锁处理并发问题的相关资料，文中通过示例代码介绍的非常详细，对大家学习或者使用Redis具有一定的参考学习...

      haofly4522019-11-26
    • Redis关于Redis数据库入门详细介绍

      关于Redis数据库入门详细介绍

      大家好，本篇文章主要讲的是关于Redis数据库入门详细介绍，感兴趣的同学赶快来看一看吧，对你有帮助的话记得收藏一下，方便下次浏览...

      沃尔码6982022-01-24
    • RedisRedis 6.X Cluster 集群搭建

      Redis 6.X Cluster 集群搭建

      码哥带大家完成在 CentOS 7 中安装 Redis 6.x 教程。在学习 Redis Cluster 集群之前，我们需要先搭建一套集群环境。机器有限，实现目标是一台机器上搭建 6 个节...

      码哥字节15752021-04-07
    • RedisRedis Template实现分布式锁的实例代码

      Redis Template实现分布式锁的实例代码

      这篇文章主要介绍了Redis Template实现分布式锁,需要的朋友可以参考下 ...

      晴天小哥哥2592019-11-18
    • Redis详解三分钟快速搭建分布式高可用的Redis集群

      详解三分钟快速搭建分布式高可用的Redis集群

      这篇文章主要介绍了详解三分钟快速搭建分布式高可用的Redis集群，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，...

      万猫学社4502021-07-25
    • Redisredis缓存存储Session原理机制

      redis缓存存储Session原理机制

      这篇文章主要为大家介绍了redis缓存存储Session原理机制详解，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪...

      程序媛张小妍9252021-11-25
    • Redis《面试八股文》之 Redis十六卷

      《面试八股文》之 Redis十六卷

      redis 作为我们最常用的内存数据库，很多地方你都能够发现它的身影，比如说登录信息的存储，分布式锁的使用，其经常被我们当做缓存去使用。...

      moon聊技术8182021-07-26
    • RedisRedis集群的5种使用方式，各自优缺点分析

      Redis集群的5种使用方式，各自优缺点分析

      Redis 多副本，采用主从(replication)部署结构，相较于单副本而言最大的特点就是主从实例间数据实时同步，并且提供数据持久化和备份策略。...

      优知学院4082021-08-10
    最近更新
    编辑推荐
    阅读排行
    热门标签
    16384 　 Hashes 　 Sorted-Sets 　 服务器管理命令 　 管线 　 操作 　 主键失效 　 LRU 　 机制 　 应用场景 　 redis-py 　 禁用命令 　 危险命令 　 速率限制 　 Redis简介 　 用户积分 　 Mac OS 　 集群部署 　 Redis安装 　 Redis配置 　 远程方法调用 　 数据结构 　 Redis教程 　 redis-dump 　 还原数据 　 java脚本 　 计数 　 使用场景 　 计数器模式 　 数据大小 　
    © 2019-2023 服务器之家(www.zzvips.com) 版权所有关于我们联系我们版权申明网站地图