Redis系列(七):数据结构List双向链表中LPUSH、LPOP、RPUSH、R
1.示意图? ? ? ? ?2.各命令详解LPUSH/RPUSHLPUSH:从队列的左边入队一个或多个元素 将所有指定的值插入到存于 key 的列表的头部。如果 key 不存在,那么在进行 push 操作前会创建一个空列表。 如果 key 对应的值不是一个 list 的话,那么会返回一个错误。 可以使用一个命令把多个元素 push 进入列表,只需在命令末尾加上多个指定的参数。元素是从最左端的到最右端的、一个接一个被插入到 list 的头部。 所以对于这个命令例子? 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 rpush mylist d e f (integer) 6 6379> lrange mylist 0 5 1) "a" 2) b3) c4) d5) e6) f6379> 源码解析 {rpush",rpushCommand,-3,write use-memory fast @list"0,NULL,1,1)">0},{lpush0}, LPUSH和RPUSH都是调的同一个函数通过传入LIST_HEAD和LIST_TAIL来判断怎么入队列 void lpushCommand(client *c) { pushGenericCommand(c,LIST_HEAD); } void rpushCommand(client *void pushGenericCommand(client *c,int where) { int j,pushed = ; 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,1)">],lobj); } listTypePush(lobj,c->argv[j],1)">); pushed++; } addReplyLongLong(c,(lobj ? listTypeLength(lobj) : )); if (pushed) { char *event = (where == LIST_HEAD) ? " : ; signalModifiedKey(c,c->db,1)">]); notifyKeyspaceEvent(NOTIFY_LIST,event,1)">1],c->db->id); } server.dirty += pushed; } LPOP/RPOPLPOP:移除并且返回 key 对应的 list 的第一个元素。 RPOP:移除并返回存于 key 的 list 的最后一个元素。 两个命令都返回被移除的元素 时间复杂度O(1) 相对于i--的操作 lpop mylist rpop mylist rpop2write fast @listlpopvoid lpopCommand(client *c) { popGenericCommand(c,1)">void rpopCommand(client *可见和push一样通过判断LIST_HEAD,来确定删除db中元素 |