第 3 章 链表

listNode

typedef struct listNode{
  struct listNode *prev;
  struct listNode *next;
  void *value;
}listNode;

void 指针可以指向任意类型的数据,如:

void main(){
  int num = 100;
  void *p = #
  printf("%d",*(int *)p);
}

可见,Redis 中的链接采用了双端链表。

list

typedef 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).
  • 无环
  • 多态:链表节点使用 void* 指针来保存节点值,并且可以通过 list 结构的 dupfreematch 三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。
    链表被广泛用于实现 Redis 的各种功能,比如列表键、发布与订阅、慢查询、监视器等。
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 实现 Redis 的列表类型 双端链表还是 Redis 列表类型的底层实现之一, 当对列表类型的键进行操作 —— ...
    待汝豪杰只是凡夫阅读 3,619评论 0 0
  • 前言   托更了一天,因为新型肺炎疫情的影响,公司昨天开工了。长时间在家里待着,突然开工了。比较不适应,觉得比较疲...
    于情于你阅读 1,594评论 0 1
  • redis使用两种数据结构保存链表,分别是ziplist与linkedlist,内存占用及常用操作效率各不相同。本...
    但莫阅读 4,902评论 0 1
  • 链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活的调整链表的长度。链表键的底层实...
    猪大金阅读 1,657评论 0 0
  • 链表提供了高效的节点重排能力,以及顺序性的节点访问方式,可以通过增删节点来灵活地调整链表的长度。 链表在Redis...
    亮亮_ff3d阅读 1,265评论 0 0

友情链接更多精彩内容