介绍压缩列表
压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。
压缩列表和数组不同的是:压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中 entry 的个数;压缩列表在表尾还有一个 zlend,表示列表结束。
在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段直接定位到,因此查找第一个元素和最后一个元素的时间复杂度是 O(1)。而查找其他元素时,只能逐个元素查找,时间复杂度是 O(N)。