redis-list实现

Redis 数据结构---链表

Redis的list底层实现使用的不是数组而是链表的数据结构叫listnode 是一个双向链表

ListNode{

Struct listNode *prev //前置节点

Struct listNode *next //后置节点

Void *value

}

而redis的list正是使用listNode实现

Typedef struct list{

listNode *head // 头结点

listNode *tail // 尾节点

unsigned long len //list长度

void *(*dup) (void *ptr) //指针指向节点复制函数

void *(*free) (void *ptr) //指针，指向节点释放函数

void *(*match) (void *ptr,void *key) // 指针，指向节点值比对函数

}

如果确定了list中的某一节点，查询其前后置节点可以直接查询pre next，时间复杂度仅为O(1)

List中head.prev=null, tail.next=null 前后为空，简称无环结构

List有api可直接获取head tail listFist和 listLast

List长度函数时间复杂度为O(1),因为有len属性

因为dup free match三个属性可为list设置不同类型的特定函数，所以链表可以用以存储不同的数据接口，只要三属性对应的函数指针正确

巴特西