链表简介
链表(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)