欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Redis 链表实现

程序员文章站 2022-04-13 09:21:23
// 每个链表节点使用一个 ListNode 结构来表示typedef struct ListNode{ //前置节点 struct ListNode *prev; //后置节点 struct ListNode *next; //节点值 void *value; } ListNode; // typ ......
// 每个链表节点使用一个 listnode 结构来表示
typedef struct listnode{ //前置节点 struct listnode *prev; //后置节点 struct listnode *next; //节点值 void *value; } listnode;

  

// 
typedef struct list{
    //头节点
    struct listnode *head;
//尾节点 struct listnode *tail;
//链表所包含的节点数量 unsigned long length;

  //节点值复制函数
  void *(*dup) (void *ptr);
  //节点值释放函数
  void *(*free) (void *ptr);
  //节点值对比函数
  void (*match) (void *ptr, void *key);
} list;

  redis 链表实现的特性总结如下:

  1. 双端:链表节点带有 prev 和 next 指针,获取某个节点的前置节点和后置节点
  2. 无环:表头节点的prev指针和表尾节点的next指针指向null,因此对链表的访问以null终止,无环
  3. 带有表头和表尾指针:通过list 的tail 和 head 指针,获取链表的表头和表尾节点的复杂度为o(1)
  4. 带有链表长度计数器:通过list 的length属性,获取链表长度的时间复杂度为o(1)
  5. 多态:链表节点使用 void* 指针来保存节点值,并且可以通过list 结构的 dup 、free、match 三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

链表被用来实现redis 的各种功能,比如列表键、发布与订阅、慢查询、监视器等