共计 1018 个字符，预计需要花费 3 分钟才能阅读完成。
链表的作用
首先我们知道，链表提供了高效的节点重排能力、顺序性的访问方式、灵活的增删节点并调整链表的长度。作为一种常用的数据结构，在很多高级的编程语言里都可以看到。实现的方式大同小异。
与数组的比较
从内存空间来看，数组是一个连续的内存空间属于连续存储存储形式。而链表则是离散存储的存储形式，有一个指针指向一个节点。所以意味着链表在内存中可以是离散的。就从内存存储方式来看，数组是一个连续的空间，查询更快，更加适合使用序列来访问数组元素。而链表更适对线性表长度无法确定，频繁的插入删除操作的动态性比较强的线性表。下图可见，数组和链表的存储形式。
数组
链表
a
other
b
a
c
other
d
b
e
other
nil
c
节点的定义
首先我们看一下节点的定义。prev 记录前一个节点的指针 next 记录下一个节点的指针 value 记录节点的阵阵的值这样如果你知道第一个节点就能完整的把整个链表循环显示出来。其实目前来看整个链表的结构已经出现了，多个 listNode 通过 prev next 就可以连起来行程一个链表。但是 redis 中的链表还对 listNode 进行了一个封装，增加了一些冗余字段来提高访问的性能，跟上一篇文章说的 SDS 有相似地方。
typedef struct listNode{
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
}
Redis 中的 list
在 redis 中对 listNode 再次封装了下，使用了一个 list。下面我们看下代码：可以看到跟 SDS 类似，多了一个表头，表尾，数量和 3 个函数。这几个属性能够达到什么效果呢？这 3 个函数可以说是对链表最常用的函数，使用起来十分的方便。链表数量作用跟 SDS 相似，可以用 O(1) 的复杂度获取整个链表的长度，表头和表尾可以快速的在表头和表尾添加元素。否则如果要在最后添加需要循环整个链表拿到尾节点，改变尾节点的 next 添加新节点。在 redis 中使用链表，几乎都是使用 list。
typedef struct list{
// 链表头
listNode *head;
// 链表尾
listNode *tail;
// 链表数量
unsigned long len;
// 节点复制韩式布
vode *(*dup) (void *ptr);
// 节点释放
vode *(*free) (void *ptr);
// 节点对比
vode *(*match) (void *ptr,void *key);
}
