Redis系列（六）：数据结构List双向链表LPUSH、LPOP、RPUSH、RPOP、LLEN命令
1.介绍
redis中的list既实现了栈（先进后出）又实现了队列（先进先出）
1.示意图
2.各命令详解
LPUSH/RPUSH
LPUSH:
从队列的左边入队一个或多个元素
将所有指定的值插入到存于 key 的列表的头部。如果 key 不存在，那么在进行 push 操作前会创建一个空列表。 如果 key 对应的值不是一个 list 的话，那么会返回一个错误。
可以使用一个命令把多个元素 push 进入列表，只需在命令末尾加上多个指定的参数。元素是从最左端的到最右端的、一个接一个被插入到 list 的头部。
所以对于这个命令例子 LPUSH mylist a b c，返回的列表是 c 为第一个元素， b 为第二个元素， a 为第三个元素。
RPUSH:
从队列的右边入队一个元素
向存于 key 的列表的尾部插入所有指定的值。如果 key 不存在，那么会创建一个空的列表然后再进行 push 操作。 当 key 保存的不是一个列表，那么会返回一个错误。
可以使用一个命令把多个元素打入队列，只需要在命令后面指定多个参数。元素是从左到右一个接一个从列表尾部插入。 比如命令 RPUSH mylist a b c 会返回一个列表，其第一个元素是 a ，第二个元素是 b ，第三个元素是 c。
两个命令都返回list的长度
时间复杂度O(1) 相对于i++的操作
127.0.0.1:6379> lpush mylist c b a (integer) 3 127.0.0.1:6379> rpush mylist d e f (integer) 6 127.0.0.1:6379> lrange mylist 0 5 1) "a" 2) "b" 3) "c" 4) "d" 5) "e" 6) "f" 127.0.0.1:6379>
源码解析
{"rpush",rpushCommand,-3,
"write use-memory fast @list",
0,NULL,1,1,1,0,0,0},
{"lpush",lpushCommand,-3,
"write use-memory fast @list",
0,NULL,1,1,1,0,0,0},
LPUSH和RPUSH都是调的同一个函数通过传入LIST_HEAD和LIST_TAIL来判断怎么入队列
void lpushCommand(client *c) { pushGenericCommand(c,LIST_HEAD); } void rpushCommand(client *c) { pushGenericCommand(c,LIST_TAIL); }
void pushGenericCommand(client *c, int where) { int j, pushed = 0; robj *lobj = lookupKeyWrite(c->db,c->argv[1]); if (lobj && lobj->type != OBJ_LIST) { addReply(c,shared.wrongtypeerr); return; } for (j = 2; j < c->argc; j++) { if (!lobj) { lobj = createQuicklistObject(); quicklistSetOptions(lobj->ptr, server.list_max_ziplist_size, server.list_compress_depth); dbAdd(c->db,c->argv[1],lobj); } listTypePush(lobj,c->argv[j],where); pushed++; } addReplyLongLong(c, (lobj ? listTypeLength(lobj) : 0)); if (pushed) { char *event = (where == LIST_HEAD) ? "lpush" : "rpush"; signalModifiedKey(c,c->db,c->argv[1]); notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id); } server.dirty += pushed; }
LPOP/RPOP
LPOP:
移除并且返回 key 对应的 list 的第一个元素。
RPOP:
移除并返回存于 key 的 list 的最后一个元素。
两个命令都返回被移除的元素
时间复杂度O(1) 相对于i–的操作
127.0.0.1:6379> lpop mylist "a" 127.0.0.1:6379> rpop mylist "f" 127.0.0.1:6379> lrange mylist 0 5 1) "b" 2) "c" 3) "d" 4) "e" 127.0.0.1:6379>
源码解析
{"rpop",rpopCommand,2,
"write fast @list",
0,NULL,1,1,1,0,0,0},
{"lpop",lpopCommand,2,
"write fast @list",
0,NULL,1,1,1,0,0,0},
void lpopCommand(client *c) { popGenericCommand(c,LIST_HEAD); } void rpopCommand(client *c) { popGenericCommand(c,LIST_TAIL); }
可见和push一样通过判断LIST_HEAD，来确定删除db中元素
void popGenericCommand(client *c, int where) { robj *o = lookupKeyWriteOrReply(c,c->argv[1],shared.null[c->resp]); if (o == NULL || checkType(c,o,OBJ_LIST)) return; robj *value = listTypePop(o,where); if (value == NULL) { addReplyNull(c); } else { char *event = (where == LIST_HEAD) ? "lpop" : "rpop"; addReplyBulk(c,value); decrRefCount(value); notifyKeyspaceEvent(NOTIFY_LIST,event,c->argv[1],c->db->id); if (listTypeLength(o) == 0) { notifyKeyspaceEvent(NOTIFY_GENERIC,"del", c->argv[1],c->db->id); dbDelete(c->db,c->argv[1]); } signalModifiedKey(c,c->db,c->argv[1]); server.dirty++; } }
LLEN
返回存储在 key 里的list的长度。 如果 key 不存在，那么就被看作是空list，并且返回长度为 0。 当存储在 key 里的值不是一个list的话，会返回error。
时间复杂度：O(1) 相当于常量操作
127.0.0.1:6379> llen mylist (integer) 4 127.0.0.1:6379>
源码解析
{"llen",llenCommand,2,
"read-only fast @list",
0,NULL,1,1,1,0,0,0},
void llenCommand(client *c) { robj *o = lookupKeyReadOrReply(c,c->argv[1],shared.czero); if (o == NULL || checkType(c,o,OBJ_LIST)) return; addReplyLongLong(c,listTypeLength(o)); }
unsigned long listTypeLength(const robj *subject) { if (subject->encoding == OBJ_ENCODING_QUICKLIST) { return quicklistCount(subject->ptr); } else { serverPanic("Unknown list encoding"); } }
unsigned long quicklistCount(const quicklist *ql) { return ql->count; }