链表的实现方式有很多种，常见的主要有三个，单向链表、双向链表、循环链表。
1、单链表
1-1
- 结构：第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
- 优点：链表特性 插入和删除方便，只需要考虑相邻节点指针的变化，因此为常数级时间复杂度O(1)
- 缺点：查找慢，需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点，因此时间复杂度为O(N)。
2、双向链表
1-2
- 结构：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
- 优点：链表特性 插入和删除方便
- 在有序链表中查找某个元素，单链表由于只有后继指针，因此只能从前往后遍历查找时间复杂度为O(N)，而双向链表可以双向遍历。
- 删除给定指针指向的结点。假设已经找到要删除的节点，要删除就必须知道其前驱节点和后继节点，单链表想要知道其前驱节点只能从头开始遍历，时间复杂度为0(n)，而双向链表由于保存了其前驱节点的地址，因此时间复杂度为0(1)。
- 缺点：查找慢，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
3、循环链表
1-3
- 结构：一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
- 优点：在于链尾到链头，链头到链尾比较方便适合处理的数据具有环型结构特点。获取第一个节点时间复杂度为O(1)，那么获取最后一个节点也为O(1) 如 获取栈顶、栈底、队头、队尾等操作
- 缺点：和其他链表差不多
redis 的链表结构（adlist.h）
//节点
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
//迭代器
typedef struct listIter {
listNode *next;
int direction;
} listIter;
//list 结构
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 链表是双向链表
/* Add a new node to the list, to head, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
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;
node->prev = node->next = NULL;
} else {
// 将头节点的prev赋值为NULL
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++;
return list;
}
/* Add a new node to the list, to tail, containing the specified 'value'
* pointer as value.
*
* On error, NULL is returned and no operation is performed (i.e. the
* list remains unaltered).
* On success the 'list' pointer you pass to the function is returned. */
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;
// 将头节点的next赋值为NULL
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len++;
return list;
}
从listAddNodeTail 和listAddNodeHead 可以看出redis 双向链表是无环的。
结构特性如下：（网上都这么说）
- 双端： 链表节点带有
prev和next指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) - 无环： 表头节点的
prev指针和表尾节点的next指针都指向NULL， 对链表的访问以NULL为终点。 - 带表头指针和表尾指针： 通过
list结构的head指针和tail指针， 程序获取链表的表头节点和表尾节点的复杂度为O(1)。 - 带链表长度计数器： 程序使用
list结构的len属性来对list持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1)。 - 多态： 链表节点使用
void*（“无类型指针”，可以指向任何数据类型） 指针来保存节点值， 并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。
总结
- 采用双向无环链表而没有采用其他链表 很显然是一种权衡的策略，那空间来减少链表的查询慢的缺点，典型空间换时间。
- 这种结构跟我们在Java中使用的LinkedList 类似。（链表不都这样吗？）
应用
除了实现列表类型以外， 双端链表还被很多 Redis 内部模块所应用：
- 事务模块使用双端链表依序保存输入的命令；
- 服务器模块使用双端链表来保存多个客户端；
- 订阅/发送模块使用双端链表来保存订阅模式的多个客户端；
- 事件模块使用双端链表来保存时间事件（time event）；
