Redis的雙向鏈表一文全知道
本文轉(zhuǎn)載自微信公眾號(hào)「學(xué)習(xí)Java的小姐姐」，作者學(xué)習(xí)Java的小姐姐0618 。轉(zhuǎn)載本文請(qǐng)聯(lián)系學(xué)習(xí)Java的小姐姐公眾號(hào)。
前言
hello，又見(jiàn)面了。不要問(wèn)為什么，問(wèn)就是勤勞。馬上要開啟爆更模式啦。
在Redis中鏈表List的應(yīng)用非常廣泛，但是Redis是采用C語(yǔ)言來(lái)寫，底層采用雙向鏈表實(shí)現(xiàn)(這邊提一嘴，如果是科班出身或者大學(xué)有學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)，可以劃走啦)。我們今天的重點(diǎn)就是雙向鏈表。
API使用
先來(lái)使用一下API。如果之前有用過(guò)的同學(xué)，可以直接跳到下一小節(jié)。
lpush左側(cè)插入數(shù)據(jù)
使用lpush命令往list的左側(cè)中插入a，b，c三個(gè)字符，這邊注意順序，查詢出來(lái)的是c，b，a。下面會(huì)說(shuō)為什么，先挖個(gè)坑。
rpush右側(cè)插入數(shù)據(jù)
使用rpush命令往list中插入d，e兩個(gè)字符，查詢出來(lái)的順序是和我們想的一樣，最后兩位是d，e。
刪除某個(gè)數(shù)據(jù)
使用lrem命令刪除a字符，那么中間1代表什么意思呢?其為count，表示移除列表中與a相等的元素個(gè)數(shù)。即如果count>0，表示從表頭開始向表尾搜索，移除count個(gè)與a相等的元素。如果count<0，表示從表尾開始向表頭搜索，移除count個(gè)與a相等的元素。如果count=0，移除所有與a相等的元素，因?yàn)槭且瞥?，所以不管從表頭還是表尾，結(jié)果是一樣的。
修改某個(gè)數(shù)據(jù)
使用lset命令將mylist的下標(biāo)為1的元素修改為dd，原來(lái)list為c ,b，d，e，修改后的結(jié)果為c，dd，d，e。
具體邏輯圖
這邊看不懂沒(méi)關(guān)系，下面會(huì)針對(duì)每個(gè)模塊詳細(xì)說(shuō)明。
雙向鏈表的定義
節(jié)點(diǎn)ListNode
包括頭指針prev，尾指針next，當(dāng)前的值value，如下圖所示。每個(gè)節(jié)點(diǎn)都有兩個(gè)指針，既能從表頭根據(jù)尾指針找到表尾，又能從表尾根據(jù)頭指針prev找到表頭，如果將他們連起來(lái)，就構(gòu)成了雙向鏈表。
具體代碼如下：
- //定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)體
- typedef struct listNode {
- //前面一個(gè)節(jié)點(diǎn)的指針
- struct listNode *prev;
- //后面一個(gè)節(jié)點(diǎn)的指針
- struct listNode *next;
- //當(dāng)前節(jié)點(diǎn)的值的指針 ，因?yàn)橹档念愋筒淮_定
- void *value;
- } listNode;
整體架構(gòu)
包括頭指針head，尾指針tail，整個(gè)鏈表長(zhǎng)度len，一些函數(shù)(個(gè)人認(rèn)為不重要，如果有知道的小伙伴歡迎評(píng)論)，如下圖所示。頭指針head指向整個(gè)鏈表的第一個(gè)節(jié)點(diǎn)，尾指針tail指向整個(gè)鏈表的最后一個(gè)節(jié)點(diǎn)。
具體代碼如下：
- //定義鏈表，對(duì)鏈表節(jié)點(diǎn)的再封裝
- typedef struct list {
- listNode *head;//頭指針
- listNode *tail;//尾指針
- void *(*dup)(void *ptr);//節(jié)點(diǎn)拷貝函數(shù)
- void (*free)(void *ptr);//釋放節(jié)點(diǎn)值函數(shù)
- int (*match)(void *ptr, void *key);//判斷兩個(gè)節(jié)點(diǎn)是否相等函數(shù)
- unsigned long len;//鏈表長(zhǎng)度
- } list;
雙向鏈表的實(shí)現(xiàn)
創(chuàng)建表頭
我們創(chuàng)建list表結(jié)構(gòu)，首先需要判斷當(dāng)前是否有可分配的空間來(lái)創(chuàng)建，使用zmalloc方法來(lái)分配空間，如果分配不了，則返回NULL，如果可以分配，則繼續(xù)。接著賦值list的頭節(jié)點(diǎn)head和尾節(jié)點(diǎn)tail為NULL，len為0，賦值相關(guān)函數(shù)為NULL。最后返回結(jié)果list。
- //創(chuàng)建一個(gè)表頭，返回值是鏈表結(jié)構(gòu)的指針
- list *listCreate(void)
- {
- struct list *list;
- //嘗試分配空間
- if ((list = zmalloc(sizeof(*list))) == NULL)
- return NULL;
- //相關(guān)屬性賦值
- list->head = list->tail = NULL;
- list->len = 0;
- list->dup = NULL;
- list->free = NULL;
- list->match = NULL;
- //最終結(jié)果返回
- return list;
清空表
傳入list的指針，首先定義當(dāng)前節(jié)點(diǎn)current，使其指向頭指針，定義len，使其等于list的長(zhǎng)度。接著進(jìn)行循環(huán)，每次len減一，定義新節(jié)點(diǎn)next，始終指向當(dāng)前節(jié)點(diǎn)current的下一個(gè)節(jié)點(diǎn)，如果有值，則釋放該節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)current后移，next節(jié)點(diǎn)同樣后移。直到len為0，釋放完所有節(jié)點(diǎn)，退出循環(huán)。最后賦值list的頭節(jié)點(diǎn)head和尾節(jié)點(diǎn)tail為NULL，len為0。
注意：這邊和SDS一樣，清空并不是直接刪除list，而是刪除其數(shù)據(jù)，外層的list結(jié)構(gòu)仍然存在。這其實(shí)上是惰性刪除。
- void listEmpty(list *list)
- {
- unsigned long len;
- //定義兩個(gè)節(jié)點(diǎn)指針current和next
- listNode *current, *next;
- //當(dāng)前節(jié)點(diǎn)指針current指向list的頭節(jié)點(diǎn)位置，即list的第一個(gè)數(shù)據(jù)
- current = list->head;
- //len為list的長(zhǎng)度
- len = list->len;
- //開始循環(huán)，每次len減1
- while(len--) {
- //先讓下一個(gè)指針指向下一個(gè)節(jié)點(diǎn)，因?yàn)榈紫轮苯俞尫女?dāng)前節(jié)點(diǎn)，如果不在此處復(fù)制，底下就獲取不到了
- next = current->next;
- //釋放當(dāng)前節(jié)點(diǎn)的值
- if (list->free) list->free(current->value);
- //釋放當(dāng)前節(jié)點(diǎn)
- zfree(current);
- //當(dāng)前節(jié)點(diǎn)等于剛才的下一個(gè)節(jié)點(diǎn)next，即開始往后移，開始下一輪循環(huán)
- current = next;
- }
- //釋放完給頭指針head,尾指針tail賦值為NULL
- list->head = list->tail = NULL;
- //len賦值0
- list->len = 0;
- }
添加元素到表頭
添加元素到表頭，首先新建一個(gè)新節(jié)點(diǎn)node，判斷是否有內(nèi)存分配，如果有，則繼續(xù)，如果沒(méi)有，則返回NULL，退出方法。這邊新節(jié)點(diǎn)是用來(lái)存在輸入?yún)?shù)中的value的，所以需要內(nèi)存。接著將新節(jié)點(diǎn)node的value值賦值為輸入?yún)?shù)value。最后需要調(diào)整list的頭指針，尾指針，原來(lái)第一個(gè)節(jié)點(diǎn)的指針情況(這邊看下圖，描述起來(lái)有點(diǎn)混亂，圖片一目了然)。最最后，就是list的len加1，返回list。
舉個(gè)例子，如果要在list中插入節(jié)點(diǎn)f，首先將節(jié)點(diǎn)的頭指針賦值為空(對(duì)應(yīng)步驟1)，然后將新節(jié)點(diǎn)的尾指針next指向第一個(gè)節(jié)點(diǎn)(對(duì)應(yīng)步驟2)，將第一個(gè)節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)(對(duì)應(yīng)步驟3)，最后將list的頭指針head指向新節(jié)點(diǎn)(對(duì)應(yīng)步驟4)。這邊需要注意的是，步驟2和步驟3需要在步驟4前面，不然會(huì)找到第一個(gè)節(jié)點(diǎn)。
具體代碼如下：
- //添加一個(gè)元素到表頭
- list *listAddNodeHead(list *list, void *value)
- {
- listNode *node;
- if ((node = zmalloc(sizeof(*node))) == NULL)
- return NULL;
- node->value = value;//為當(dāng)前節(jié)點(diǎn)賦值
- //如果當(dāng)前l(fā)ist為空
- if (list->len == 0) {
- list->head = list->tail = node;//頭尾指針都指向該節(jié)點(diǎn)
- node->prev = node->next = NULL;//當(dāng)前節(jié)點(diǎn)的頭尾指針都為null
- } else {//如果當(dāng)前l(fā)ist不為空
- node->prev = NULL;//新節(jié)點(diǎn)的頭指針為null
- node->next = list->head;//新節(jié)點(diǎn)的尾指針指向原來(lái)的尾指針
- list->head->prev = node;//原來(lái)的第一個(gè)節(jié)點(diǎn)的頭指針指向新節(jié)點(diǎn)
- list->head = node;//鏈表的頭指針指向新節(jié)點(diǎn)
- }
- list->len++;//list長(zhǎng)度+1
- return list;
- }
添加元素到表尾
添加元素到表尾，首先新建一個(gè)新節(jié)點(diǎn)node，判斷是否有內(nèi)存分配，如果有，則繼續(xù)，如果沒(méi)有，則返回NULL，退出方法。這邊新節(jié)點(diǎn)是用來(lái)存在輸入?yún)?shù)中的value的，所以需要內(nèi)存。接著將新節(jié)點(diǎn)node的value值賦值為輸入?yún)?shù)value。最后需要調(diào)整list的頭指針，尾指針，原來(lái)最后一個(gè)節(jié)點(diǎn)的指針情況(這邊看下圖，描述起來(lái)有點(diǎn)混亂，圖片一目了然)。最最后，就是list的len加1，返回list。
舉個(gè)例子，如果要在list中插入節(jié)點(diǎn)f，首先將節(jié)點(diǎn)的尾指針賦值為空(對(duì)應(yīng)步驟1)，然后將新節(jié)點(diǎn)的頭指針指向最后一個(gè)節(jié)點(diǎn)(對(duì)應(yīng)步驟2)，將最后一個(gè)節(jié)點(diǎn)的next指向新節(jié)點(diǎn)(對(duì)應(yīng)步驟3)，最后將list的尾指針tail指向新節(jié)點(diǎn)(對(duì)應(yīng)步驟4)。
步驟如下：
- //添加元素到表尾
- list *listAddNodeTail(list *list, void *value)
- {
- //新建節(jié)點(diǎn)node
- listNode *node;
- //嘗試分配內(nèi)存
- if ((node = zmalloc(sizeof(*node))) == NULL)
- return NULL;
- //為新節(jié)點(diǎn)node賦值
- node->value = value;
- //調(diào)整指針
- if (list->len == 0) {
- list->head = list->tail = node;
- node->prev = node->next = NULL;
- } else {
- node->prev = list->tail;
- node->next = NULL;
- list->tail->next = node;
- list->tail = node;
- }
- //len加1
- list->len++;
- return list;
- }
插入
為list的某個(gè)節(jié)點(diǎn)old_node的after(大于0為前面新增，小于0為后面新增)新增新值value，首先新建一個(gè)新節(jié)點(diǎn)node，判斷是否有內(nèi)存分配，如果有，則繼續(xù)，如果沒(méi)有，則返回NULL，退出方法。這邊新節(jié)點(diǎn)是用來(lái)存在輸入?yún)?shù)中的value的，所以需要內(nèi)存。接著根據(jù)after的值確定是在節(jié)點(diǎn)old_node的前面新增數(shù)據(jù)，還是在節(jié)點(diǎn)old_node的后面新增數(shù)據(jù)，具體的是指針的調(diào)整。最后len加1，返回list。
- //在list的某個(gè)位置old_node的after(前后)插入value值
- list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
- listNode *node;
- if ((node = zmalloc(sizeof(*node))) == NULL)
- return NULL;
- node->value = value;
- if (after) {//大于0
- node->prev = old_node;
- node->next = old_node->next;
- if (list->tail == old_node) {
- list->tail = node;
- }
- } else {//小于0
- node->next = old_node;
- node->prev = old_node->prev;
- if (list->head == old_node) {
- list->head = node;
- }
- }
- if (node->prev != NULL) {
- node->prev->next = node;
- }
- if (node->next != NULL) {
- node->next->prev = node;
- }
- list->len++;
- return list;
- }
刪除
從list中刪除節(jié)點(diǎn)node，如果該節(jié)點(diǎn)的前面存在節(jié)點(diǎn)，使其前面一個(gè)節(jié)點(diǎn)的next指針指向node后面一個(gè)節(jié)點(diǎn)的地址，其實(shí)就是跳過(guò)了node節(jié)點(diǎn)，如果該節(jié)點(diǎn)的前面不存在節(jié)點(diǎn)，則將list的頭指針指向node的下一節(jié)點(diǎn)地址。同樣的，如果該節(jié)點(diǎn)的后面存在節(jié)點(diǎn)，邏輯一樣的。最后釋放要?jiǎng)h除的節(jié)點(diǎn)node內(nèi)存，len減1。
- //從鏈表list中刪除某個(gè)節(jié)點(diǎn)node
- void listDelNode(list *list, listNode *node)
- {
- //如果該節(jié)點(diǎn)的前面存在節(jié)點(diǎn)
- if (node->prev)
- node->prev->next = node->next;
- else
- list->head = node->next;
- //如果該節(jié)點(diǎn)的前面存在節(jié)點(diǎn)
- if (node->next)
- node->next->prev = node->prev;
- else
- list->tail = node->prev;
- //釋放當(dāng)前節(jié)點(diǎn)node的值
- if (list->free) list->free(node->value);
- //釋放內(nèi)存
- zfree(node);
- //len-1
- list->len--;
- }
總結(jié)
該篇主要講了Redis的list數(shù)據(jù)類型的底層實(shí)現(xiàn)雙向鏈表adlist，先從list的一些API使用，引出雙向鏈表數(shù)據(jù)結(jié)構(gòu)，進(jìn)而結(jié)合源碼對(duì)雙向鏈表進(jìn)行描述，包括節(jié)點(diǎn)listNode和list的頭指針和尾指針，最后針對(duì)list的往表頭插入元素，往表尾插入元素，刪除，修改等方法進(jìn)行源碼解析，使其對(duì)雙向鏈表有更清晰的認(rèn)識(shí)。
如果覺(jué)得寫得還行，麻煩給個(gè)贊👍，您的認(rèn)可才是我寫作的動(dòng)力!
