链表简介
链表(linkedlist)作为一种非常常见的数据结构,List类型就使用了链表作为底层实现之一。它不仅在Redis其它数据结构中使用的非常广泛,而且许多高级语言都内置了这种数据结构,比如:Java中的LinkedList
链表分为 单向链表、双向链表、循环链表 等。链表是一种逻辑上连续,物理上分散的数据结构,比如双向链表中的每一个节点它不仅只保存的当前节点的数据,还用两个属性保存了当前节点的上一个节点(pre)和下一个节点(next)的引用地址,分别叫做节点的前驱和后置。有了这两个属性,就算在链表中的节点在内存块中不是连续的,也可以通过next引用向后遍历下一个节点,当next为NULL时,就知道这是最后一个节点。
链表适合存储大量数据节点,因为内存在系统中会有多个进程在使用,内存分配和回收就会产生大量的内存碎片,当一个非常大的数据结构需要被分配内存的时候,将这些内存碎片重新整理的话是很浪费时间的,竟然如此,为什么不在这些内存碎片的基础上继续使用它呢?链表结构就是为了这种场景应运而生的,如果是单项链表的话,每个节点只要多用一个属性去放它下一个节点的内存地址值就行了,内存地址的大小一般是4byte。
但也意味着每个节点都需要需要多浪费4byte去存储这些和实际数据没什么直接关系的地址值本省也是一种浪费,当节点多的时候,这种浪费更严重。
链表这种设计思想在很多地方都有用到,就是 空间换时间 的一种方式,比如重写一个数组结构,在里面多加个len属性,用来存储数组的长度。原来获取数组的长度需要遍历数组起始位置到结束位置的每个节点,时间复杂度是O(n),现在只需要调用一下len属性就好了,时间复杂度为O(1)。
所以链表也不是万能药,只有最适合的,没有最好的。
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)