Redis-链表

链表

Redis构建了自己的链表实现，使用地方有列表键、发布与订阅、慢查询、监视器等

listNode{
//前置节点
struct listNode prev;
//后置节点
struct listNode next;
//节点的值
void = value;

}

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

特点

• 有前后指针获取前置后置节点复杂度为O(1)
• 无环：头尾指向null
• list结构获取头结点和尾节点时间复杂度为O(1)
• 链表长度计数 用len计数 获取长度时间复杂度为O(1)