详解Redis中的双链表结构

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

typedef struct listNode {
  struct listNode *prev; //前向节点
  struct listNode *next; //后向节点
  void *value;       //该节点的值
} listNode;

2.双向链表结构

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.双向链表遍历器

typedef struct listIter {
  listNode *next;  //下一个节点
  int direction;
} listIter;

 方向定义

  #define AL_START_HEAD 0 //向前查找
  #define AL_START_TAIL 1  //向后查找

4.宏定义函数

#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.定义函数

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)

  /**
   * 创建一个新列表
   *
   * 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)

  /**
   * 释放整个列表
   *
   * 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)

  /**
   * 新建一个包含给定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)

  /**
   * 新建一个包含给定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)

  /**
   * 创建一个包含值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)

  

 /**
   * 释放列表中给定的节点
   *
   * 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结构实现了一个迭代器,用于对链表进行遍历

迭代器的结构定义如下:

  /**
   * 链表迭代器
   */
  typedef struct listIter {
    // 下一节点
    listNode *next; 

    // 迭代方向
    int direction;
  } listIter;

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

  #define AL_START_HEAD 0
  #define AL_START_TAIL 1

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

listIter *listGetIterator(list *list, int direction)

  /**
   * 创建列表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)

  /**
   * 将迭代器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)

  /**
   * 将迭代器iter的迭代指针倒回list的表尾
   *
   * T = O(1)
   */
  void listRewindTail(list *list, listIter *li)
  {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
  }


listNode *listNext(listIter *iter)

  /**
   * 函数要么返回当前节点,要么返回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;
  }
(0)

相关推荐

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • 简单介绍线性表以及如何实现双链表

    线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列. 一.数组 数组有上界和下界,数组的元素在上下界内是连续的. 存储10,20,30,40,50的数组的示意图如下: 数组的特点:数据是连续的:随机访问速度快. 数组中稍微复杂一点的是多维数组和动态数组.对于C语言而言,多维数组本质上也是通过一维数组实现的.至于动态数组,是指数组的容量能动态增长的数组:对于C语言而言,若要提供动态数组,需要手动实现:而对于C++而言,STL提供了Vector:对于Java而言,Colle

  • C/C++ 双链表之逆序的实例详解

    C/C++ 双链表之逆序的实例详解 一.结点结构 双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点 本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve

  • C数据结构之双链表详细示例分析

    复制代码 代码如下: typedef struct node{      struct node *prior;      struct node *next;       int num;}NODE;/*******双向链表的初始化********/NODE *Init_link(void){     int i;     NODE *phead,*pb,*pi;     phead = (NODE *)malloc(sizeof(NODE));     printf("please inpu

  • PHP 双链表(SplDoublyLinkedList)简介和使用实例

    双链表是一种重要的线性存储结构,对于双链表中的每个节点,不仅仅存储自己的信息,还要保存前驱和后继节点的地址. PHP SPL中的SplDoublyLinkedList类提供了对双链表的操作. SplDoublyLinkedList类摘要如下: SplDoublyLinkedList implements Iterator , ArrayAccess , Countable { public __construct ( void ) public void add ( mixed $index ,

  • Node.js环境下JavaScript实现单链表与双链表结构

    单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n

  • C++ 双链表的基本操作(详解)

    1.概念 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • 详解Redis中的双链表结构

    Redis中双链表实现的基本结构: 1.节点结构 typedef struct listNode { struct listNode *prev; //前向节点 struct listNode *next; //后向节点 void *value; //该节点的值 } listNode; 2.双向链表结构 typedef struct list { listNode *head; //头节点 listNode *tail; //尾节点 void *(*dup)(void *ptr); //复制函数

  • 详解Redis中的List类型

    本系列将和大家分享Redis分布式缓存,本章主要简单介绍下Redis中的List类型,以及如何使用Redis解决博客数据分页.生产者消费者模型和发布订阅等问题. Redis List的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销,Redis内部的很多实现,包括发送缓冲队列等也都是用这个数据结构. List类型主要用于队列和栈,先进先出,后进先出等. 存储形式:key--LinkList<value> 首先先给大家Show一波Redis中与List类型相

  • 详解redis中的锁以及使用场景

    分布式锁 什么是分布式锁? 分布式锁是控制分布式系统之间同步访问共享资源的一种方式. 为什么要使用分布式锁? ​ 为了保证共享资源的数据一致性. 什么场景下使用分布式锁? ​ 数据重要且要保证一致性 如何实现分布式锁? 主要介绍使用redis来实现分布式锁 redis事务 redis事务介绍: ​ 1.redis事务可以一次执行多个命令,本质是一组命令的集合. ​ 2.一个事务中的所有命令都会序列化,按顺序串行化的执行而不会被其他命令插入 ​ **作用:**一个队列中,一次性.顺序性.排他性的执

  • 详解Redis中key的命名规范和值的命名规范

    数据库中得热点数据key命名惯例 表名:主键名:主键值:字段名 例如 user:id:0001:name 例如 user:id:0002:name 例如 order:id:s2002:price 上面的key对应的值则可以是 存放的方式 key value 优点 单独的key:value形式 order:id:s2002:price 2000 方便简单的操作,例如incr自增或自减 json格式 user:id:0001 {id:0001,name:"张三"} 方便一次性存和取数据,但

  • 一文详解Redis中的持久化

    目录 1. 前言 2. RDB 2.1 手动触发 2.2 自动触发 3. bgsave大致流程 4. RDB持久化方式的优缺点 5. AOF 6. AOF的使用方式 7. AOF流程剖析 7.1 命令写入 7.2 文件同步 7.3 重写机制 7.4 重启加载 8. 问题定位与优化 8.1 关于fork操作 8.2 关于子进程开销 8.3 关于AOF追加阻塞 1. 前言 为什么要进行持久化?:持久化功能有效地避免因进程退出造成的数据丢失问题,当下次重启时利用之前持久化的文件即可实现数据恢复. 持久

  • 详解Redis中Lua脚本的应用和实践

    引言 前段时间组内有个投票的产品,上线前考虑欠缺,导致被刷票严重.后来,通过研究,发现可以通过 redis lua 脚本实现限流,这里将 redis lua 脚本相关的知识分享出来,讲的不到位的地方还望斧正. redis lua 脚本相关命令 这一小节的内容是基本命令,可粗略阅读后跳过,等使用的时候再回来查询 redis 自 2.6.0 加入了 lua 脚本相关的命令,EVAL.EVALSHA.SCRIPT EXISTS.SCRIPT FLUSH.SCRIPT KILL.SCRIPT LOAD,

  • 详解C++中的双冒号 ::

    C++中的双冒号 ::第一种,类作用域,用来标明类的变量.函数 Human::setName(char* name); 第二种,命名空间作用域,用来注明所使用的类.函数属于哪一个命名空间的 std::cout << "Hello World" << std::endl; 第三种,全局作用域,用来区分局部.全局的.最容易被忽视的一种,很多时候写了一个全局函数或者想要调用一个全局函数,却发现IDE或者Editor找不到该函数,原因是因为局部函数与想要调用的全局函数名

  • 详解JavaScript (!!) 中的双感叹号是干什么用的

    目录 JavaScript (!!) 中的双感叹号是干什么用的? 真与真 那么为什么要双感叹号呢? JavaScript (!!) 中的双感叹号是干什么用的? 如果您曾在某人的 JavaScript 代码中注意到双感叹号 (!!),您可能会好奇它的用途和作用.这很简单:这是一种将变量转换为布尔值(真或假)的捷径.让我解释. typeof JavaScript!= '静态' JavaScript 不是静态语言,而是动态语言.这意味着变量可以引用或保存任何类型的值,此外,该类型可以随时更改.无论您喜

  • 详解JavaScript中Hash Map映射结构的实现

    Hash Map通常在JavaScript中作为一个简单的来存储键值对的地方.然而,Object并不是一个真正的哈希映射,如果使用不当可能会带来潜在的问题.而且JavaScript可能不提供本地哈希映射(至少不是跨浏览器兼容的),有一个更好的声明对象属性的方法. Hash Map的简单实现: var hashMap = { Set : function(key,value){this[key] = value}, Get : function(key){return this[key]}, Co

  • 详解mysql 中的锁结构

    Mysql 支持3中锁结构 表级锁,开销小,加锁快,不会出现死锁,锁定的粒度大,冲突概率高,并发度最低 行级锁,开销小,加锁慢,会出现死锁,锁定粒度小,冲突概率最低,并发度最高 页面锁,开销和加锁处于表锁和行锁之间,会出现死锁,锁粒度基于表和行之间,并发一般 InnoDB锁问题 InnoDB与MyISAM的最大不同有两点:一是支持事务(TRANSACTION):二是采用了行级锁.  行级锁和表级锁本来就有许多不同之处,另外,事务的引入也带来了一些新问题. InnoDB的行锁模式及加锁方法 Inn

随机推荐