這篇博文，主要講解了Redis中的List（列表）的實現原理和命令。 ...
小喵的嘮叨話：前面我們介紹了Redis的string的數據結構的原理和操作。當時我們提到Redis的鍵值對不僅僅是字元串。而這次我們就要介紹Redis的第二個數據結構了，List（鏈表）。由於List在原理上的實現並不是特別的複雜，我們在這裡將原理和具體的命令都放在一起介紹。
小喵的個人博客地址: http://www.miaoerduo.com/ ,歡迎隨時騷擾~
該博客原地址： http://www.miaoerduo.com/redis/三、redis基本操作-list.html ，排版應該更精美一點。
Redis基本操作——List（原理篇）
學習過數據結構的同學，一定對鏈表（Linked List）十分的熟悉。相信我們自己也曾經使用過這種數據結構。
鏈表分為很多種：單向鏈表，雙向鏈表，迴圈鏈表，塊狀鏈表[1]等等。
鏈表的作用也有很多。首先，鏈表可以存放數據。其次鏈表可以模擬隊列、堆棧等其他的數據結構。
鏈表的實現也有多種，以C語言為例，最常見的是構造節點node，node中又有指針，用於指向下一個node，這樣就構成了單向鏈表，如果node中有兩個指針，分別指向前一個和後一個node，則構造了雙向鏈表，再如果鏈表是首尾相連的，那麼就是迴圈鏈表。鏈表的具體演算法，是數據結構裡面的內容，我們這裡就不專門介紹啦。
那麼，Redis內部的List是什麼樣子的鏈表呢？又是怎麼來維護的呢？
我們慢慢的剖析。
1 typedef struct listNode { 2 3 // 前置節點 4 struct listNode *prev; 5 6 // 後置節點 7 struct listNode *next; 8 9 // 節點的值 10 void *value; 11 } listNode;
上述就是Redis的節點的定義。
可以看出，這是一個雙向的鏈表。比較有意思的是，節點記憶體的值，是一個void *的指針，這就說明節點內部可以存放任何的內容。
反派汪：我不能理解為什麼value是void *的指針就能存任何內容？我甚至不知道為什麼還有要void *這麼奇怪的數據類型。
喵太：其實很多人也有這個疑問。不過先問問你自己，指針到底是什麼？int *，float *和char *的這幾種指針有什麼區別？
反派汪：指針裡面存的就是地址，通過地址就能訪問到指定的記憶體。以int *指針為例，int *說明，指針指向的是一個由int型的數據組成的記憶體。通過指針運算符*，我們就能取到對應位置的記憶體中的值。通過對指針的+和-，我們就能移動到相鄰的位置。
喵太：嗯，說的不錯，但是你只說對了一半。指針裡面存放的是地址，無論任何類型的指針，裡面存放的都只是一個32位的無符號整數。指針的類型，其實只是決定了對記憶體進行的操作。int *的指針，每次加1的時候，其實移動了4個位元組，char *則移動1個。使用指針運算符*其實也是一樣。int *會得到連續4個位元組的內容，並且存進一個int變數裡面，而char *則會得到一個位元組的內容，並存進一個char裡面。因此，任何類型的指針其實本質上是一樣的。
反派汪：那你的意思是，所有類型的指針都是一樣的了。那麼我還是不能理解void *的指針究竟能做什麼。
喵太：void *的指針是C語言中最簡單的一種指針，它存放的是一個地址，並且沒有給出任何操作上的提示。但是任何類型的指針都能賦給void *的指針。void *的指針也能強制轉換成任何類型的指針。這裡使用void *的指針，只是在說明，value對應的是一塊記憶體。開發者，可以自行轉換指針的類型，來做相應的操作。如果你熟悉C語言的話，malloc函數的返回值也是一個void *的指針，而我們通常會把它強制轉換成我們需要的任何數據類型。
反派汪：這樣啊，那原則上這裡的指針用什麼類型的都是可以的了？反正就是一個地址而已。只是void *更純粹一點，也最符合要求，畢竟它只是指向數據的地址，沒有做任何的限制。
喵太：孺狗可教也。
現在，我們有了listNode這個節點的數據結構，就可以構造我們的鏈表了。
圖一 鏈表的結構
依照上圖的示意圖，我們就可以使用listNode構造一個雙向鏈表了。
Redis中，為了更好地管理鏈表，定義了一個list的數據結構，作為鏈表的封裝。
1 typedef struct list { 2 3 // 頭節點 4 listNode *head; 5 6 // 尾節點 7 listNode *tail; 8 9 // 鏈表中的節點數 10 unsigned int len; 11 12 // 節點值複製函數 13 void *(*dup) (void *ptr); 14 15 // 節點值釋放函數 16 void (*free) (void *ptr); 17 18 // 節點值對比函數 19 int (*match) (void *ptr, void *key); 20 } list;
list結構記錄了鏈表的頭指針，尾指針，鏈表的節點數。dup，free和match三個成員則表示對節點的值進行複製，釋放和比較的函數。由於這裡的節點的value的內容是任意的，複製和釋放並不一定能用類似於memcpy和free的函數來處理（不太理解的話，可以google一下淺拷貝和深拷貝）。
因此，我們得到的最終的鏈表結構是這個樣子的：
圖二 鏈表的結構
Redis的鏈表的實現的主要特性如下：
- 雙端：鏈表節點都有prev和next指針，這樣獲取一個節點的前置節點和後置節點的演算法複雜度都為O(1)。
- 無環：list的第一個節點（頭節點）的prev和最後一個節點（尾節點）的next都指向NULL。
- 帶表頭指針和表尾指針：通過list的head和tail兩個指針，可以隨意的從鏈表的頭和尾進行操作。
- 帶鏈表長度計數器：可以通過len成員來獲取鏈表的節點的個數，複雜度O(1)。
- 多態：鏈表使用void *指針來保存value，並且可以通過dup，free，match來操控節點的value值，因此，該鏈表可以保存任意類型的值。
小喵看到這個多態的實現也是驚呆了，原來C語言也能實現多態，也第一次知道了函數指針居然可以這麼用。
由此想到之前看過的一句話：高手用樹葉也能殺人。希望每個人都能成為傳說中的高手~
關於鏈表的操作，是數據結構課程中的基礎，無外乎是增、刪、改、查這四個操作，這裡不再介紹。聰明的你，bing一下就OK了！
Redis基本操作——List（實戰篇）
現在，我們已經基本瞭解了Redis的List結構的底層實現。那麼，Redis提供了哪些可以供我們調用的介面呢？請聽小喵慢慢道來。
以下指令根據類別和使用的頻率進行排序。
指令清單：
- BLPOP
- BRPOP
- BRPOPLPUSH
- LINDEX
- LINSERT
- LLEN
- LPOP
- LPUSH
- LPUSHX
- LRANGE
- LREM
- LSET
- LTRIM
- RPOP
- RPOPLPUSH
- RPUSH
- RPUSHX
一、PUSH操作
1，RPUSH key value [value ...]
從隊列的右邊入隊一個元素或多個元素，複雜度O(1)。
將所有指定的值插入存於key的列表的尾部（從右側插入）。如果key不存在，那麼PUSH之前，會先自動創建一個空的列表。如果key對應的值不是一個list的話，則會返回一個錯誤。如果同時push多個值的話，值會依次從左到右PUSH從尾部進入list。
那麼這個命令有什麼作用呢？
作用大大滴！
PUSH和POP操作，其實是隊列的基本操作。Redis的list就是一個極其強大的隊列系統。我們在哪些地方會用到隊列呢？下麵，我們說兩個例子：
a，評論系統
逛過微博的筒子們應該都對評論系統有瞭解。我們在看完一條微博之後，常常會評論一番，或者看看其他人的吐槽。每條評論的記錄都是按照時間順序排序的。我們讀的時候也是這個順序。這時，隊列就是一個很好的存儲結構。每提交一次評論，都向list的末尾添加一個新的節點。
當然，博客本身也可以是這樣的結構。
b，並行轉串列
我們做後臺開發的筒子們應該都遇到過類似的情景。用戶每時每刻都可能發出請求，而且請求的頻率經常變化。這時，後臺的程式不可能立刻響應每一個用戶的請求，尤其是請求特別占資源的服務的時候（雙11的時候，你有沒有看到404頁面？）。有什麼好的辦法來解決這個問題呢？我們需要一個排隊系統。根據用戶的請求時間，將用戶的請求放入隊列中，後臺程式依次從隊列中獲取任務，處理並將結果返回到結果隊列。
這其實也是一個生產者消費者模型。通過隊列，我們將並行的請求轉換成串列的任務隊列，之後依次處理（當然後臺的程式也可以多核並行處理）。
那麼，這麼強大的功能，我們不馬上試試嗎？
redis> rpush queue a (integer) 1 redis> rpush queue b (integer) 2 redis> rpush queue c (integer) 3 redis> rpush queue d e f (integer) 6 redis> lrange queue 0 -1 1) "a" 2) "b" 3) "c" 4) "d" 5) "e" 6) "f"
lrange這個命令是獲取指定範圍的list中的數據，我們下麵再具體介紹。
這個例子中，我們依次將a、b、c、d、e、f、g從尾部(右側)追加到queue中，最後通過lrange查看queue中的數據的順序。
2，LPUSH key value [value ...]
從隊列的左邊入隊一個或多個元素，複雜度O(1)。
這個指令和RPUSH幾乎一樣，只是插入節點的方向相反了，是從list的頭部(左側)進行插入的。
1 redis> del queue 2 (integer) 1 3 redis> lpush queue a 4 (integer) 1 5 redis> lpush queue b 6 (integer) 2 7 redis> lpush queue c 8 (integer) 3 9 redis> lpush queue e f g 10 (integer) 6 11 redis> lrange queue 0 -1 12 1) "g" 13 2) "f" 14 3) "e" 15 4) "c" 16 5) "b" 17 6) "a"
可以看出，結果正好和RPUSH相反。
3，RPUSHX key value
從隊列的右邊入隊一個元素，僅隊列存在時有效。當隊列不存在時，不進行任何操作。
1 # 之前queue已經存在，且有a、b、c、d、e、f、g這6個元素 2 redis> rpushx queue z 3 (integer) 7 4 redis> del queue 5 (integer) 1 6 redis> rpushx queue z 7 (integer) 0
可以看出，最開始rpushx向queue中新增了一個節點，但當我們刪掉了queue時，再rpushx，就沒有插入成功（返回值為0）。
4，LPUSHX key value
從隊列的左邊入隊一個元素，僅隊列存在時有效。當隊列不存在時，不進行任何操作。
參考RPUSHX。
二、POP操作
PUSH操作，是從隊列頭部和尾部增加節點的操作。而POP是獲取並刪除頭尾節點的操作。
1，LPOP key
從隊列的左邊出隊一個元素，複雜度O(1)。如果list為空，則返回nil。
1 redis> del queue 2 (integer) 0 3 redis> rpush queue a b c d e f 4 (integer) 6 5 redis> lrange queue 0 -1 6 1) "a" 7 2) "b" 8 3) "c" 9 4) "d" 10 5) "e" 11 6) "f" 12 redis> lpop queue 13 "a" 14 redis> lpop queue 15 "b" 16 redis> lrange queue 0 -1 17 1) "c" 18 2) "d" 19 3) "e" 20 4) "f" 21 redis> rpop queue 22 "f" 23 redis> rpop queue 24 "e" 25 redis> lrange queue 0 -1 26 1) "c" 27 2) "d"
我們首先向空的list中添加了a、b、c、d、e、f這6個值，之後從左邊POP(LPOP)出兩個值，再從右側POP(RPOP)出兩個值。
2，RPOP key
從隊列的右邊出隊一個元素，複雜度O(1)。如果list為空，則返回nil。
見LPOP。
3，BLPOP key [key ...] timeout
刪除，並獲得該列表中的第一元素，或阻塞，直到有一個可用。
這是LPOP的阻塞版本。在LPOP的時候，如果隊列中沒有值，則會返回一個nil。而BLPOP則會等待一段時間，如果list中有值（等待的時候，被添加的），則返回對應值；如果在給定時間內仍沒有得到結果，則返回nil。
1 redis> lrange queue 0 -1 2 1) "c" 3 2) "d" 4 redis> BLPOP queue 1 5 1) "queue" 6 2) "c" 7 redis> BLPOP queue 1 8 1) "queue" 9 2) "d" 10 redis> BLPOP queue 1 11 (nil) 12 (1.10s) 13 redis> LPOP queue 14 (nil)
我們仍接著上面的實驗繼續，這時queue裡面只有2個元素了，我們使用BLPOP取值，前兩次都成功地得到了值，效果和LPOP一樣。但第三次的時候，由於list已經為空，但是BLPOP並沒有立刻返回nil，而是阻塞了一點時間(timeout的時間)，之後才返回了nil。最後，我們試驗了一下LPOP，證實了LPOP是立刻返回結果的。
timeout表示等待的時間，單位是秒。當設為0時，表示永遠阻塞，非0時，表示等待的最長時間。
要註意的是，LBPOP支持多個key，也就是說可以同時監聽多個list，並按照key的順序，依次檢查list是否為空，如果不為空，則返回最優先的list中的值。如果都為空，則阻塞，直到有一個list不為空，那麼返回這個list對應的值。這裡進行試驗不是特別的方便，更具體的介紹可以查看中文官網的文檔：http://redis.cn/commands/blpop.html。
4，BRPOP key [key ...] timeout
刪除，並獲得該列表中的最後一個元素，或阻塞，直到有一個可用。
參考BLPOP。
三、POP and PUSH
1，RPOPLPUSH source destination
刪除列表中的最後一個元素，將其追加到另一個列表。
這個命令可以原子性地返回並刪除source對應的列表的最後一個元素（尾部元素），並將鈣元素放入destination對應的列表的第一個元素位置（列表頭部）。
1 redis> rpush q1 1 2 3 4 5 2 (integer) 5 3 redis> lrange q1 0 -1 4 1) "1" 5 2) "2" 6 3) "3" 7 4) "4" 8 5) "5" 9 redis> rpoplpush q1 q2 10 "5" 11 redis> rpoplpush q1 q2 12 "4" 13 redis> lrange q1 0 -1 14 1) "1" 15 2) "2" 16 3) "3" 17 redis> lrange q2 0 -1 18 1) "4" 19 2) "5"
我們簡單的看一下上述的例子，首先我們初始化一個q1，內容是{1, 2, 3, 4, 5}。這是q2沒有定義，可以理解是一個空的list {}。
之後使用rpoplpush，從q1右邊pop出一個元素5，然後在q2左側push進。則現在的q1為{1, 2, 3, 4}，q2為{5}。
再進行一次rpoplpush，從q1右邊pop出一個元素4，然後在q2左側push進。則現在的q1為{1, 2, 3}，q2為{4, 5}。
那麼，這個有意思的命令有什麼實際的用處呢？
redis的官網給出了兩個有意思的案例（因為寫的很詳細，所以直接照搬下來了）[2]：
模式：安全的隊列
Redis通常都被用做一個處理各種後臺工作或消息任務的消息伺服器。 一個簡單的隊列模式就是：生產者把消息放入一個列表中，等待消息的消費者用 RPOP 命令（用輪詢方式）， 或者用 BRPOP 命令（如果客戶端使用阻塞操作會更好）來得到這個消息。
然而，因為消息有可能會丟失，所以這種隊列並是不安全的。例如，當接收到消息後，出現了網路問題或者消費者端崩潰了， 那麼這個消息就丟失了。
RPOPLPUSH (或者其阻塞版本的 BRPOPLPUSH） 提供了一種方法來避免這個問題：消費者端取到消息的同時把該消息放入一個正在處理中的列表。 當消息被處理了之後，該命令會使用 LREM 命令來移除正在處理中列表中的對應消息。
另外，可以添加一個客戶端來監控這個正在處理中列表，如果有某些消息已經在這個列表中存在很長時間了（即超過一定的處理時限）， 那麼這個客戶端會把這些超時消息重新加入到隊列中。
模式：迴圈列表
RPOPLPUSH 命令的 source 和 destination 是相同的話， 那麼客戶端在訪問一個擁有n個元素的列表時，可以在 O(N) 時間里一個接一個獲取列表元素， 而不用像 LRANGE 那樣需要把整個列表從伺服器端傳送到客戶端。
上面這種模式即使在以下兩種情況下照樣能很好地工作： * 有多個客戶端同時對同一個列表進行旋轉（rotating）：它們會取得不同的元素，直到列表裡所有元素都被訪問過，又從頭開始這個操作。 * 有其他客戶端在往列表末端加入新的元素。
這個模式讓我們可以很容易地實現這樣一個系統：有 N 個客戶端，需要連續不斷地對一批元素進行處理，而且處理的過程必須儘可能地快。 一個典型的例子就是伺服器上的監控程式：它們需要在儘可能短的時間內，並行地檢查一批網站，確保它們的可訪問性。
值得註意的是，使用這個模式的客戶端是易於擴展（scalable）且安全的（reliable），因為即使客戶端把接收到的消息丟失了， 這個消息依然存在於隊列中，等下次迭代到它的時候，由其他客戶端進行處理。
2，BRPOPLPUSH source destination timeout
彈出一個列表的值，將它推到另一個列表，並返回它;或阻塞，直到有一個可用
RPOPLPUSH的阻塞版本。timeout的單位是秒，當timeout為0的時候，表示無限期阻塞。
具體使用參考RPOPLPUSH。
四、其他
和名字一樣易懂，這裡不再過多解釋。
2，LRANGE key start stop
從列表中獲取指定返回的元素
我們在前面用到了很多次。LRANGE可以獲取list的指定範圍的值。範圍用start和stop表示。負數表示從右向左數。
需要註意的是，超出範圍的下標不會產生錯誤：如果start>end，會得到空列表，如果end超過隊尾，則Redis會將其當做列表的最後一個元素。
3，LINDEX key index
獲取一個元素，通過其索引列表
我們之前介紹的操作都是對list的兩端進行的，所以演算法複雜度都只有O(1)。而這個操作是指定位置來進行的，每次操作，list都得找到對應的位置，因此演算法複雜度為O(N)。list的下表是從0開始的，index為負的時候是從右向左數。-1表示最後一個元素。當下標超出的時候，會返回nul。所以不用像操作數組一樣擔心範圍越界的情況。
1 redis> rpush q1 a b c d f e g 2 (integer) 7 3 redis> lrange q1 0 -1 4 1) "a" 5 2) "b" 6 3) "c" 7 4) "d" 8 5) "f" 9 6) "e" 10 7) "g" 11 redis> lindex q1 0 12 "a" 13 redis> lindex q1 3 14 "d" 15 redis> lindex q1 4 16 "f" 17 redis> lindex q1 -1 18 "g" 19 redis> lindex q1 100 20 (nil)
4，LSET key index value
設置隊列裡面一個元素的值
這個操作和LINDEX類似，只不過LINDEX是讀，而LSET是寫。下標的用法和LINDX相同。不過當index越界的時候，這裡會報異常。
1 redis> rpush q1 a b c d f e g 2 (integer) 7 3 redis> lrange q1 0 -1 4 1) "a" 5 2) "b" 6 3) "c" 7 4) "d" 8 5) "f" 9 6) "e" 10 7) "g" 11 redis> lset q1 0 1 12 OK 13 redis> lset q1 3 3 14 OK 15 redis> lset q1 -1 0 16 OK 17 redis> lset q1 100 0 18 (error) ERR index out of range 19 redis> lrange q1 0 -1 20 1) "1" 21 2) "b" 22 3) "c" 23 4) "3" 24 5) "f" 25 6) "e" 26 7) "0"
5，LREM key count value
從列表中刪除元素
該命令用於從key對應的list中，移除前count次出現 的值為value的元素。count參數有三種情況：
count > 0: 表示從頭向尾（左到右）移除值為value的元素。
count < 0: 表示從尾向頭（右向左）移除值為value的元素。
count = 0: 表示移除所有值為value的元素。
1 redis> rpush q 1 0 1 1 2 1 0 1 1 2 (integer) 9 3 redis> lrange q 0 -1 4 1) "1" 5 2) "0" 6 3) "1" 7 4) "1" 8 5) "2" 9 6) "1" 10 7) "0" 11 8) "1" 12 9) "1" 13 redis> lrem q 2 1 14 (integer) 2 15 redis> lrange q 0 -1 16 1) "0" 17 2) "1" 18 3) "2" 19 4) "1" 20 5) "0" 21 6) "1" 22 7) "1" 23 redis> lrem q -2 1 24 (integer) 2 25 redis> lrange q 0 -1 26 1) "0" 27 2) "1" 28 3) "2" 29 4) "1" 30 5) "0" 31 redis> lrem q 0 1 32 (integer) 2 33 redis> lrange q 0 -1 34 1) "0" 35 2) "2" 36 3) "0"
6，LTRIM key start stop
修剪到指定範圍內的清單
這個命令和LRANGE十分相似，LRANGE會將指定範圍的元素返回給客戶端，而LTRIM會對list進行修剪，使其只包含指定範圍的元素。start和stop表示範圍。
超出範圍的下標不會產生錯誤：如果start>end，會得到空列表，如果end超過隊尾，則Redis會將其當做列表的最後一個元素。
1 redis> rpush q a b c d e f g 2 (integer) 7 3 redis> lrange q 0 -1 4 1) "a" 5 2) "b" 6 3) "c" 7 4) "d" 8 5) "e" 9 6) "f" 10 7) "g" 11 redis> ltrim q 1 4 12 OK 13 redis> lrange q 0 -1 14 1) "b" 15 2) "c" 16 3) "d" 17 4) "e"
7，LINSERT key BEFORE|AFTER pivot value
在列表中的另一個元素之前或之後插入一個元素
該命令將value插入值key對應的列表的基準值pivot的前面或是後面。
當key不存在時，這個list被視為空列表，任何操作都不會發生。
當key存在，但保存的不是list，則會報error。
該命令會返回修改之後的list的長度，如果找不到pivot，則會返回-1。
1 redis> rpush q a b c d e 2 (integer) 5 3 redis> lrange q 0 -1 4 1) "a" 5 2) "b" 6 3) "c" 7 4) "d" 8 5) "e" 9 redis> linsert q before c 0 10 (integer) 6 11 redis> linsert q after c 0 12 (integer) 7 13 redis> linsert q before 0 1 14 (integer) 8 15 redis> linsert q after 0 1 16 (integer) 9 17 redis> lrange q 0 -1 18 1) "a
