Redis 链表

链表简介

链表(linkedlist)作为一种非常常见的数据结构,List类型就使用了链表作为底层实现之一。它不仅在Redis其它数据结构中使用的非常广泛,而且许多高级语言都内置了这种数据结构,比如:Java中的LinkedList

链表分为 单向链表、双向链表、循环链表 等。链表是一种逻辑上连续,物理上分散的数据结构,比如双向链表中的每一个节点它不仅只保存的当前节点的数据,还用两个属性保存了当前节点的上一个节点(pre)和下一个节点(next)的引用地址,分别叫做节点的前驱和后置。有了这两个属性,就算在链表中的节点在内存块中不是连续的,也可以通过next引用向后遍历下一个节点,当next为NULL时,就知道这是最后一个节点。

链表适合存储大量数据节点,因为内存在系统中会有多个进程在使用,内存分配和回收就会产生大量的内存碎片,当一个非常大的数据结构需要被分配内存的时候,将这些内存碎片重新整理的话是很浪费时间的,竟然如此,为什么不在这些内存碎片的基础上继续使用它呢?链表结构就是为了这种场景应运而生的,如果是单项链表的话,每个节点只要多用一个属性去放它下一个节点的内存地址值就行了,内存地址的大小一般是4byte。

但也意味着每个节点都需要需要多浪费4byte去存储这些和实际数据没什么直接关系的地址值本省也是一种浪费,当节点多的时候,这种浪费更严重。

链表这种设计思想在很多地方都有用到,就是 空间换时间 的一种方式,比如重写一个数组结构,在里面多加个len属性,用来存储数组的长度。原来获取数组的长度需要遍历数组起始位置到结束位置的每个节点,时间复杂度是O(n),现在只需要调用一下len属性就好了,时间复杂度为O(1)。

所以链表也不是万能药,只有最适合的,没有最好的。
linkedlist_1.jpg

Redis链表结构实现

链表节点:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
  • prev:前驱
  • next:后置
  • value:数据

链表:

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;
  • head:头节点
  • tail:尾节点
  • len:链表长度
  • dup:复制链表节点所保存的值
  • free:释放链表节点所保存的值
  • match:对比链表节点所保存的值和另一个输入值是否相等

Redis中的链表结构是双端双向无环链表
通过head和tail属性程序获取链表的表头节点和表尾节点的复杂度为 O(1)
通过len属性获取链表中节点数量的复杂度为 O(1)

# Redis 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×