一個鏈表節(jié)點的結(jié)構(gòu)
typedef struct listNode {
// 前置節(jié)點
struct listNode *prev;
// 后置節(jié)點
struct listNode *next;
// 節(jié)點的值
void *value;
} listNode;
鏈表
/*
* 雙端鏈表結(jié)構(gòu)
*/
typedef struct list {
// 表頭節(jié)點
listNode *head;
// 表尾節(jié)點
listNode *tail;
// 節(jié)點值復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
// 節(jié)點值對比函數(shù)
int (*match)(void *ptr, void *key);
// 鏈表所包含的節(jié)點數(shù)量
unsigned long len;
} list;
Redis的鏈表
- 雙端：鏈表節(jié)點帶有prev和next指針惠豺，獲得節(jié)點的前置或后置節(jié)點復(fù)雜福都是O(1)
- 無環(huán)：表頭節(jié)點的prev指針和表尾節(jié)點的next指針都指向NULL
- 帶鏈表長度計數(shù)器
