Redis系列（五）：數據結構List雙向鏈表中基本操作操作命令和源碼解析
1.介紹
List是通過ListNode實現的雙向鏈表。
1.雙端：獲取某個結點的前驅和後繼結點都是O(1)
2.無環：表頭的prev指針和表尾的next指針都指向NULL，對鏈表的訪問都是以NULL為終點
3.帶表頭指針和表尾指針：獲取表頭和表尾的複雜度都是O(1)
4.帶鏈表長度計數器：len屬性記錄，獲取鏈表長度O(1)
5.多態：鏈表結點使用void*指針來保存結點的值，並且可以通過鏈表結構的三個函數為結點值設置類型特定函數，所以鏈表可以保存各種不同類型的值
雙向鏈表詳解：//www.cnblogs.com/vic-tory/p/13140779.html
中文網：//redis.cn/commands.html#list
2.源碼解析
// listNode 雙端鏈表節點 typedef struct listNode { // 前置節點 struct listNode *prev; // 後置節點 struct listNode *next; // 節點的值 void *value; } listNode;
// list 雙端鏈表 typedef struct list { // 在c語言中,用結構體的方式來模擬對象是一種常見的手法 // 表頭節點 listNode *head; // 表尾節點 listNode *tail; // 節點值複製函數 void *(*dup)(void *ptr); // 節點值釋放函數 void(*free)(void *ptr); // 節點值對比函數 int(*match)(void *ptr, void *key); // 鏈表所包含的節點數量 unsigned long len; } list;
/* 作為宏實現的函數 */ //獲取長度 #define listLength(l) ((l)->len) //獲取頭節點 #define listFirst(l) ((l)->head) //獲取尾結點 #define listLast(l) ((l)->tail) //獲取前一個結點 #define listPrevNode(n) ((n)->prev) //獲取後一個結點 #define listNextNode(n) ((n)->next) //獲取結點的值 是一個void類型指針 #define listNodeValue(n) ((n)->value) /* 下面3個函數主要用來設置list結構中3個函數指針，參數m為method的意思 */ #define listSetDupMethod(l,m) ((l)->dup = (m)) #define listSetFreeMethod(l,m) ((l)->free = (m)) #define listSetMatchMethod(l,m) ((l)->match = (m)) /* 下面3個函數主要用來獲取list結構的單個函數指針 */ #define listGetDupMethod(l) ((l)->dup) #define listGetFree(l) ((l)->free) #define listGetMatchMethod(l) ((l)->match)
3.API實現
listCreate函數：創建一個不包含任何結點的新鏈表
/* * listCreate 創建一個新的鏈表 * * 創建成功返回鏈表，失敗返回 NULL 。 * * T = O(1) */ list *listCreate(void) { struct list *list; // 分配記憶體 if ((list = zmalloc(sizeof(*list))) == NULL) return NULL;//記憶體分配失敗則返回NULL // 初始化屬性 list->head = list->tail = NULL;//空鏈表 list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; return list; }
listAddNodeHead函數：將一個包含給定值的新結點添加到給定鏈表的表頭
/* * listAddNodeHead 將一個包含有給定值指針 value 的新節點添加到鏈表的表頭 * * 如果為新節點分配記憶體出錯，那麼不執行任何動作，僅返回 NULL * * 如果執行成功，返回傳入的鏈表指針 * * T = O(1) */ list *listAddNodeHead(list *list, void *value) { listNode *node; // 為節點分配記憶體 if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; // 保存值指針 node->value = value; // 添加節點到空鏈表 if (list->len == 0) { list->head = list->tail = node; //該結點的前驅和後繼都為NULL node->prev = node->next = NULL; } else { // 添加節點到非空鏈表 node->prev = NULL; node->next = list->head; list->head->prev = node; list->head = node; } // 更新鏈表節點數 list->len++; return list; }
listAddNodeTail函數：將一個包含給定值的新結點插入到給定鏈表的表尾
/* * listAddNodeTail 將一個包含有給定值指針 value 的新節點添加到鏈表的表尾 * * 如果為新節點分配記憶體出錯，那麼不執行任何動作，僅返回 NULL * * 如果執行成功，返回傳入的鏈表指針 * * T = O(1) */ list *listAddNodeTail(list *list, void *value) { listNode *node; // 為新節點分配記憶體 if ((node = zmalloc(sizeof(*node))) == NULL) return NULL; // 保存值指針 node->value = value; // 目標鏈表為空 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; } // 更新鏈表節點數 list->len++; return list; }
listInsertNode函數：將一個給定值的新結點插入到給定結點之前或者之後
/* * listInsertNode 創建一個包含值 value 的新節點，並將它插入到 old_node 的之前或之後 * * 如果 after 為 0 ，將新節點插入到 old_node 之前。 * 如果 after 為 1 ，將新節點插入到 old_node 之後。 * * T = O(1) */ 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) { node->prev = old_node; node->next = old_node->next; // 給定節點是原表尾節點 if (list->tail == old_node) { list->tail = node; } } // 將新節點添加到給定節點之前 else { 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; }
listDelNode函數：從指定的list中刪除給定的結點
/* * listDelNode 從鏈表 list 中刪除給定節點 node * * 對節點私有值(private value of the node)的釋放工作由調用者進行。該函數一定會成功. * * T = O(1) */ void listDelNode(list *list, listNode *node) { // 調整前置節點的指針 if (node->prev) node->prev->next = node->next; else list->head = node->next; // 調整後置節點的指針 if (node->next) node->next->prev = node->prev; else list->tail = node->prev; // 釋放值 if (list->free) list->free(node->value); // 釋放節點 zfree(node); // 鏈表數減一 list->len--; }
listRelease函數：釋放給定鏈表以及鏈表中所有結點
/* * listRelease 釋放整個鏈表，以及鏈表中所有節點, 這個函數不可能會失敗. * * T = O(N) */ void listRelease(list *list) { unsigned long len; listNode *current, *next; // 指向頭指針 current = list->head; // 遍歷整個鏈表 len = list->len; while (len--) { next = current->next; // 如果有設置值釋放函數，那麼調用它 if (list->free) list->free(current->value); // 釋放節點結構 zfree(current); current = next; } // 釋放鏈表結構 zfree(list); }
該函數不僅釋放了表結點的記憶體還釋放了表結構的記憶體
listGetIterator函數：為給定鏈表創建一個迭代器
在講這個函數之前，我們應該先看看鏈表迭代器的結構：
// listIter 雙端鏈表迭代器 typedef struct listIter { // 當前迭代到的節點 listNode *next; // 迭代的方向 int direction; } listIter;
迭起器只有兩個重要的屬性：當前迭代到的結點，迭代的方向
下面再看看鏈表的迭代器創建函數
/* * listGetIterator 為給定鏈表創建一個迭代器， * 之後每次對這個迭代器調用 listNext 都返回被迭代到的鏈表節點,調用該函數不會失敗 * * direction 參數決定了迭代器的迭代方向： * AL_START_HEAD ：從表頭向表尾迭代 * AL_START_TAIL ：從表尾想表頭迭代 * * T = O(1) */ listIter *listGetIterator(list *list, int direction) { // 為迭代器分配記憶體 listIter *iter; if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL; // 根據迭代方向，設置迭代器的起始節點 if (direction == AL_START_HEAD) iter->next = list->head; else iter->next = list->tail; // 記錄迭代方向 iter->direction = direction; return iter; }
listReleaseIterator函數：釋放指定的迭代器
/* * listReleaseIterator 釋放迭代器 * * T = O(1) */ void listReleaseIterator(listIter *iter) { zfree(iter); }
listRewind函數和listRewindTail函數：迭代器重新指向表頭或者表尾的函數
/* * 將迭代器的方向設置為 AL_START_HEAD, * 並將迭代指針重新指向表頭節點。 * * T = O(1) */ void listRewind(list *list, listIter *li) { li->next = list->head; li->direction = AL_START_HEAD; } /* * 將迭代器的方向設置為 AL_START_TAIL, * 並將迭代指針重新指向表尾節點。 * * T = O(1) */ void listRewindTail(list *list, listIter *li) { li->next = list->tail; li->direction = AL_START_TAIL; }
listNext函數：返回當前迭代器指向的結點
/* * 返回迭代器當前所指向的節點。 * * 刪除當前節點是允許的,但不能修改鏈表裡的其他節點。 * * 函數要麼返回一個節點,要麼返回 NULL,常見的用法是： * * iter = listGetIterator(list,<direction>); * while ((node = listNext(iter)) != NULL) { * doSomethingWith(listNodeValue(node)); * } * * T = O(1) */ listNode *listNext(listIter *iter) { listNode *current = iter->next; if (current != NULL) { // 根據方向選擇下一個節點 if (iter->direction == AL_START_HEAD) // 保存下一個節點，防止當前節點被刪除而造成指針丟失 iter->next = current->next; else // 保存下一個節點，防止當前節點被刪除而造成指針丟失 iter->next = current->prev; } return current; }
該函數保持了當前結點的下一個結點，避免了當前結點被刪除而迭代器無法繼續迭代的尷尬情況
listDup函數：複製整個鏈表，返回副本
/* * 複製整個鏈表。 * * 複製成功返回輸入鏈表的副本， * 如果因為記憶體不足而造成複製失敗，返回 NULL 。 * * 如果鏈表有設置值複製函數 dup ，那麼對值的複製將使用複製函數進行， * 否則，新節點將和舊節點共享同一個指針。 * * 無論複製是成功還是失敗，輸入節點都不會修改。 * * T = O(N) */ list *listDup(list *orig) { list *copy;//鏈表副本 listIter *iter;//鏈表迭代器 listNode *node;//鏈表結點 // 創建新的空鏈表 if ((copy = listCreate()) == NULL) return NULL;//創建空的鏈表失敗則返回NULL // 設置副本鏈表的節點值處理函數 copy->dup = orig->dup; copy->free = orig->free; copy->match = orig->match; //獲取輸入鏈表的迭代器 iter = listGetIterator(orig, AL_START_HEAD); //遍歷整個輸入鏈表進行複製 while ((node = listNext(iter)) != NULL) { //副本結點值 void *value; // 存在複製函數 if (copy->dup) { //調用複製函數複製 value = copy->dup(node->value); //複製結果為空，說明複製失敗 if (value == NULL) { //複製失敗則釋放副本鏈表和迭代器，避免記憶體泄漏 listRelease(copy); listReleaseIterator(iter); return NULL; } } //不存在複製函數 則直接指針指向 else value = node->value; // 將節點添加到副本鏈表 if (listAddNodeTail(copy, value) == NULL) { //如果不能成功添加，則釋放副本鏈表和迭代器，避免記憶體泄漏 listRelease(copy); listReleaseIterator(iter); return NULL; } } // 釋放迭代器 listReleaseIterator(iter); // 返回副本 return copy; }
如果複製失敗則要注意釋放副本鏈表和迭代器，避免記憶體泄漏
listSearchKey函數：查找list中值和key匹配的結點
/* * 查找鏈表 list 中值和 key 匹配的節點。 * * 對比操作由鏈表的 match 函數負責進行， * 如果沒有設置 match 函數， * 那麼直接通過對比值的指針來決定是否匹配。 * * 如果匹配成功，那麼第一個匹配的節點會被返回。 * 如果沒有匹配任何節點，那麼返回 NULL 。 * * T = O(N) */ listNode *listSearchKey(list *list, void *key) { listIter *iter;//鏈表迭代器 listNode *node;//鏈表結點 //獲得鏈表迭代器 iter = listGetIterator(list, AL_START_HEAD); //遍歷整個鏈表查詢 while ((node = listNext(iter)) != NULL) { //存在比較函數 if (list->match) { //利用比較函數進行比較 if (list->match(node->value, key)) { //返回目標結點之前釋放迭代器空間，避免記憶體泄漏 listReleaseIterator(iter); return node; } } //不存在比較函數 else { //直接比較 if (key == node->value) { //返回目標結點之前釋放迭代器空間，避免記憶體泄漏 listReleaseIterator(iter); // 找到 return node; } } } //返回目標結點之前釋放迭代器空間，避免記憶體泄漏 listReleaseIterator(iter); // 未找到 return NULL; }
listIndex函數：返回鏈表在給定索引上的值
/* * 返回鏈表在給定索引上的值。 * * 索引以 0 為起始，也可以是負數， -1 表示鏈表最後一個節點，諸如此類。 * * 如果索引超出範圍(out of range),返回 NULL 。 * * T = O(N) */ listNode *listIndex(list *list, long index) { listNode *n;//鏈表結點 /* n不用設置成NULL的原因： 如果索引超出範圍， 那肯定是找到表頭或者表尾沒有找到， 表頭的前驅和表尾的後繼都是NULL， 所以這裡n不用設置為NULL，直接設置也可以*/ // 如果索引為負數，從表尾開始查找 if (index < 0) { //變成正數，方便索引 index = (-index) - 1; //從尾部開始找 n = list->tail; //尋找 因為從尾部開始找，所以是前驅 while (index-- && n) n = n->prev; } // 如果索引為正數，從表頭開始查找 else { //從頭部開始找 n = list->head; //尋找 因為從頭部開始找，所以是後繼 while (index-- && n) n = n->next; } return n; }
listRotate函數：取出鏈表的表尾結點放到表頭，成為新的表頭結點
/* * 取出鏈表的表尾節點，並將它移動到表頭，成為新的表頭節點。 * * T = O(1) */ void listRotate(list *list) { //表尾結點 listNode *tail = list->tail; //如果鏈表中只有一個元素，那麼表頭就是表尾，可以直接返回 if (listLength(list) <= 1) return; // 重新設置表尾節點 list->tail = tail->prev; list->tail->next = NULL; // 插入到表頭 list->head->prev = tail; tail->prev = NULL; tail->next = list->head; list->head = tail; }
