文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

从 Redis 源码了解双向链表的设计与实现

2024-11-28 15:25

关注

详解redis中链表的设计与实现

链表底层结构的设计

链表是由无数个节点也就是我们常说的listNode构成,每个节点通过前驱和后继节点指针维护其前驱和后继节点信息:

对应的我们也给出redis中链表节点listNode 的源码,它位于adlist.h的定义中,可以看到它通过prev指针和next指针分别管理当前节点的前驱节点和后继节点,然后通过value指针维护当前节点的值,由这一个个节点的串联构成双向链表:

typedef struct listNode {
    //指向前驱节点
    struct listNode *prev;
    //指向后继节点
    struct listNode *next;
    //维护当前节点的值的指针
    void *value;
} listNode;

双向链表需要一个头指针和尾指针管理首尾节点,从而实现后续灵活的头插法和尾插法的操作,所以在设计双向链表的时候,我们就需要一个head和tail指针管理链表的首尾节点。同时,为了实现O(1)级别的长度计算,在元素添加或者删除操作的时候,我们还需要一个len字段记录当前链表的长度:

而redis中双向链表的结构体list 也是同理:

typedef struct list {
    //头节点指针
    listNode *head;
    //尾节点指针
    listNode *tail;
    //......
    //链表长度
    unsigned long len;
} list;

了解了基本的数据结构,我们再来说说链表的初始化,redis中的双向链表会为其分配一块内存空间,然后将头尾节点的指针设置为空,长度初始化为0:

对应的我们给出双向链表初始化的源码即位于adlist.c的listCreate函数,它完成空间分配和指针、长度初始化之后返回这个链表的指针:

list *listCreate(void)
{
    //为list结构体分配内存空间
    struct list *list;

    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //头尾指针初始化设置为空    
    list->head = list->tail = NULL;
    //链表长度设置为0
    list->len = 0;
   //......
    return list;
}

节点头插法的实现

通过上文我们了解了链表的基本数据结构,接下来我们就来聊聊链表的第一个操作,也就是头插法,这个操作就是将最新的节点插入的链表的首部,我们以初次插入为例,此时链表全空,双向链表初始化节点之后,就会让链表的头尾指针指向这个node,然后长度自增为1:

若非第一次操作,则初始化一个新节点之后,让这个节点指向原有的头节点,最后让原有的头节点作为新节点的后继即可:

图片图片

对此我们也给出头插法的源码,可以看到它会传入当前需要操作的链表和新节点的value指针完成节点生成和头插工序,对应的源码操作细节和上述讲解大体一致,读者可自行参阅:

list *listAddNodeHead(list *list, void *value)
{
    //初始化node节点内存空间
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //value指针指向传入的值    
    node->value = value;
    //如果链表长度为0,则让首尾节点指向这个node,然后node前驱和后继节点为空
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //节点的前驱指向空,后继节点指向原有的头节点,完成后再让原有的头节点作为新节点的后继节点
        //最后head指针指向当前node
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    //维护一下链表的长度+1
    list->len++;
    return list;
}

尾插法的实现

尾插法就是将最新节点插入到链表末尾,初次插入和头插法一致,即头指针head和尾指针tail都指向最新node节点,这里就不做赘述。 我们重点说说常规操作的尾插法,双向链表在进行尾插法时步骤如下:

尾插法的函数为listAddNodeTail,入参为要进行操作的list指针和value值,操作步骤的上图表述基本一致,读者可结合注释自行参阅:

list *listAddNodeTail(list *list, void *value)
{
    
    listNode *node;
    //分配node内存空间
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //node的value指针指向value    
    node->value = value;
    //如果长度为0,则首尾指针指向这个node
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //新节点的前驱节点指向尾节点,然后让原有尾节点指向新节点,最后让tail指针指向新节点
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    //长度信息维护一下
    list->len++;
    return list;
}

指定节点插入

该函数会传入修改前驱后继关系的节点,如果希望将新节点n插入到旧节点后面,则会让新节点n的前驱指向原有节点,后继节点指向原有节点的后继,最后让新节点的前驱后继节点指向插入的新节点n:

同理插入前面也很节点后添加差不多,这里就不多赘述,对此我们给出listInsertNode的源码,可以看到它传入需要进行操作的list指针,再传入需要维护新关系的old_node指针和需要插入的value,将value封装为node之后,如果after为1则执行上述所说的old_node后节点插入操作:

对应的源码如下,读者可参考笔者上述图解并结合源码注释了解整个插入过程:

list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    listNode *node;
    //节点初始化并设置value
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    //如果after为1则将新节点插入到old_node后面
    if (after) {
        //node前驱指向old_node,node指向old_node的后继
        node->prev = old_node;
        node->next = old_node->next;
        //如果old_node是尾节点,则让tail指向新插入的node
        if (list->tail == old_node) {
            list->tail = node;
        }
    } else {
        //将新节点插入到old_node前面
        node->next = old_node;
        node->prev = old_node->prev;
        //如果old_node是头节点,则修改head指向,让其指向新节点
        if (list->head == old_node) {
            list->head = node;
        }
    }
    //将node原有的前驱后继节点指向当前node维护的前驱和后继节点
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    if (node->next != NULL) {
        node->next->prev = node;
    }
    //维护一下长度
    list->len++;
    return list;
}

获取指定位置的元素

双向链表支持基于索引查找指定位置的元素,操作时间复杂度为O(n),我们以从头查找为例,如果希望查找索引2的元素,也就是第3个元素,它就会从head开始跳越2条,由此走到第3个节点的位置并返回这个节点的指针:

对应我们给出listIndex的源码,可以看到如果传入的index为负数,则说明调用者要从后往前找,假设我们传入-2也就是要找到倒数第2个元素,最终取正计算得到1,这也就意味着我们只需从尾节点跳1下就能得到倒数第2个元素,而index若为正数则是顺序查找,原理如上图解析,这里就不多赘述了,读者可自行查阅listIndex函数及其源码:

listNode *listIndex(list *list, long index) {
    listNode *n;
    //如果小于0,说明从后往前照
    if (index < 0) {
        //将负数转为正数,例如传入-2,也就找倒数第2个元素,转为正为1,也就是往前1跳,返回这个node
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        //说明从前往后照,跳n跳即可得到对应元素
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

删除指定位置的元素

最后一个就是链表删除操作了,操作比较简单,让被删除节点的前驱和后继节点构成关联关系,然后释放当前被删节点,然后减小一下长度即可:

对应的源码如下,读者可自行参阅学习:

void listDelNode(list *list, listNode *node)
{
    //如果node前驱有节点,则让这个节点指向被删除节点的后继
    //反之说明这个节点是头节点,则让head指向这个后继节点
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    //如果这个节点有后继节点,则让这个后继的prev指向被删节点的前驱
    //反之说明被删的是尾节点,则让tail指针指向被删节点的后继
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    //释放被删除节点的内存空间,并减小链表长度    
    if (list->free) list->free(node->value);
    zfree(node);
    list->len--;
}

小结

自此我们将redis底层的双向链表的设计与实现的源码进行的深入分析,从中了解到redis双向链表数据结构设计和节点操作的实现细节,希望对你有所帮助。

来源:写代码的SharkChili内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯