链表
对比一下数组 链表这块的话 不需要一块连续的存储空间 只需要“指针”把一组零散的内存块串联起来使用，有效利用了空间
常见的有三种： 单链表、双链表、循环链表
内存块称之为链表的“结点”，为了将所有的节点串联起来，每个链表的节点除了存储数据之外，还需要记录链表的下一个节点的地址，这个记录下个节点地址的指针叫做后继指针next。
双链表节点 还有前驱指针prev
在链表中插入和删除 不需要为了保持内存的连续性而搬移结点，因此插入和删除比较高效。
循环链表是一种特殊的链表 区别在于尾结点
单链表的尾结点指向空地址，而循环链表尾结点指向链表的头结点。像一个环一样首尾相连。
优点在于从链表尾到链表头比较方便，比如约瑟夫问题，使用循环链表就非常方便。
虽然双向链表比较浪费存储空间，但是也带来了 双向的灵活性
java当中的LinkedHashMap这个容器就使用了双链表这种数据结构
为什么使用这个？
一个原因就是使用 空间换时间！！
在内存空间充足的时候，我们使用空间换时间；
内存如果比较紧缺的话，我们就用时间换空间。
缓存本质就是使用空间换时间的设计思想，数据存储在硬盘，比较节省内存。但是查找不是很方便，可以通过缓存的技术，事先将数据加载在内存中，这样虽然比较耗费内存空间，但是每次数据查询的速度就大大提升了。
数组使用连续内存 借助cpu的缓存机制 预读数组中的数据 访问效率更高。数组缺点是大小固定，容易内存不足。
链表中的结点在被频繁插入、删除的操作情况下 容易造成内存碎片，使用java会导致频繁的gc。