redis链表

文章目录
  1. 1. 每个链表和链表节点的实现
    1. 1.1. 链表节点结构
    2. 1.2. 链表结构
  2. 2. API

每个链表和链表节点的实现

链表节点结构

1
2
3
4
5
6
7
8
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
  	struct listNode *next;
    // 节点内容
    void *value;
} listNode;

链表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list {
    // 头节点
    listNode *head;
    // 尾节点
    listNode *tail;
    // 节点数量
    unsigned long len;
    // 节点复制函数
    void* (*dup) (void *ptr);
    // 节点释放函数
    void (*free) (void *ptr);
    // 节点对比函数
    int (*match) (void *prt, void *key);
} list;

dup、free、match成员用于实现多态链表所需的类型特定函数：

  • dup函数用于复制链表节点所保存的值。
  • free函数用于释放节点所保存的值。
  • match函数用户对比链表节点所保存的值和另一个输入值是否相等。

Redis的链表实现特性

  • 双端：链表节点带有prev和next指针，获取前置节点和后置节点的复杂度都是O(1)
  • 无环：头结点的prev和尾节点的next都指向NULL
  • 头节点和尾节点：获取表头和表尾复杂度都是O(1)
  • 多态：链表节点都用void*保存节点值，并且可以通过list结构的dup、free、match三个属性为节点设置类型特定函数，所以链表可以保存不同类型的值。

API

  • listSetDupMethod：将给定的函数设置为链表的节点复制函数，O(1)
  • listGetDupMethod：返回链表正在使用的节点复制函数，O(1)
  • listSetFreeMethod：将给定的函数设置成链表节点的释放函数，O(1)
  • listGetFreeMethod：反馈链表正在使用的节点释放函数，O(1)
  • listSetMatchMethod：将给定的函数设置成链表节点的对比函数，O(1)
  • listGetMatchMethod：反馈链表正在使用的节点对比函数，O(1)
  • listLength：返回链表长度，O(1)
  • listFirst：返回链表头结点，O(1)
  • listLast：返回链表尾节点，O(1)
  • listPrevNode：返回前置节点，O(1)
  • listNextNode：返回后置节点，O(1)
  • listNodeValue：返回节点保存的值，O(1)
  • listCreate：创建一个空链表，O(1)
  • listAddNodeHead：添加节点到链表头，O(1)
  • listAddNodeTail：添加节点到链表尾，O(1)
  • listInsertNode：将新节点添加到给定节点之前或者之后，O(1)
  • listSearchKey：反会链表中包含给定值的节点，O(N)
  • listIndex：返回链表中给定索引的节点，O(N)
  • listDelNode：删除给定节点，O(N)
  • listRotate：弹出尾节点，并弹出，插入到表头，O(1)
  • listDup：复制一个给链表，O(N)
  • listRelease：释放给定链表以及链表中所有节点，O(N)