Redis内部数据结构详解之双向链表（linkedlist）

php中文网

发布： 2016-06-07 15:22:38

原创

1746人浏览过

一、双向链表简介双向链表作为一种常见的数据结构，在严蔚敏数据结构书里有详细的讲解，双向链表的每个数据节点都有两个指针，分别指向后继与前驱节点，因此从双向链表中的任意一个节点开始都可以很方便地访问其前驱与后继节点。二、Redis中双向链表数据结

一、双向链表简介

双向链表作为一种常见的数据结构，在严蔚敏数据结构书里有详细的讲解，双向链表的每个数据节点都有两个指针，分别指向后继与前驱节点，因此从双向链表中的任意一个节点开始都可以很方便地访问其前驱与后继节点。

二、Redis中双向链表数据结构以及相关宏定义

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

typedef struct listIter {//链表迭代器
    listNode *next;
    int direction;//遍历方向
} listIter;

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;

登录后复制

宏名称	作用
listLength	获取链表的长度值
listFirst	获取链表的首指针
listLast	获取链表的尾指针
listPrevNode	获取当前节点的前驱节点指针
listNextNode	获取当前节点的后继节点指针
listNodeValue	获取当前节点所存储的值
listSetDupMethod	设置链表节点value的复制函数
listSetFreeMethod	设置链表节点value的释放内存函数
listSetMatchMethod	设置链表节点value的比较函数
listGetDupMethod	获取链表节点value的复制函数
listGetFree	获取链表节点value的释放内存函数
listGetMatchMethod	获取链表节点value的比较函数

三、Redis中双向链表API介绍

名称	作用	复杂度
listCreate	创建一个新双向链表	O(1) 开拍用AI制作口播视频 289 查看详情
listRelease	释放一个双向链表以及包含的节点内存	O(N)
listAddNodeHead	将一个节点添加到链表的表头	O(1)
listAddNodeTail	将一个节点添加到链表的表尾	O(1)
listInsertNode	将一个节点添加到给定节点的之后或之前	O(1)
listDelNode	删除给定的节点	O(1)
listGetIterator	生成双向链表的迭代器	O(1)
listReleaseIterator	释放双向链表的迭代器	O(1)
listNext	通过迭代器获取下一个节点	O(1)
listDup	创建给定链表的副本	O(N)
listSearchKey	查找与给定key相同值的节点	O(N)
listIndex	根据给定的索引值，返回相应的节点	O(N)
listRewind	重新初始化迭代器，迭代方向从头至尾	O(1)
listRewindTail	重新初始化迭代器，迭代方向从尾至头	O(1)
listRotate	取出链表尾节点并插入到头部	O(1)