面試官:簡述 Redis 鏈表實現(xiàn)
寫在前面
小牛之前出了八股文背誦版系列,不少朋友問我,能不能搞個八股文精講,把面試問題講講透,于是系列就這樣誕生了。咱們第一期先聊聊Redis。
阿里面試:簡述Redis鏈表實現(xiàn)
鏈表,我感覺學(xué)過編程的小伙伴都知道。
但遺憾的是,我前兩天逛牛客網(wǎng),有個阿里面試官問:來,講講Redis的鏈表。
額,不好意思我沒看過。。。。
為了避免這種尷尬的情形發(fā)生,我寫了這篇博文,爭取讓大家20秒能掌握和面試官談笑風(fēng)生redis鏈表的能力。
首先明確一點,redis的鏈表是雙向鏈表,所以鏈表結(jié)構(gòu)的節(jié)點定義極其清晰
- typedef struct listNode {
- struct listNode * prev;//前置節(jié)點
- struct listNode * next;//后置節(jié)點
- void * value;//節(jié)點數(shù)值
- } listNode;
說實話,有這么一個結(jié)構(gòu),已經(jīng)夠大家寫雙向鏈表的所有操作了。
但Redis還是比較貼心的,它在listNode這一數(shù)據(jù)結(jié)構(gòu)上,又封裝了一個數(shù)據(jù)結(jié)構(gòu)list,方便程序員開發(fā)調(diào)用。
- typedef struct list {
- listNode * head;//鏈表頭
- listNode * tail;//鏈表尾
- unsigned long len;//鏈表長度
- void *(*dup) (void *ptr); //節(jié)點值復(fù)制函數(shù)
- void (*free) (void *ptr); //節(jié)點值釋放函數(shù)
- void (*match)(void *ptr,void *key); //節(jié)點值對比函數(shù)
- }
注意,其封裝的dup,free 和match均是針對節(jié)點的函數(shù),而不是針對整個鏈表而言的。
Redis也提供了相關(guān)函數(shù),給大家使用,比如鏈表的增加節(jié)點,刪除節(jié)點,等等就不用咱寫了,不然有小伙伴自己手寫寫錯了還可能搞個循環(huán)鏈表出來。列幾個用的多的函數(shù)給大家參考吧。
- lpush:向鏈表左邊增加元素
- rpush:向鏈表右邊增加元素
- lpop: 彈出左側(cè)第一個元素
- rpop:彈出右側(cè)第一個元素
- llen: 獲得鏈表長度
- lrange:按索引范圍獲得值
參考
- 《Redis源碼剖析與實戰(zhàn)》
- 《Redis的設(shè)計與實現(xiàn)》
- https://www.jianshu.com/p/624ed78852f7