专栏首页原创分享redis0.1源码解析之链表

redis0.1源码解析之链表

分析代码之前先看看链表的数据结构。

1 新建一个链表

// 新建一个链表头结点
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;
    // 释放节点value域的函数
    list->free = NULL;
    // 匹配节点的函数
    list->match = NULL;
    return list;
}

2 释放一个链表

// 释放一个链表
void listRelease(list *list)
{
    unsigned int len;
    listNode *current, *next;
    // 第一个节点
    current = list->head;
    // 链表中的节点数
    len = list->len;
    while(len--) {
        next = current->next;
        // 定义了free函数,则执行
        if (list->free) list->free(current->value);
        // 释放节点内存
        zfree(current);
        current = next;
    }
    // 释放链表内存
    zfree(list);
}

3 插入一个节点(支持头插和尾插)

// 给链表新增一个节点,头插法
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
    // 分配一个新的listNode节点
    if ((node = zmalloc(sizeof(*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)
{
    listNode *node;

    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    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;
}

4 删除节点

// 删除节点node
void listDelNode(list *list, listNode *node)
{
    // 有前指针说明不是第一个节点,则前节点的next指针指向node的第一个节点
    if (node->prev)
        node->prev->next = node->next;
    else
        // 前指针为空说明是第一个节点,更新头节点头指针的指向,指向node的下一个节点
        list->head = node->next;
    // next非空说明不是最后一个节点,更新node下一个节点的前指针为node的前一个节点
    if (node->next)
        node->next->prev = node->prev;
    else
        // 删除的是最后一个节点,则更新头节点尾指针的指向
        list->tail = node->prev;
    // 定义了free函数
    if (list->free) list->free(node->value);
    // 释放节点的内存
    zfree(node);
    // 节点数减一
    list->len--;
}

5 查找

查找有两种,第一是根据索引查找,第二种是根据键查找。

// 返回链表的第index个字节
listNode *listIndex(list *list, int index) {
    listNode *n;
    // index小于0,则-1是最后一个节点
    if (index < 0) {
        /*
                    |
            ---------------------
                    |
         -2   -1    0   1   2
        假设index=-2,-index则为2,-index-1则为1。即向前走1个节点,
        因为初始化时n指向了尾节点,所以这时候返回的是倒数第二个节点
        */  
        index = (-index)-1;
        n = list->tail;
        while(index-- && n) n = n->prev;
    } else {
        // 索引为0对应的节点(第一个节点),如果只有2个节点,index大于节点数,则返回最后一个节点
        n = list->head;
        while(index-- && n) n = n->next;
    }
    return n;
}

通过键查找

// 遍历链表,查找key对应的节点
listNode *listSearchKey(list *list, void *key)
{
    listIter *iter;
    listNode *node;

    iter = listGetIterator(list, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        // 定义了match函数
        if (list->match) {
            if (list->match(node->value, key)) {
                listReleaseIterator(iter);
                return node;
            }
        } else {
            // 默认比较内存地址
            if (key == node->value) {
                listReleaseIterator(iter);
                return node;
            }
        }
    }
    listReleaseIterator(iter);
    return NULL;
}

6 复制一个链表

// 复制一个链表
list *listDup(list *orig)
{
    list *copy;
    listIter *iter;
    listNode *node;
    // 申请一个新的链表头节点
    if ((copy = listCreate()) == NULL)
        return NULL;
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    // 申请一个链表迭代器
    iter = listGetIterator(orig, AL_START_HEAD);
    while((node = listNext(iter)) != NULL) {
        void *value;
        // 定义了复制函数,比如深度复制
        if (copy->dup) {
            value = copy->dup(node->value);
            // 复制出错,释放刚才申请的内存
            if (value == NULL) {
                listRelease(copy);
                listReleaseIterator(iter);
                return NULL;
            }
        } else
            // 默认浅复制
            value = node->value;
        // 插入新的链表
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            listReleaseIterator(iter);
            return NULL;
        }
    }
    // 用完了,释放迭代器
    listReleaseIterator(iter);
    return copy;
}

7 迭代链表 首先申请一个迭代器。

// 申请一个链表迭代器
listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;

    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    // 从头还是从尾开始遍历
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

然后利用这个迭代器就可以进行迭代链表了

// 一次迭代,返回链表中的一个节点
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;
}

本文分享自微信公众号 - 编程杂技(theanarkh),作者:theanarkh

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • js实现avl树的构建和查找

    theanarkh
  • js的arguments分析

    执行结果中可以发现,argument和函数的参数列表中的变量是有关联的,这里假设函数的实参和形参个数是一样的。这个结果的背后到底是怎么回事,看了一下es5的ar...

    theanarkh
  • 深入浅出文件系统原理之文件读取(基于linux0.11)

    这篇文章讲的是文件系统树,我们知道,文件系统的数据是存在硬盘里的,这里来看一下,这些数据是怎么组织成一棵树,又是怎么进行遍历的。下面就是这棵树。

    theanarkh
  • TencentOS-tiny中双向循环链表的实现及使用

    双向链表也是链表的一种,区别在于每个节点除了后继指针外,还有一个前驱指针,双向链表的节点长下面这样:

    Mculover666
  • Redis源码解析——双向链表

            相对于之前介绍的字典和SDS字符串库,Redis的双向链表库则是非常标准的、教科书般简单的库。但是作为Redis源码的一部分,我决定还是要讲一讲...

    方亮
  • zip函数-求最长公共前缀

    用python解决问题的方法有很多:函数法、暴力法以及一些常见的算法等等,而且python 的很多基础题用函数来解决是非常快捷的。熟练掌握函数的方法和技巧能够更...

    小小科
  • Python|zip函数-求最长公共前缀

    用python解决问题的方法有很多:函数法、暴力法以及一些常见的算法等等,而且python 的很多基础题用函数来解决是非常快捷的。熟练掌握函数的方法和技巧能够更...

    算法与编程之美
  • ArrayList在foreach删除倒数第二个元素不抛并发修改异常的问题

    平时我们使用ArrayList比较多,但是我们是否知道ArrayList在进行foreach的时候不能直接通过list的add或者move方法进行删除呢,

    小勇DW3
  • 5.迭代器和生成器

    zhang_derek
  • 0423作业(函数)

    py3study

扫码关注云+社区

领取腾讯云代金券