一、链表
1.什么是链表
和数组一样，链表也是一种线性表从内存结构上看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构链表中的每一个内存块被称为节点Node，节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next
2.常见的缓存策略
先进先出策略FIFO (First In,First Out)最少使用策略LFU (Least Frequently Used)最近最小使用策略LRU(Least Recently Used)
3.常见的三种链表结构
单链表
每个节点只包含一个指针，即后继指针单链表有两个特殊的节点，即首节点和尾节点。用首节点地址表示整条链表，用尾节点的后继指针指向空指针地址null性能特点：插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)双向链表
节点除了存储数据外，还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)首节点的前驱指针prev和尾节点的后继指针均指向空地址循环链表
除了尾节点的后继指针指向首节点的地址外，均与单链表一致试用于存储有循环特点的数据，比如约瑟夫问题。
4.数组和链表的区别
最直观的区别是数据需要一块连续的内存空间，对内存的要求比较高，如果我们申请一个100MB大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。而链表恰恰相反，它并不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用，所以如果我们申请的是100MB大小的链表，是不会有问题的。
复杂度对比：
时间复杂度数组链表
插入删除O(n)O(1)随机访问O(1)O(n)链表相对于数组来说，内存空间消耗更大，因为需要额外的空间存储指针信息，对链表进行频繁的插入和删除操作，回导致频繁的内存申请和释放，容易造成内存碎片，在java中回造成频繁的GC操作
转载于:https://www.cnblogs.com/jakaBlog/p/11284518.html
相关资源：数据结构与算法分析—C语言描述 高清版
