双向链表 + LRU淘汰算法 + 线程安全

双向链表的设计

用OC来设计双向链表（不是循环链表）

单个节点

image.png

整个链表

image.png

备注：

• ->是啥：如果我们手动开辟一个结构体，再给他的元素设置值，需要加上这个，举个栗子：

//使用系统的方法创建结构体，直接用'.'就可以
CGPoint p = CGPointMake(42,42);
NSLog(@"%f", p.x);

//手动创建一个结构体，获取他的元素需要用'->'
CGPoint *p = malloc(1*sizeof(CGPoint));
p->x = 2.0;
NSLog(@"%f", p->x);
free(p);

退一万步说，结构体p是一個不完整的地址，里面的x、y就是地址偏移量，p->x其实拿到的是偏移量的地址，也就是指向x的指针

LRU

1.算法思想

Least Recently Used 近期最少使用算法， 常应用于缓存中的数据淘汰， 其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高“。

2.插入数据

• 新数据在链表中存在（一般称为命中），则把该节点移到链表头部
• 新数据在链表中不存在，则新建一个节点，放到链表头部
• 若缓存满了，则把链表最后一个节点删除

3.读取数据

• 数据在链表中存在，则把该节点移到链表头部
• 数据在链表中不存在，返回-1

附录：

• Core Foundation对象，简称CF，可不是穿越火线哦，这个嘛，需要自己创建，自己释放，比如CFMutableDictionaryRef，创建方法是CFDictionaryCreateMutable，释放方法是CFRelease
• CF和OC对象转化
  OC->CF:加__bridge，举例如下：

id p;
void * key;
key = (__bridge const void *)p

CF->OC:加__bridge_transfer，举例如下：

id obj = (__bridge_transfer id)p;