摘要：
1，双链表的介绍
2，双链表的用途
3，双链表的节点插入和删除
1，双链表的介绍
前面我们讲过单链表，单链表的特点就是只能往后访问不能往前访问。单链表一般在面试中用的比较多，比如删除倒数第 n 个节点，链表反转等，但在实际的工作中单链表用的并不多。比如Java中的LinkedList，LinkedHashMap等都是双链表。
双链表每个节点包含三个域，一个是数据域，两个指针域。两个指针域中一个指向前一个节点，一个指向后一个节点，如下图所示：
Java代码：
// 双链表节点类
class LinkNode {
int val;// 节点中存储的数据。
LinkNode pre;// 指向前一个节点的指针。
LinkNode next;// 指向下一个节点的指针。
public LinkNode(int val, LinkNode pre, LinkNode next) {
this.val = val;
this.pre = pre;
this.next = next;
}
}C++语言：
// 双链表节点类
struct LinkNode {
int val;// 节点中存储的数据。
LinkNode *pre;// 指向前一个节点的指针。
LinkNode *next;// 指向下一个节点的指针。
LinkNode(int x, LinkNode *p, LinkNode *n) : val(x), pre(p), next(n) {}
};单链表中因为只能从前往后遍历，我们只需要记录头节点head即可，但双链表中可以从后往前遍历，我们还需要记录尾节点tail，两个方向都可以遍历。如果不想记录尾节点，也可以让双链表的首尾相连，构成一个环形链表，只记录头节点head即可，从head开始沿着两个方向都可以访问。
2，双链表的用途
双链表的用途非常强大，除了当链表使用以外，还可以当做普通队列，双端队列，栈来使用，除此之外还可以用于数据的缓存，比如常见的LRU(Least Recently Used)缓存，LFU(least frequently used)缓存等。
在Android开发中图片的缓存一般使用的是LruCache，而LruCache继承的就是LinkedHashMap，LinkedHashMap就是一个双向链表。
他会把经常使用的数据插入到头节点head，这样不经常使用的数据就会越来越靠后，当存储数据足够多的时候，就会从尾节点tail往前删除，也就是把最不经常使用的数据给删除，即达到缓存的效果，又防止了数据量过大。
3，双链表的节点插入和删除
双链表的节点插入和删除与单链表一样，也是分三种情况，分别是在头部，尾部和中间，我们分别来看下。
3.1 头部插入：
1，创建新节点，让它的next指针指向head节点。
2，让head的pre指针指向新节点。
3，让head指向新节点。
3.2 尾部插入：
