《征服数据结构》双向链表

摘要：

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 尾部插入：