什么是链表
是一种将一组零散的内存块串联起来使用的数据结构。
与数组的区别
数组需要一块连续的内存空间，而链表不需要。
假如现在剩余的内存空间为100M，但是内存空间并不连续，这时候我们是不能申请一个100M的数组的，但是可以申请一个100M的链表。
常见的链表
单链表
链表是零散的内存块串联起来使用的，每个内存块就是一个结点，结点除了需要存储数据之外，还需要记录链表下一个结点的地址，这个记录下个结点的指针叫后继指针next。
单链表还有两个特殊的结点，头结点（第一个结点）和尾结点（最后一个结点）。
头结点详细理解
头结点不是必须存在的，但是头指针是必须存在的。
尾结点
尾结点的next指针指向一个空地址NULL。
单链表的整个删除操作的时间复杂度为O(n)。因为假如我们要删除第n个结点的数据，我们需要找到n前面的结点才能确定n的内存地址，所以查找n的时间复杂度为O(n),找到n直接删除结点，时间复杂度为O(1),所以整个删除的操作的时间复杂度为O(n)。
循环链表
循环链表的特点就是尾结点的next指针指向头结点。
双向链表
双向链表结构就是比单向链表多出一个指针，前驱指针指向当前结点的前驱结点。双向链表是最常用的链表结构，因为其比单向链表更为高效。
例：我们删除一个链表的第k（k是已知结点）个位置的结点。如果这个链表是单向链表，那么我们需要先遍历这个链表找到k的前驱结点才能获取的k的内存地址，这个遍历的时间复杂度为O(n)。但是这个链表为双向链表的话，它本身就有指向前驱结点的指针，不需要遍历所以时间复杂度为O(1)。
双向链表采用的就是用空间换时间的设计思想，当空间足够大的时候通常采用这种设计思想。相反当空间紧张的时候会采取时间换空间的设计思想。
链表和数组的性能比较
链表
插入和删除的时间复杂度为O(1)，内存空间是不连续的，不支持CPU的缓存机制，天然支持动态扩容。
数组
插入和删除的时间复杂度为O(n)，内存空间是连续的，支持CPU的缓存机制，预读数组中的数据，访问效率更高，不支持动态扩容。
练习1：实现一个基于链表的LRU缓存淘汰算法的思路
维护一个单向链表，越靠近尾部的数据就是越早之前访问的数据，当有一个新的访问数据的时候我们遍历链表，如果这个数据不存于这个链表，那么我们就直接将这个数据插入到链表的首位置（如果内存已满，那么先删除链表的尾结点）。如果这个链表中之前就存在这个数据，那么先把这个数据在原来的链表中删除，然后再把数据插入到链表的首位置。
练习2：链表的删除和插入（非头尾结点）
删除p结点的后继结点
p->next = p ->next->next;
将x结点插入到a，b结点之间
x->next = p->next ;
p->next =x;
