[[432725]]

寫在前面

小牛之前出了八股文背誦版系列，不少朋友問我，能不能搞個八股文精講，把面試問題講講透，于是系列就這樣誕生了。咱們第一期先聊聊Redis。

阿里面試：簡述Redis鏈表實現

鏈表，我感覺學過編程的小伙伴都知道。

但遺憾的是，我前兩天逛牛客網，有個阿里面試官問：來，講講Redis的鏈表。

額，不好意思我沒看過。。。。

為了避免這種尷尬的情形發生，我寫了這篇博文，爭取讓大家20秒能掌握和面試官談笑風生redis鏈表的能力。

首先明確一點，redis的鏈表是雙向鏈表，所以鏈表結構的節點定義極其清晰

typedef struct listNode { 
     
    struct listNode * prev;//前置節點 
     
    struct listNode * next;//后置節點 
     
    void * value;//節點數值 
} listNode; 

說實話，有這么一個結構，已經夠大家寫雙向鏈表的所有操作了。

但Redis還是比較貼心的，它在listNode這一數據結構上，又封裝了一個數據結構list，方便程序員開發調用。

typedef struct list { 
 
    listNode * head;//鏈表頭 
 
    listNode * tail;//鏈表尾 
 
    unsigned long len;//鏈表長度 
 
    void *(*dup) (void *ptr); //節點值復制函數 
 
    void (*free) (void *ptr); //節點值釋放函數 
 
    void (*match)(void *ptr,void *key); //節點值對比函數 
} 

注意，其封裝的dup，free 和match均是針對節點的函數，而不是針對整個鏈表而言的。

Redis也提供了相關函數，給大家使用，比如鏈表的增加節點，刪除節點，等等就不用咱寫了，不然有小伙伴自己手寫寫錯了還可能搞個循環鏈表出來。列幾個用的多的函數給大家參考吧。

• lpush：向鏈表左邊增加元素
• rpush：向鏈表右邊增加元素
• lpop: 彈出左側第一個元素
• rpop：彈出右側第一個元素
• llen: 獲得鏈表長度
• lrange：按索引范圍獲得值

參考

• 《Redis源碼剖析與實戰》
• 《Redis的設計與實現》
• https://www.jianshu.com/p/624ed78852f7