一、3.0以前的列表实现

链表是由许多内存碎片组成，而压缩列表是为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构，这个和各种语言的数组类似。当redis的列表包含了比较多的元素时，或者包含的元素都是比较长的字符串时，会使用链表来存储数据结构；而当包含了少量的列表项，并且每个元素要么是小整数值，要么是长度比较短的字符串时，会使用压缩列表来作为列表键的底层实现。

linkedlist（链表）

1、链表的实现

每个链表节点使用一个adlist.h/listNode结构来表示：

typedefstructlistNode {
// 前置节点指针structlistNode*prev;
//后置节点指针structlistNode*next;
//节点的值的指针void*value;
} listNode;

多个listNode可以通过pre（前置）和next（后置）组成双端链表；

虽然仅仅使用多个listNode结构可以组成链表，但使用adlist.h/list来持有链表的话，操作起来会更方便：

typedefstructlist {
//头部节点指针listNode*head;
//尾部节点指针listNode*tail;
//节点值复制void*(*dup)(void*ptr);
//节点值释放void (*free)(void*ptr);
//节点值对比int (*match)(void*ptr, void*key);
//链表所包含的节点数量unsignedlonglen;
} list;

list结构为链表提供了表头指针head、表尾指针tail以及链表长度计数器len，而dup、free、match则是用于实现多态链表所需的类型特定函数。

2、链表的特性：

• 双端：带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
• 无环：prev指针和next指针都指向NULL
• 带表头指针和表尾指针：通过list结构的head和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)
• 带链表长度计数器：获取链表中节点数量的复杂度为O(1)
• 多态：链表节点使用void*指针保存节点值，通过dup、free、match为节点值设置类型特定函数，所以链表可以保存各种不同类型的值

ziplist（压缩列表）

1、压缩列表的构成

2、压缩列表节点的构成

2.1 previous_entry_length

2.2 encoding

节点的encoding记录了节点的content属性所保存数据的类型以及长度：

2.3 content

3、连锁更新

二、3.2以后的列表实现

1、quicklist的数据结构

typedefstructquicklist {
//quicklist的链表头quicklistNode*head;
//quicklist的链表尾quicklistNode*tail; 
//所有压缩列表中的总元素个数unsignedlongcount;
//链表节点的个数 quicklistNodeunsignedlonglen;       
    ...
} quicklist;

2、quicklistNode的结构

typedefstructquicklistNode {
//指向前节点的指针structquicklistNode*prev;     //前一个quicklistNode//指向后节点的指针structquicklistNode*next;     //后一个quicklistNode//quicklistNode指向的压缩列表unsignedchar*zl;  
//压缩列表的的字节大小unsignedintsz;    
//压缩列表的元素个数unsignedintcount : 16;        //ziplist中的元素个数     ....
} quicklistNode;

可以看到 node节点有指向前节点和后节点的指针，以及节点的元素保存的不是单纯的元素值，而是保存了一个压缩链表，所以有个指向压缩链表的指针*zl

在向quicklist添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩链表是否能容纳该元素，如果能够容纳，那么就直接保存到quicklistNode结构里面的压缩列表，如果不能容纳，才会新建一个Node结构。

quicklist会控制quicklistNode结构里面的压缩列表的大小或者元素个数，用来规避潜在的连锁更新的风险，但是并没有完全解除。