链表(双端链表) list

@[toc] --- ## list 的定义 **链表（双端链表）list**： <img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/20220609160817.png" style="zoom:50%;" /> **链表节点 listNode**： <img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/20220609160856.png" style="zoom:50%;" /> 只用 listNode 也能实现链表，不过 list 添加首尾指针和链表长度属性，能够在 O(1) 复杂度获取链表的最后一个节点以及链表长度 ## Redis 链表的特点 - 双端：链表节点带有表头指针和表尾指针，获取某个节点的前置节点和后置节点的复杂度都是 O(1) - 带链表长度计数器 len：程序获取链表中节点数量的复杂度为 O(1) - 无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点 <img src="https://cs-wiki.oss-cn-shanghai.aliyuncs.com/img/20220609161059.png" style="zoom:67%;" /> - 多态：链表节点使用 `void*` 指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以<u>链表可以用于保存各种不同类型的值</u>