首页 / REDIS / redis 数据结构基础 （二） 链表

redis 数据结构基础 （二） 链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了redis 数据结构基础 （二） 链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2130字，纯文字阅读大概需要4分钟。

内容图文

redis中的链表恐怕是最简单的数据结构了，redis链表中总共有3个数据结构：

listNode:

            1 typedef struct listNode {
2struct listNode *prev; //前向节点指针
3struct listNode *next; //后续节点指针
4void *value;  //存储的值，采取void*类型，万能类型，但是少了类型信息
5 } listNode;

从这个上面可以看出，redis的链表是双向链表

list：

typedef struct list {
    listNode *head; //头结点指针
    listNode *tail; //尾节点指针
    void *(*dup)(void *ptr); //复制节点数据的函数指针
    void (*free)(void *ptr); //释放节点数据的函数指针
    int (*match)(void *ptr, void *key); //这个类似于C++中的operator==操作，即判定节点的数据内容和key指向的内容是否匹配
    unsigned long len; //节点的个数
} list;

值得研究一下的是，redis为链表实现了迭代器，迭代器是本文的第三个数据结构：

            1 typedef struct listIter {
2     listNode *next; //迭代器指向的节点
3int direction;  //迭代器前进的方向 表头->表尾 or 表尾->表头？
4 } listIter;

迭代器本身就是一种设计模式，可见C语言一样可以利用各种设计模式

list的操作都非常简单，本文不再分析，简单描述如下： 1 list *listCreate(void); //创建链表 2void listRelease(list *list); //释放链 3void listEmpty(list *list); //清空链表中的数据

                 4 list *listAddNodeHead(list *list, void *value); //表头添加节点 O(1)
 5 list *listAddNodeTail(list *list, void *value); //表尾添加节点 O(1)
 6 list *listInsertNode(list *list, listNode *old_node, void *value, int after); //插入节点，after参数表明是在该节点前还是该节点后插入该节点 O(1) 
 7void listDelNode(list *list, listNode *node); //删除某节点 O(1)
 8 listIter *listGetIterator(list *list, int direction); //得到链表的迭代器， direction参数表示这是个前向迭代器还是个逆向迭代器
 9 listNode *listNext(listIter *iter); //迭代器指向下一个节点 O(1)
10void listReleaseIterator(listIter *iter); //释放迭代器
11 list *listDup(list *orig); //复制链表 O(n)
12 listNode *listSearchKey(list *list, void *key); //在链表中查找匹配key的节点， 如果match函数不为空，则调用match函数比较，否则直接判定指针的地址的方式来判定 O(n)
13 listNode *listIndex(list *list, long index); //得到第index个节点，注意index可以为负数，-1代表最后一个，-2代表倒数第二个 O(n)
14void listRewind(list *list, listIter *li); //重置迭代器到表头，且未前向迭代器 O(1)
15void listRewindTail(list *list, listIter *li); //重置迭代器到表尾，且未前向迭代器 O(1)
16 void listRotate(list *list);  //将表尾的节点作为新的表头 O(1)
17void listJoin(list *l, list *o); //将o链表中的内容增加到o中去， 操作执行完成后，o中的内容被清空 O(n
o 
)

redis链表的总结：

1、redis中的链表中直接存储了头节点和尾节点，不是循环链表，到表头和表尾都是O(1)时间

2、添加、删除、插入都是O(1)的时间

3、所有的迭代器操作都是O(1)时间

4、获取链表中数据个数的时间也是O(1)

5、redis结构中设置了dup,free,match三个函数指针，使得对数据的操作和链表操作解耦，其实就是实现了C语言下的多态

原文：http://www.cnblogs.com/crane2000/p/7479759.html

内容总结

以上是互联网集市为您收集整理的redis 数据结构基础 （二） 链表全部内容，希望文章能够帮你解决redis 数据结构基础 （二） 链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1297501.html

来源：【匿名】