当前位置：首页 > news >正文

redis面试（二）List链表数据

news 2025/8/4 20:49:32

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将列表缩减为指定的元素范围。