双向链表，顾名思义，就是这是一个双向的链表，其相比于单向链表的优点：

· 以往我们在单向链表里进行增删改查时，都需要记录修改节点的前一个节点，因为我们是单向的，‘只进不退’嘛

·双向链表对这些增删改查操作就很方便了，我们只需要找到这个要修改的节点，对这个节点的前一个节点改一改，后一个节点改一改就完成了

接下来，我们来实现一个双向链表：

1.和单向链表一样，我们需要描述出链表中的一个个 ‘节点’，也就是静态内部类ListNode，这个节点里存着三样东西：

·该节点自身的值- int val

·该节点的前一个节点的地址- ListNode prev

·该节点的下一个节点的地址- LIstNode next

public class MyLinkedList {

    static class ListNode{
        public int val;

        public ListNode prev;

        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }
}

在写各种方法前，我们再准备一个头节点head和一个尾节点last

public ListNode head;

public ListNode last;

接下来，我们定义一个包含要实现的所有方法的接口IList：

public interface IList {
    void addFirst(int data);

    void addLast(int data);

    void addIndex(int index,int data);

    boolean contains(int key);

    void remove(int key);

    void removeAllKey(int key);

    int size();

    void clear();

    void display();

    void display2(MyLinkedList.ListNode Newhead);
}

一、size()

@Override
public int size() {
   int count = 0;
   ListNode cur = head;
   while(cur!=null){
       count++;
       cur = cur.next;
   }
   return count;
}

定义一个计数器count，通过cur遍历整个链表，记录这个链表的总长度

二.addFirst(int data)

@Override
public void addFirst(int data) {
   ListNode node = new ListNode(data);
   if(head==null){
       head = node = last;
   }else{
       node.next = head;
       head.prev = node;
       head = node;
   }
}

1.若头节点为空，则代表这条链表为空，我们让new出来的node节点同时成为head和last即可

2.头节点不为空，我们让node节点的next指向原来的头节点head，让原来head的prev里面的null指向这个新的头节点node，最后定义head = node（让node成为新的头节点）

三、addLast(int data)

@Override
public void addLast(int data) {
     ListNode node = new ListNode(data);
     if(head==null){
         head = node = last;
     }else{
         last.next = node;
         node.prev = last;
         last = node;
     }
}

1.若头节点为空，则代表这条链表为空，我们让new出来的node节点同时成为head和last即可

2.同样的，我们让node节点的prev指向原来的last节点，last的next节点指向新的尾节点node，最后定义last = node 即可

四、addIndex (int index,int data)

@Override
public void addIndex(int index, int data) {
      //处理index越界的问题
    int len = size();//链表长度
    if(index<0||index>len){
        throw new RuntimeException("插入位置index不合法，索引越界！");
    }
    if(index==0){
        addFirst(data);
        return;
    }
    if(index==len){
        addLast(data);
        return;
    }
    //接下来的情况为，插入链表中间的情况，我们需要找到index号节点的位置
    ListNode cur = head;
    ListNode node = new ListNode(data);
    while(index!=0){
          cur = cur.next;
          index--;
    }
    //循环结束，此时cur对应index号节点
    //我们的目标是将node节点插入到 P 和 cur 的中间
    ListNode P = cur.prev;
    P.next = node;
    node.prev = P;
    node.next = cur;
    cur.prev = node;
}

1.我们先处理了index，插入位置不合法的情况，处理方法：抛出一个运行时异常

2.如果index==0或者index==size（），我们调用一下前面写的addFirst或者addLast就return，很方便

3.我们通过循环找到了index号节点，并对其前后都进行操作

五、contains(int key)

@Override
public boolean contains(int key) {
    if(head==null){
        return false;
    }
    ListNode cur = head;
    while(cur!=null){
        if(cur.val==key){
            return true;
        }
        cur = cur.next;
    }
    return false;
}

1.若头节点为null，也就是链表为空，那么什么都不包含，false

2.通过cur遍历整个链表，如果找到某节点的val == key了，return 一个 true，如果遍历完都没找到则返回false

六、remove (int key)

@Override
public void remove(int key) {
    if(head==null){
        return;
    }
    if(head.val==key){
        head = head.next;

        /*注意此时这个head是新的头节点，也就是原来链表中的第二个节点*/
   
        if(head!=null){
            head.prev = null;
            return;
        }else{
            last = null;
        }
        return;
    }
    if(last.val==key){
        last = last.prev;
        last.next = null;
        return;
    }
    ListNode cur = head;
    while(cur!=null){
        if(cur.val==key){
            cur.prev.next = cur.next;
            return;
        }
        cur = cur.next;
    }
    //走到这里都没找打cur.val = key 的情况，说明我遍历的整个链表都没找到删除目标，那么执行return
    return;
}

1.如果链表为空(head==null) 那么return

2.如果头节点就是我要删除的目标，那么我们考虑该链表是否为单节点链表，为什么呢？

·正常思路：head = head.next, 新的头节点 head.prev = null

·单节点链表的情况：我们先正常让 head = head.next，此时新头节点head指向了null！

（单节点链表：head = last, head.prev = null, head.next = null）

3.处理措施：我们先正常 head = head.next，此时 head = null，而单向链表中head = last，但是我们要指出来，last = null，这样我们就成功处理好了单节点的情况

4.我们在删除尾节点时也会遇到单节点情况，不过这种情况已经被删除head节点处理过了，接下来我们画图得出正常处理思路接口

5.遍历链表，找到删除目标节点cur，执行 cur.prev.next = cur.next

七、removeAllKey (int key)

@Override
public void removeAllKey(int key) {
    if(head==null){
        return;
    }
   while(head!=null&&head.val==key){
       head = head.next;
   }
   if(head==null){ //如果此时新的head节点为null，说明该链表为单节点链表，处理方法和在remove里一样
       last = null;
       return;
   }

   //执行到这说明不是单节点链表，由于我们已经检查过了head.val ？= key，所以我们让cur = head.next，就不检查head了
    ListNode cur = head.next;
   while(cur!=null){
       if(cur.val==key){
           cur.prev.next = cur.next;
           if(cur.next!=null){
               //cur没有变，还是这个要删除的节点，不过此时已经删了，但我们还可以查看，cur的下一个节点是否为null
               //如果cur.next！=null，说明cur这个节点不是尾节点
               cur.next.prev = cur.prev;
           }else{
               //此时cur为尾节点
               last = cur.prev;
           }
       }
       cur = cur.next;
   }
}

1.老样子，判断链表是否为空

2.处理单节点：

·我们先检查第一个节点是否为要删除的节点

·如果此时是要删除的节点，我们像remove一样，head = head.next,再检查新的head是否为null，为null则说明是单节点，让last = null，执行return即可

3.接下来准备遍历链表，我们让cur = head.next，为什么不是head，因为我们在处理单节点的时候就检查了head.val ?= key，是不是不重要，反正已经检查了head节点，如果==key,我们早就通过head = head.next处理过了，不是也不重要

4.while循环内又分为cur，也就是删除目标，是否为尾节点，画图即可

八、clear，display

较简单的三个方法，不做过多描述

@Override
public void clear() {
    ListNode cur = head;
    while(cur!=null){
        ListNode curN = cur.next;
        cur.next = null;
        cur.prev =null;
        cur = curN;
    }
    head = last = null;
}

@Override
public void display() {
    ListNode cur = head;
    while(cur!=null){
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
}

@Override
public void display2(ListNode Newhead) {
    ListNode cur = Newhead;
    while(cur!=null){
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
}

写到这里，我们的双向链表就实现了，感谢你的阅读~