一个链表节点的结构
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
链表
/*
* 双端链表结构
*/
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
Redis的链表
- 双端：链表节点带有prev和next指针，获得节点的前置或后置节点复杂福都是O(1)
- 无环：表头节点的prev指针和表尾节点的next指针都指向NULL
- 带链表长度计数器
网友评论