Redis中雙鏈表實現(xiàn)的基本結(jié)構(gòu)：
1.節(jié)點(diǎn)結(jié)構(gòu)
typedef struct listNode {
struct listNode *prev; //前向節(jié)點(diǎn)
struct listNode *next; //后向節(jié)點(diǎn)
void *value; //該節(jié)點(diǎn)的值
} listNode;
2.雙向鏈表結(jié)構(gòu)
typedef struct list {
listNode *head; //頭節(jié)點(diǎn)
listNode *tail; //尾節(jié)點(diǎn)
void *(*dup)(void *ptr); //復(fù)制函數(shù)
void (*free)(void *ptr); //釋放函數(shù)
int (*match)(void *ptr, void *key); //匹配函數(shù)，查找節(jié)點(diǎn)使用
unsigned long len; //雙向鏈表的長度即節(jié)點(diǎn)的個數(shù)
} list;
3.雙向鏈表遍歷器
typedef struct listIter {
listNode *next; //下一個節(jié)點(diǎn)
int direction;
} listIter;
方向定義
#define AL_START_HEAD 0 //向前查找
#define AL_START_TAIL 1 //向后查找
4.宏定義函數(shù)
#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)
#define listNodeValue(n) ((n)->value)
#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))
#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)
5.定義函數(shù)
list *listCreate(void); //創(chuàng)建一個新的鏈表。該鏈表可以使用AlFree（）方法釋放。
//但使用AlFree（）方法前需要釋放用戶釋放私有節(jié)點(diǎn)的值。
//如果沒有創(chuàng)建成功，返回null；創(chuàng)建成功則返回指向新鏈表的指針。
void listRelease(list *list); //釋放整個鏈表，此函數(shù)不會執(zhí)行失敗。調(diào)用zfree(list *list)方法,定義在Zmalloc.c中。
list *listAddNodeHead(list *list, void *value); //向鏈表頭部中增加一個節(jié)點(diǎn)
list *listAddNodeTail(list *list, void *value); //向鏈表尾部增加一個節(jié)點(diǎn)
list *listInsertNode(list *list, listNode *old_node, void *value, int after);//向某個節(jié)點(diǎn)位置插入節(jié)點(diǎn) after為方向
void listDelNode(list *list, listNode *node);//從鏈表上刪除特定節(jié)點(diǎn)，調(diào)用者釋放特定私用節(jié)點(diǎn)的值。
//該函數(shù)不會執(zhí)行失敗
listIter *listGetIterator(list *list, int direction);//返回某個鏈表的迭代器。
//迭代器的listNext（）方法會返回鏈表的下個節(jié)點(diǎn)。direction是方向
//該函數(shù)不會執(zhí)行失敗。
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter); //釋放迭代器的內(nèi)存。
list *listDup(list *orig); //復(fù)制整個鏈表。當(dāng)內(nèi)存溢出時返回null，成功時返回原鏈表的一個備份
//不管該方法是否執(zhí)行成功，原鏈表不會改變。
listNode *listSearchKey(list *list, void *key); //從特定的鏈表查找key。成功則返回第一個匹配節(jié)點(diǎn)的指針
//如果沒有匹配，則返回null。
listNode *listIndex(list *list, long index); //序號從0開始，鏈表的頭的索引為0.1為頭節(jié)點(diǎn)的下個節(jié)點(diǎn)。一次類推。
//負(fù)整數(shù)用來表示從尾部開始計數(shù)。-1表示最后一個節(jié)點(diǎn)，-2倒數(shù)第二個節(jié)點(diǎn)
//如果超過鏈表的索引，則返回null
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL;
}
void listRotate(list *list); //旋轉(zhuǎn)鏈表，移除尾節(jié)點(diǎn)并插入頭部。
list結(jié)構(gòu)和listNode結(jié)構(gòu)的API
list和listNode都有它們自己的一族API，這里貼出來學(xué)習(xí)一下redis的源碼(ps:下面的代碼都是我仿照redis改寫能直接編譯運(yùn)行的代碼)
list *listCreate(void)
/**
* 創(chuàng)建一個新列表
*
* T = O(1)
*/
list *listCreate(void)
{
struct list *list;
// 為列表結(jié)構(gòu)分配內(nèi)存
list = (struct list *)malloc(sizeof(struct list));
if (list == NULL)
return NULL;
// 初始化屬性
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
void listRelease(list *list)
/**
* 釋放整個列表
*
* T = O(N), N為列表長度
*/
void listRelease(list *list)
{
unsigned long len;
listNode *current, *next;
current = list->head;
len = list->len;
while (len --) {
next = current->next;
// 如果列表有自帶的free方法，那么先對節(jié)點(diǎn)值調(diào)用它
if (list->free) list->free(current->value);
// 之后釋放節(jié)點(diǎn)
free(current);
current = next;
}
free(list);
}
list *listAddNodeHead(list *list, void *value)
/**
* 新建一個包含給定value的節(jié)點(diǎn)，并將它加入到列表的表頭
*
* T = O(1)
*/
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
// 第一個節(jié)點(diǎn)
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
// 不是第一個節(jié)點(diǎn)
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len ++;
return list;
}
list *listAddNodeTail(list *list, void *value)
/**
* 新建一個包含給定value的節(jié)點(diǎn)，并把它加入到列表的表尾
*
* T = O(1)
*/
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
if (list->len == 0) {
// 第一個節(jié)點(diǎn)
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
// 不是第一節(jié)點(diǎn)
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len ++;
return list;
}
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
/**
* 創(chuàng)建一個包含值value的節(jié)點(diǎn)
* 并根據(jù)after參數(shù)的指示，將新節(jié)點(diǎn)插入到old_node的之前或者之后
*
* T = O(1)
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after)
{
listNode *node;
node = (listNode *)malloc(sizeof(listNode));
if (node == NULL)
return NULL;
if (after) {
// 插入到old_node之后
node->prev = old_node;
node->next = old_node->next;
// 處理表尾節(jié)點(diǎn)
if (list->tail == old_node) {
list->tail = node;
}
} else {
// 插入到old_node之前
node->next = old_node;
node->prev = old_node->prev;
// 處理表頭節(jié)點(diǎn)
if (list->head == old_node) {
list->head = node;
}
}
// 更新前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)的指針(這個地方很經(jīng)典，節(jié)約代碼)
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
// 更新列表節(jié)點(diǎn)
list->len ++;
return list;
}
void listDelNode(list *list, listNode *node)
/**
* 釋放列表中給定的節(jié)點(diǎn)
*
* T = O(1)
*/
void listDelNode(list *list, listNode *node)
{
// 處理前驅(qū)節(jié)點(diǎn)指針
if (node->prev) {
node->prev->next = node->next;
} else {
list->head = node->next;
}
// 處理后繼節(jié)點(diǎn)
if (node->next) {
node->next->prev = node->prev;
} else {
list->tail = node->prev;
}
// 釋放節(jié)點(diǎn)值
if (list->free) list->free(node->value);
// 釋放節(jié)點(diǎn)
free(node);
// 更新列表節(jié)點(diǎn)數(shù)目
list->len --;
}
迭代器
其實我對迭代器的概念非常陌生，因為我是純c程序員，不會c++，這里直接跟著學(xué)了！
Redis針對list結(jié)構(gòu)實現(xiàn)了一個迭代器，用于對鏈表進(jìn)行遍歷
迭代器的結(jié)構(gòu)定義如下：
/**
* 鏈表迭代器
*/
typedef struct listIter {
// 下一節(jié)點(diǎn)
listNode *next;
// 迭代方向
int direction;
} listIter;
direction決定了迭代器是沿著next指針向后迭代，還是沿著prev指針向前迭代，這個值可以是adlist.h中的AL_START_HEAD常量或AL_START_TAIL常量：
#define AL_START_HEAD 0
#define AL_START_TAIL 1
學(xué)習(xí)一下迭代器的api實現(xiàn)：
listIter *listGetIterator(list *list, int direction)
/**
* 創(chuàng)建列表list的一個迭代器，迭代方向由參數(shù)direction決定
*
* 每次對迭代器listNext(),迭代器返回列表的下一個節(jié)點(diǎn)
*
* T = O(1)
*/
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
iter = (listIter *)malloc(sizeof(listIter));
if (iter == NULL)
return NULL;
// 根據(jù)迭代器的方向，將迭代器的指針指向表頭或者表尾
if (direction == AL_START_HEAD) {
iter->next = list->head;
} else {
iter->next = list->tail;
}
// 記錄方向
iter->direction = direction;
return iter;
}
void listRewind(list *list, listIter *li)
/**
* 將迭代器iter的迭代指針倒回list的表頭
*
* T = O(1)
*/
void listRewind(list *list, listIter *li)
{
li->next = list->head;
li->direction = AL_START_HEAD;
}
void listRewindTail(list *list, listIter *li)
/**
* 將迭代器iter的迭代指針倒回list的表尾
*
* T = O(1)
*/
void listRewindTail(list *list, listIter *li)
{
li->next = list->tail;
li->direction = AL_START_TAIL;
}
listNode *listNext(listIter *iter)
/**
* 函數(shù)要么返回當(dāng)前節(jié)點(diǎn)，要么返回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) {
// 根據(jù)迭代方向，選擇節(jié)點(diǎn)
if (iter->direction == AL_START_HEAD)
iter->next = current->next;
else
iter->next = current->prev;
}
return current;
}
您可能感興趣的文章:- 詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計與實現(xiàn)
- C++ 雙鏈表的基本操作(詳解)
- Node.js環(huán)境下JavaScript實現(xiàn)單鏈表與雙鏈表結(jié)構(gòu)
- javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)嵗斀?/li>
- 簡單介紹線性表以及如何實現(xiàn)雙鏈表
- PHP 雙鏈表(SplDoublyLinkedList)簡介和使用實例
- C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
- C/C++ 雙鏈表之逆序的實例詳解
