基础数据结构之链表
链表（Linked List）
介绍
下图（1-4）为LinkedList在Redis中的实现：
// 节点
typedef struct listNode
{
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 值
void *value;
} listNode;
// 链表
typedef struct list
{
// 头节点
listNode *head;
// 尾节点
listNode *tail;
// 节点数
unsigned long len;
// 复制函数
void *(*dup)(void *ptr);
// 释放函数
void (*free)(void *ptr);
// 比较函数
int (*match)(void *ptr, void *key);
}
Redis使用listNode存储节点值，使用list操作链表，两者组合实现了一个双向动态链表。
下图（1-5）为链表在内存中的结构：
下表（1-6）表述了Linked List实现和其特点之间的关系
| list | head | O(1)获取头节点 |
| tail | O(1)获取尾节点 | |
| len | O(1)获取链表长度 | |
| listNode | prev | 头节点为NULL，无环；双向； |
| next | 尾节点为NULL,无环；双向； | |
| value | void，多态，可保存各种类型的值； |
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻