（一）什么是链表？
链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。
所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。
1、那么先从单向链表着手，先看看单向链表的模拟图：
image.png
单向链表包含两个域，一个是信息域，一个是指针域。也就是单向链表的节点被分成两部分，一部分是保存或显示关于节点的信息，第二部分存储下一个节点的地址，而最后一个节点则指向一个空值。
2、双向链表：
image.png
从上图可以很清晰的看出，每个节点有2个链接，一个是指向前一个节点（当此链接为第一个链接时，指向的是空值或空列表），另一个则指向后一个节点（当此链接为最后一个链接时，指向的是空值或空列表）。意思就是说双向链表有2个指针，一个是指向前一个节点的指针，另一个则指向后一个节点的指针。
3、循环链表：
image.png
循环链表就是首节点和末节点被连接在一起。循环链表中第一个节点之前就是最后一个节点，反之亦然。
YYCache用到的双向链表
键值对存储操作
通过创建链表节点node，进行间接操作数据
#pragma mark - _YYLinkedMapNode
@interface _YYLinkedMapNode : NSObject {
// 类似C中的private_extern，使用@private的话，限制太大，@package在类的镜像外进行引用就会报错
// 使用@public @protect等的话，就没什么限制的
// 目的是，限制在本文件中使用
@package
__unsafe_unretained _YYLinkedMapNode *_prev; // 通过dic进行持有
__unsafe_unretained _YYLinkedMapNode *_next; // 通过dic进行持有
id _key;
id _value;
NSUInteger _cost;
NSTimeInterval _time;
}
@end
https://blog.csdn.net/Jasmine_shine/article/details/44033947
