2.2 Redis-链表

 链表：具有高效节点重排能力，顺序性节点访问，通过增删节点灵活调整长度。C语言中没有内置链表，Redis构建了自身的链表实现。
 链表应用：
  1.Redis使用链表诸位链表键的底层实现。
  2.发布订阅、慢查询、监视器功能使用链表。
  3.Redis客户端使用链表保存多个客户端信息。
  4.链表构建客户端输出缓冲。
链表结构

typedef stryct listNode {//链表节点
  // 前置节点
  struct listNode *prev;
  // 后置节点
  struct listNode *next;
  // 节点值
  void *value;
}listNode;

typedef struct list {//链表
  //表头节点
  listNode *head;
  //表尾节点
  listNode *tail;
  // 链表所包含的节点数量
  unsigned long len;
  // 节点值复制函数
  void *(*dup)(void *ptr);
  // 节点值释放函数
  void *(*free)(void *ptr);
  // 节点值对比函数
  int (*match)(void *ptr,void *key);
}list;

一个list结构和3个listNode节点示意图所示：

1.2.1 链表结构示意图.png

 根据数据结构和示意图我们可以得到链表的以下信息
  1.双端链表，节点存在prev和next指针，在O(1)的情况下获得链表的前后节点；list中存在len属性，可以O(1)获得链表的长度；同时list中存在tail和head，O(1)获得头尾部节点信息。
  2.无环，不是环状结构，头节点的prev是null，尾节点的next是null。
  3.dup、free、match函数存在，可以让不同list存不同各类型的函数。