[[432725]]

寫在前面

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

阿里面試：簡(jiǎn)述Redis鏈表實(shí)現(xiàn)

鏈表，我感覺(jué)學(xué)過(guò)編程的小伙伴都知道。

但遺憾的是，我前兩天逛牛客網(wǎng)，有個(gè)阿里面試官問(wèn)：來(lái)，講講Redis的鏈表。

額，不好意思我沒(méi)看過(guò)。。。。

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

首先明確一點(diǎn)，redis的鏈表是雙向鏈表，所以鏈表結(jié)構(gòu)的節(jié)點(diǎn)定義極其清晰

typedef struct listNode { 
     
    struct listNode * prev;//前置節(jié)點(diǎn) 
     
    struct listNode * next;//后置節(jié)點(diǎn) 
     
    void * value;//節(jié)點(diǎn)數(shù)值 
} listNode; 

說(shuō)實(shí)話，有這么一個(gè)結(jié)構(gòu)，已經(jīng)夠大家寫雙向鏈表的所有操作了。

但Redis還是比較貼心的，它在listNode這一數(shù)據(jù)結(jié)構(gòu)上，又封裝了一個(gè)數(shù)據(jù)結(jié)構(gòu)list，方便程序員開(kāi)發(fā)調(diào)用。

typedef struct list { 
 
    listNode * head;//鏈表頭 
 
    listNode * tail;//鏈表尾 
 
    unsigned long len;//鏈表長(zhǎng)度 
 
    void *(*dup) (void *ptr); //節(jié)點(diǎn)值復(fù)制函數(shù) 
 
    void (*free) (void *ptr); //節(jié)點(diǎn)值釋放函數(shù) 
 
    void (*match)(void *ptr,void *key); //節(jié)點(diǎn)值對(duì)比函數(shù) 
} 

注意，其封裝的dup，free 和match均是針對(duì)節(jié)點(diǎn)的函數(shù)，而不是針對(duì)整個(gè)鏈表而言的。

Redis也提供了相關(guān)函數(shù)，給大家使用，比如鏈表的增加節(jié)點(diǎn)，刪除節(jié)點(diǎn)，等等就不用咱寫了，不然有小伙伴自己手寫寫錯(cuò)了還可能搞個(gè)循環(huán)鏈表出來(lái)。列幾個(gè)用的多的函數(shù)給大家參考吧。

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

參考

• 《Redis源碼剖析與實(shí)戰(zhàn)》
• 《Redis的設(shè)計(jì)與實(shí)現(xiàn)》
• https://www.jianshu.com/p/624ed78852f7