Fork me on GitHub

二、Redis-链表

发表于

链表和链表节点

链表节点

每个链表节点使用listNode结构来表示

1
2
3
4
5
6
7
8
9
10
struct listNode{
    //前置节点
    struct listNode *prev;
    
    //后置节点
    struct listNode *next;
    
    //节点的值
    void *value;
}listNode

通过这个listNode我们可以构造出一个双端链表，虽然使用多个listNode可以组成链表，但是如果我们再使用一个结构体整合起来，就会方便很多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct list{
    //表头节点
    listNode *head;
    
    //表尾节点
    listNode *tail;
    
    //链表所包含的节点数量
    unsigned long len;
    
    //节点值复制函数
    void *(*dup)(void *ptr);
    
    //节点值释放函数
    void (*free)(void *ptr);
    
    //节点值对比函数
    int (*match)(void *ptr,void *key);
}

通过上面定义这个结构体将链表持有，通过这个结构，我们可以快速知道当前链表的头、尾节点、以及链表长度，同时也提供了链表节点的三个操作函数。

Redis链表实现的特性

  • 双端：获取某个节点的前置节点和后置节点的时间复杂度为O(1)
  • 无环：表头的前置节点和表尾的后置节点都为NULL
  • 带表头指针和表尾指针：通过list结构的head和tail，获取链表头节点和尾节点的时间复杂度为O(1)
  • 带链表长度计数器：通过list结构的len属性，获取链表中节点数量的复杂度为O(1)
  • 多态：链表节点使用void* 指针来保存节点的值，所以链表可以保存不同类型的值