1.介紹
Redis中List是通過ListNode構造的雙向鏈表。
特點：
1.雙端：獲取某個結點的前驅和後繼結點都是O(1)
2.無環：表頭的prev指針和表尾的next指針都指向NULL，對鏈表的訪問都是以NULL為終點
3.帶表頭指針和表尾指針：獲取表頭和表尾的複雜度都是O(1)
4.帶鏈表長度計數器：len屬性記錄，獲取鏈表長度O(1)
5.多態：鏈表結點使用void*指針來保存結點的值，並且可以通過鏈表結構的三個函數為結點值設置類型特定函數，所以鏈表可以保存各種不同類型的值
雙向鏈表詳解：https://www.cnblogs.com/vic-tory/p/13140779.html
中文網：http://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;
}
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能
※台北網頁設計公司這麼多該如何選擇?
※智慧手機時代的來臨，RWD網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※回頭車貨運收費標準
※聚甘新
