redis面试（二）List链表数据

list 列表

我们总是说List为列表，其实在真正的数据结构来说，redis是自己基于c语言来实现的双向链表数据结构，主要的逻辑就是每个节点都可以指向下一个节点，这个结构就属于链表数组结构。
每个节点中的属性如下：

typedef struct listNode {struct listNode * prev; //上一个节点struct listNode * next; //下一个节点void * value; //当前节点值
}

本身的List列表也有一个对象，属性如下：

typedef struct list {listNode * head;  //头部节点地址listNode * tail;  //尾部节点地址unsigned long len;  长度void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);
} 

双向链表，获取prev和next的时间复杂度都是O(1)，而且不能搞成环，因为头和尾都是指向NULL的
head和tail指针，可以让头和尾的获取时间复杂度都是O(1)
len可以获取链表元素个数的时间复杂度是O(1)，lrange -> 遍历-> O(n)
支持多态，void*指针保存了value值，元素可以是不同类型的值，dup、free、match可以给节点值设置类型特定的函数

优点

即使列表中有数百万个元素，在列表头部或尾部添加新元素的操作也是在恒定时间内执行的。使用命令将新元素添加到包含十个元素的列表头部的速度 与 将元素添加到包含一千万个元素的列表头部的速度相同。

缺点

在使用数组实现的列表中，通过索引访问元素非常快（java中的ArrayList，常量时间索引访问），而在通过链接列表实现的列表中则不那么快（其中操作需要的工作量与所访问元素的索引成比例）。
如果在业务中确实要大量访问列表中的中间部分元素的话，建议使用有序列表ZSet

使用命令

LPUSH命令在列表的头部添加一个新元素；RPUSH添加到列表的尾部。
LPOP从列表头部移除并返回一个元素；RPOP执行相同操作，但从列表尾部移除。
LLEN返回列表的长度。
LMOVE原子地将元素从一个列表移动到另一个列表。
LRANGE从列表中提取一定范围的元素。
LTRIM将列表缩减为指定的元素范围。

例子

队列

当做队列使用（先进先出）
LPUSH命令在列表的头部添加一个新元素；
RPOP命令在尾部弹出一个元素，并移除；

堆栈

将列表视为堆栈（先进后出）
LPUSH命令在列表的头部添加一个新元素；
LPOP从列表头部移除并返回一个元素；

淘汰列表

LTRIM命令需要两个参数

LTRIM bikes:repairs 0 2

上面这个命令，就是保留列表中的索引0-2范围内的元素，其他元素全部丢弃