网上有关“双链表的基本操作”话题很是火热，小编也是针对双链表的基本操作寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。
前言
续接上文：redis压缩列表ziplist，内存优化之路
本文参考源码版本仍为Redis6.2。
quicklist是Redis底层最重要的数据结构之一，它是Redis对外提供的6种基本数据结构中List的底层实现，在Redis 3.2版本中引入。
在引入quicklist之前，Redis采用压缩链表（ziplist）以及双向链表（linked-list）作为List的底层实现。
当元素个数比较少并且元素长度比较小时，Redis采用ziplist作为其底层存储。
当任意一个条件不满足时，Redis采用linked-list作为底层存储结构。
这么做的主要原因是，当元素长度较小时，采用ziplist可以有效节省存储空间，但ziplist的存储空间是连续的，当元素个数比较多时，修改元素时，必须重新分配存储空间，这无疑会影响Redis的执行效率，故而采用一般的双向链表。
quicklist是综合考虑了时间效率与空间效率引入的新型数据结构。
<hr color=#000000 size=1">
一、quicklist真面目Redis源码中对quicklist的注释为 A doubly linked list of ziplists；也就是说quicklist是由ziplist组成的双向链表，其中每一个链表节点都是一个独立的ziplist结构，因此，从结构上看，quicklist就是ziplist的升级版。
优化的关键在于，如何控制好每个ziplist的大小
quicklist的节点ziplist越小，越有可能造成更多的内存碎片。极端情况下，一个ziplist只有一个数据entry，也就退化成了linked list
quicklist的节点ziplist越大，分配给ziplist的连续内存空间越困难。极端情况下，一个quicklist只有一个ziplist，也就退化成了ziplist
因此，合理配置参数显得至关重要，不同场景可能需要不同配置；redis提供list-max-ziplist-size参数进行配置，默认-2，表示每个ziplist节点大小不超过8KB
二、原理分析数据存储1. quicklistNode结构：typedef?struct?quicklistNode?{struct?quicklistNode?*prev;//前一个quicklistNodestruct?quicklistNode?*next;//后一个quicklistNodeunsigned?char?*zl;?//quicklistNode指向的ziplistunsigned?int?sz;?//ziplist的字节大小unsigned?int?count?:?16;?//ziplist中的元素个数unsigned?int?encoding?:?2;?//编码格式，原生字节数组或压缩存储unsigned?int?container?:?2;//存储方式unsigned?int?recompress?:?1;?//数据是否被压缩unsigned?int?attempted_compress?:?1;?//数据能否被压缩unsigned?int?extra?:?10;?//预留的bit位}?quicklistNode;其中
prev、next指向该节点的前后节点；
zl指向该节点对应的ziplist结构；
sz代表整个ziplist结构的大小；
encoding代表采用的编码方式：1代表是原生的，2代表使用LZF进行压缩；
container为quicklistNode节点zl指向的容器类型：1代表none,2代表使用ziplist存储数据
recompress代表这个节点之前是否是压缩节点，若是，则在使用压缩节点前先进行解压缩，使用后需要重新压缩，此外为1，代表是压缩节点；
attempted_compress测试时使用；
extra为预留
2. quicklist结构quicklist 作为一个链表结构，在它的数据结构中，是定义了整个 quicklist 的头、尾指针，这样一来，可以通过 quicklist 的数据结构，来快速定位到 quicklist 的链表头和链表尾。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;fill用来指明每个quicklistNode中ziplist长度，当fill为正数时，表明每个ziplist最多含有的数据项数，当fill为负数时，如下：
Length -1: 4k，即ziplist节点最大为4KB
Length -2: 8k，即ziplist节点最大为8KB
Length -3: 16k ...
Length -4: 32k
Length -5: 64k
fill取负数时，必须大于等于-5。可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小。实际上每个ziplist节点所占的内存会在该值上下浮动。
考虑quicklistNode节点个数较多时，我们经常访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩，通过修改参数list-compress-depth进行配置，即设置compress参数，该项的具体含义是两端各有compress个节点不压缩。
quicklist整体结构：
3. quicklistEntry结构quicklistNode中ziplist中的一个节点
typedef?struct?quicklistEntry?{const?quicklist?*quicklist;quicklistNode?*node;unsigned?char?*zi;unsigned?char?*value;long?long?longval;unsigned?int?sz;int?offset;}?quicklistEntry;其中：
quicklist指向当前元素所在的quicklist;
node指向当前元素所在的quicklistNode结构；
zi指向当前元素所在的ziplist;
value指向该节点的字符串内容；
longval为该节点的整型值；
sz代表该节点的大小，与value配合使用；
offset表明该节点相对于整个ziplist的偏移量，即该节点是ziplist第多少个entry
4. quicklistIter结构quicklist中用于遍历的迭代器：
typedef?struct?quicklistIter?{const?quicklist?*quicklist;quicklistNode?*current;unsigned?char?*zi;long?offset;?/*?offset?in?current?ziplist?*/int?direction;}?quicklistIter;quicklist指向当前元素所处的quicklist;
current指向元素所在quicklistNode;
zi指向元素所在的ziplist;
offset表明节点在所在的ziplist中的偏移量；
direction表明迭代器的方向。
数据压缩quicklist每个节点的实际数据存储结构为ziplist，这种结构的主要优势在于节省存储空间。
为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：
一部分是解释字段，另一部分是存放具体的数据字段。
解释字段可以占用1～3个字节，数据字段可能不存在。
解释字段|数据|......|解释字段|数据LZF压缩的数据格式有3种，即解释字段有3种：
000LLLLL：字面型，解释字段占用1个字节，数据字段长度由解释字段后5位决定；L是数据长度字段，数据长度是长度字段组成的字面值加1。例如：0000 0001代表数据长度为2
LLLooooo oooooooo：简短重复型，解释字段占用2个字节，没有数据字段，数据内容与前面数据内容重复，重复长度小于8；L是长度字段，数据长度为长度字段的字面值加2, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：0010 0000 0000 0100代表与前面5字节处内容重复，重复3字节。
111ooooo LLLLLLLL oooooooo：批量重复型，解释字段占3个字节，没有数据字段，数据内容与前面内容重复；L是长度字段，数据长度为长度字段的字面值加9, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：1110 0000 0000 0010 0001 0000代表与前面17字节处内容重复，重复11个字节。
quicklistLZF结构：
/*?quicklistLZF?is?a?4+N?byte?struct?holding?'sz'?followed?by?'compressed'.?*?'sz'?is?byte?length?of?'compressed'?field.?*?'compressed'?is?LZF?data?with?total?(compressed)?length?'sz'?*?NOTE:?uncompressed?length?is?stored?in?quicklistNode->sz.?*?When?quicklistNode->zl?is?compressed,?node->zl?points?to?a?quicklistLZF?*/typedef?struct?quicklistLZF?{unsigned?int?sz;?/*?LZF?size?in?bytes*/char?compressed[];}?quicklistLZF;zs 该压缩node的的总长度
compressed压缩后的数据片段(多个)，每个数据片段由解释字段和数据字段组成
当前ziplist未压缩长度存在于quicklistNode->sz字段中
当ziplist被压缩时，node->zl字段将指向quicklistLZF
1. 压缩LZF数据压缩的基本思想是：数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。
压缩算法的流程如下：遍历输入字符串，对当前字符及其后面2个字符进行散列运算，如果在Hash表中找到曾经出现的记录，则计算重复字节的长度以及位置，反之直接输出数据。
/*?*?compressed?format?*?*?000LLLLL?<L+1>;?literal,?L+1=1..33?octets?*?LLLooooo?oooooooo?;?backref?L+1=1..7?octets,?o+1=1..4096?offset?*?111ooooo?LLLLLLLL?oooooooo?;?backref?L+8?octets,?o+1=1..4096?offset?*/unsigned?intlzf_compress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)2. 解压缩根据LZF压缩后的数据格式，可以较为容易地实现LZF的解压缩。需要注意的是，可能存在重复数据与当前位置重叠的情况，例如在当前位置前的15个字节处，重复了20个字节，此时需要按位逐个复制。
unsigned?intlzf_decompress?(const?void?*const?in_data,?unsigned?int?in_len,?void?*out_data,?unsigned?int?out_len)基本操作1. 插入元素API定义：
/*?Insert?a?new?entry?before?or?after?existing?entry?'entry'.?*?*?If?after==1,?the?new?value?is?inserted?after?'entry',?otherwise?*?the?new?value?is?inserted?before?'entry'.?*/REDIS_STATIC?void?_quicklistInsert(quicklist?*quicklist,?quicklistEntry?*entry,?void?*value,?const?size_t?sz,?int?after)其中，参数after用于控制在entry之前或者之后插入。
正因为 quicklist 采用了链表结构，所以当插入一个新的元素时，quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素，这是通过 _quicklistNodeAllowInsert 函数来完成判断的。
REDIS_STATIC?int?_quicklistNodeAllowInsert(const?quicklistNode?*node,?const?int?fill,?const?size_t?sz)?{if?(unlikely(!node))return?0;int?ziplist_overhead;/*?size?of?previous?offset?*/if?(sz?<?254)ziplist_overhead?=?1;elseziplist_overhead?=?5;/*?size?of?forward?offset?*/if?(sz?<?64)ziplist_overhead?+=?1;else?if?(likely(sz?<?16384))ziplist_overhead?+=?2;elseziplist_overhead?+=?5;/*?new_sz?overestimates?if?'sz'?encodes?to?an?integer?type?*/unsigned?int?new_sz?=?node->sz?+?sz?+?ziplist_overhead;if?(likely(_quicklistNodeSizeMeetsOptimizationRequirement(new_sz,?fill)))return?1;else?if?(!sizeMeetsSafetyLimit(new_sz))return?0;else?if?((int)node->count?<?fill)return?1;elsereturn?0;}_quicklistNodeAllowInsert 函数会计算新插入元素后的大小（new_sz），这个大小等于 quicklistNode 的当前大小（node->sz）、插入元素的大小（sz），以及插入元素后 ziplist 的 prevlen 占用大小。
在计算完大小之后，_quicklistNodeAllowInsert 函数会依次判断新插入的数据大小（sz）是否满足要求，即单个 ziplist 是否不超过 8KB，或是单个 ziplist 里的元素个数是否满足要求。
只要这里面的一个条件能满足，quicklist 就可以在当前的 quicklistNode 中插入新元素，否则 quicklist 就会新建一个 quicklistNode，以此来保存新插入的元素。
这样一来，quicklist 通过控制每个 quicklistNode 中，ziplist 的大小或是元素个数，就有效减少了在 ziplist 中新增或修改元素后，发生连锁更新的情况，从而提供了更好的访问性能。
2. 删除元素quicklist对于元素删除提供了删除单一元素以及删除区间元素2种方案。
1）对于删除单一元素，可以使用quicklist对外的接口quicklistDelEntry实现，也可以通过quicklistPop将头部或者尾部元素弹出。
quicklistDelEntry函数调用底层quicklistDelIndex函数，该函数可以删除quicklistNode指向的ziplist中的某个元素，其中p指向ziplist中某个entry的起始位置。
quicklistPop可以弹出头部或者尾部元素，具体实现是通过ziplist的接口获取元素值，再通过上述的quicklistDelIndex将数据删除
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;02）对于删除区间元素，quicklist提供了quicklistDelRange接口，该函数可以从指定位置删除指定数量的元素
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;1start为需要删除的元素的起始位置，count为需要删除的元素个数。返回0代表没有删除任何元素，返回1并不代表删除了count个元素，因为count可能大于quicklist所有元素个数，故而只能代表操作成功。
总体删除逻辑为：不管什么方式删除，最终都会通过ziplist来执行元素删除操作。先尝试删除该链表节点所指向的ziplist中的元素，如果ziplist中的元素已经为空了，就将该链表节点也删除掉。
3. 更改元素quicklist更改元素是基于index，主要的处理函数为quicklistReplaceAtIndex。
其基本思路是先删除原有元素，之后插入新的元素。quicklist不适合直接改变原有元素，主要由于其内部是ziplist结构，ziplist在内存中是连续存储的，当改变其中一个元素时，可能会影响后续元素。故而，quicklist采用先删除后插入的方案。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;24. 查找元素quicklist查找元素主要是针对index，即通过元素在链表中的下标查找对应元素。基本思路是，首先找到index对应的数据所在的quicklistNode节点，之后调用ziplist的接口函数ziplistGet得到index对应的数据，源码中的处理函数为quicklistIndex。
typedef?struct?quicklist?{quicklistNode?*head;?//?quicklist的链表头quicklistNode?*tail;?//?quicklist的链表尾unsigned?long?count;?//?所有ziplist中的总元素个数unsigned?long?len;?//?quicklistNodes的个数int?fill?:?QL_FILL_BITS;//?单独解释unsigned?int?compress?:?QL_COMP_BITS;?//?具体含义是两端各有compress个节点不压缩...}?quicklist;3单链表的删除操作是指删除第i个结点，返回被删除结点的值。删除操作也需要从头引用开始遍历单链表，直到找到第i个位置的结点。如果i为1，则要删除第一个结点，则需要把该结点的直接后继结点的地址赋给头引用。对于其它结点，由于要删除结点，所以在遍历过程中需要保存被遍历到的结点的直接前驱，找到第i个结点后，把该结点的直接后继作为该结点的直接前驱的直接后继。删除操作如图
单链表的删除操作示意图
删除操作的算法实现如下：
public T Delete(int i)
{
if (IsEmpty()|| i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null&& j < i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The ith node is not exist!");
return default(T);
}
}
算法的时间复杂度分析：单链表上的删除操作与插入操作一样，时间主要消耗在结点的遍历上。如果表为空则不进行遍历。当表非空时，删除第i个位置的结点， i等于1遍历的结点数最少（1个），i等于n遍历的结点数最多（n个，n为单链表的长度），平均遍历的结点数为n/2。所以，删除操作的时间复杂度为O（n）。
关于“双链表的基本操作”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！
本文来自作者[隽娇娇]投稿，不代表育友号立场，如若转载，请注明出处：https://jxydedu.cn/jyan/202512-4133.html
评论列表（3条）
我是育友号的签约作者“隽娇娇”
本文概览：网上有关“双链表的基本操作”话题很是火热，小编也是针对双链表的基本操作寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。前言续接上文：re...
文章不错《双链表的基本操作》内容很有帮助