1、什么是双向链表
上期我们实现了一下单链表，在Java(1.8)中，链表为 LinkedList，而底层是一个双向链表，跟 ArrayList 一样，LinkedList 也实现了 List 接口，这里我们画一个图，让大家简单见识下双向链表：
如图我们可以看出，双向链表最少有三个域，分别是数据域和两个指针域，分别指向节点的前驱和后继，第一个节点没有前驱，最后一个节点没有后继。
2、实现一个双向链表
2.1 实现前的约定
链表的每个元素是一个节点，我们仍然采用内部类的方式，既然是双向的，那么我们还需要在外部定义一个head和last，分别为头节点和尾节点的引用。
public class MyLinkedList { private class ListNode { private int val; //数据域 private ListNode prev; //前指针域 private ListNode next; //后指针域 private ListNode(int val) { this.val = val; } } private ListNode head; //头节点引用 private ListNode last; //尾节点引用 private int size; //链表有效数据个数 }
同时我们还要实现以下几个方法：
public void addFirst(int data); //头插法 public void addLast(int data); //尾插法 public boolean addIndex(int index,int data) //任意位置插入,第一个数据节点为0号下标 public boolean contains(int key); //查找是否包含关键字key是否在单链表当中 public void removeAllKey(int key); //删除所有值为key的节点 public void clear(); //清空链表 public int size(); //得到链表的长度
2.2 addFirst 方法
//头插法 public void addFirst(int data) { ListNode newNode = new ListNode(data); // 链表为空的情况 if (this.head == null) { this.head = newNode; this.last = newNode; this.size++; return; } newNode.next = this.head; //新节点的后一个为头节点 this.head.prev = newNode; //头节点的前一个为新节点 this.head = newNode; //新节点成为新的头节点 this.size++; }
与单链表不同，由于双向链表有头尾节点引用，所以这里我们要在第一次插入元素的时候进行特殊处理，当第一次插入元素我们需要将头尾节点的引用都指向这个节点，后续插入只需要改变头节点的引用即可，最后插入完成别忘记链表有效节点个数自增1哦！
2.3 addLast 方法
//尾插法 public void addLast(int data) { ListNode newNode = new ListNode(data); // 链表为空的情况 if (this.head == null) { this.head = newNode; this.last = newNode; this.size++; return; } newNode.prev = this.last; //新节点的前一个为尾节点 this.last.next = newNode; //尾节点的后一个为新节点 this.last = newNode; //新节点成为新的尾节点 this.size++; }
与头插法相差不多，无非就是需要修改尾节点的引用，以及注意新节点的指针域指向问题，这里小伙伴们可以结合我的代码注释，尝试去理解，配合画图，相信你就能掌握好头插法和尾插法了！
2.4 addIndex 方法
//任意位置插入,第一个数据节点为0号下标 public boolean addIndex(int index,int data) { // 判断index下标的合法性 if (index < 0 || index > this.size) { return false; } // index为0表示头插 if (index == 0) { addFirst(data); return true; } // index为size长度表示尾插 if (index == this.size) { addLast(data); return true; } //其他情况为中间插入 ListNode newNode = new ListNode(data); ListNode cur = this.head; while (index != 0) { cur = cur.next; index--; } newNode.prev = cur.prev; //新节点的前一个为cur的前一个 newNode.next = cur; //新节点的后一个为cur cur.prev.next = newNode; //cur的前节点的后一个为新节点 cur.prev = newNode; //cur的前节点为新节点 return true; }
对于在指定位置插入节点来说，如果给定的 index 位置大于我们的有效节点个数呢？也就是说假设我链表只有 5 个节点，你要在 8 位置插入元素显然是不合法的，其次，如果要在负数的位置插入那更不合法，所以我们要对 index 做判断，往后走我们还可以考虑两个点，如果index == 0 或者 index == size()，那么也就是对应着我们的头插和尾插，那么我们直接调用前面写的头插尾插方法即可，代码接着往后走，剩下的就是中间插入节点的情况了，逻辑很简单，首先要找到 index 对应的节点，接着改变相关节点指针域的指向即可，这里可以结合着代码以及注释，下来画图进行分析。
2.5 contains 方法
//查找是否包含关键字key是否在双链表当中 public boolean contains(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { return true; } cur = cur.next; } return false; }
这个方法跟我们之前写单链表的时候相差无几，相信有了前面单链表的基础，这个简直是信手拈来了吧，无非就是遍历这个链表，只要 cur 没有遍历到 null，也就是没有到最后一个节点的 next 位置，我们就遍历找有没有 key，找到了返回 true 找不到返回 false 咯！
2.6 removeAllKey 方法
//删除所有值为key的节点 public void removeAllKey(int key) { ListNode cur = this.head; while (cur != null) { if (cur.val == key) { //如果被删除cur是头节点 if (cur == this.head) { //只有一个节点的情况 if (this.head.next == null) { this.head = null; this.last = null; } else { cur.next.prev = null; //cur的后节点的前节点指针域改为null this.head = cur.next; //头节点变成cur的下一个节点 } } else { //如果被删除cur是尾节点 if (cur == this.last) { this.last = cur.prev; //尾节点变成cur的前节点 } else { cur.next.prev = cur.prev; //cur的后节点的前节点指针域改为cur的前节点 } cur.prev.next = cur.next; //cur的前节点的后节点指针域改为cur的后节点 } this.size--; } cur = cur.next; } }
要删除所有值为 key 的节点，这道题思想不难，还是遍历链表嘛，如果值一样，修改相关节点引用即可，但是问题来了，删除头节点和尾节点，和删除中间节点的修改指向逻辑可不一样，所以我们要分别处理，分开处理这三种情况之后，如果只有一个节点的情况呢？也得处理，于是就有了我们上面的代码，当然可以有很多种写法，你只要把各种情况捋清楚了就好，至于修改指针域指向的逻辑画画图就能理解了！
