什么是双向链表

如上图所示，双向链表就是可以通过头节点依次指向尾节点，也可以通过尾节点反过来查找头结点。

所以在编写双向链表的时候，我们需要设置两个节点，因为写的是哨兵版本，我们可以通过构造函数使设置的两个节点赋予值，并完成指向操作，我们来看代码。

public class DoublyLinkedListSentinel implements Iterable<Integer>{
    static class Node{
        Node prev;//上一个节点指针
        int value;//值
        Node next;//下一个节指针
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head;//头哨兵
    private Node tail;//为哨兵

    //构造方法
    public DoublyLinkedListSentinel(){
        head=new Node(null,666,null);
        tail=new Node(null,888,null);
        head.next=tail;
        tail.prev=head;
    }
    @Override
    public Iterator<Integer> iterator() {
        return null;
    }
}

findNode查找索引对应的节点

我们将i的值设为-1.这样在之后insert和remove方法中找前节点的时候不会出现异常，进行递增，直到查找到末尾哨兵节点。

private Node findNode(int index){
        int i=-1;
        for (Node p=head;p!=tail;p=p.next,i++){
            if(i==index){
                return p;
            }
        }
        return null;
    }

insert插入

插入的方法也是先找到插入位置的前一个节点，将前一个节点的next设置为新节点的next

找到了新node的prev和next将其实例化为一个具体的节点，再将前一个节点的next指向自己，下一个节点的prev指向自己

同时我们也要增加查找到prev为空的异常处理

public void insert(int index, int value){
        Node prev=findNode(index-1);
        if(prev==null){
            illegalIndex(index);
        }
        Node next=prev.next;
        Node inserted=new Node(prev,value,next);
        prev.next=inserted;
        next.prev=inserted;
    }
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index[%d] not found", index)
        );
    }

因为findNode里面不会返回哨兵节点，所以在insert方法中不用担心prev没有next，只要findNode返回的不是null，说明肯定有一个末尾的哨兵节点存在。

remove删除

思路也是先找到索引位置的前一个节点，如果为null则进行一次异常处理。

通过prev.next找到要移除的节点removed，将移除节点的下一个节点标记为next。

将prev指向next，将next的prev（前指向）指向prve即可。

同时需要考虑findNode返回的下一个节点可能为末尾哨兵的情况

不能移除哨兵节点，所以需要进行异常处理。

代码如下：

public void remove(int index){
        Node prev=findNode(index-1);
        if(prev==null){
            illegalIndex(index);
        }
        Node removed=prev.next;
        if(removed==tail){
            illegalIndex(index);
        }
        Node next=removed.next;

        prev.next=next;
        next.prev=prev;
    }

removeFirst移除头结点

继续调用remove方法即可

public void removeFirst(){
        remove(0);
    }

我们学过了上面的一些操作，不难发现好像双向链表的这些操作要更加的复杂，不仅需要处理next还要处理prev，那双向链表有哪些好处呢，因为有了头，尾节点，我们在进行尾插法，头插法等不需要遍历查找到最后一个元素。

 public void removeLast(){
        Node removed=tail.prev;
        Node prev=removed.prev;
        prev.next=tail;
        tail.prev=prev;
    }

我们也需要注意链表里面只有头和尾节点的情况，因为头结点删除不了，所以我们需要进行异常处理。

我们来看完整代码：

public void removeLast(){
        Node removed=tail.prev;
        if(removed==head){
            illegalIndex(0);
        }
        Node prev=removed.prev;
        prev.next=tail;
        tail.prev=prev;
    }

迭代器遍历：

我们还是使用lterator进行遍历，我们将遍历的初始节点设置为哨兵节点之后，再在hasnext里面通过是否遍历到末尾哨兵来进行判断。

在遍历更新的next方法中进行迭代，我们来看代码：

@Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p=head.next;
            @Override
            public boolean hasNext() {
                return p!=tail;
            }

            @Override
            public Integer next() {
                int value=p.value;
                p=p.next;
                return value;
            }
        };
    }

以上就是双向链表的所有基础操作，我们来看完整代码：

import java.util.Iterator;

public class DoublyLinkedListSentinel implements Iterable<Integer>{
    static class Node{
        Node prev;//上一个节点指针
        int value;//值
        Node next;//下一个节指针
        public Node(Node prev, int value, Node next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    private Node head;//头哨兵
    private Node tail;//为哨兵

    //构造方法
    public DoublyLinkedListSentinel(){
        head=new Node(null,666,null);
        tail=new Node(null,888,null);
        head.next=tail;
        tail.prev=head;
    }

    private Node findNode(int index){
        int i=-1;
        for (Node p=head;p!=tail;p=p.next,i++){
            if(i==index){
                return p;
            }
        }
        return null;
    }

    public void insert(int index, int value){
        Node prev=findNode(index-1);
        if(prev==null){
            illegalIndex(index);
        }
        Node next=prev.next;
        Node inserted=new Node(prev,value,next);
        prev.next=inserted;
        next.prev=inserted;
    }

    public void remove(int index){
        Node prev=findNode(index-1);
        if(prev==null){
            illegalIndex(index);
        }
        Node removed=prev.next;
        if(removed==tail){
            illegalIndex(index);
        }
        Node next=removed.next;

        prev.next=next;
        next.prev=prev;
    }

    public void removeFirst(){
        remove(0);
    }

    public void removeLast(){
        Node removed=tail.prev;
        if(removed==head){
            illegalIndex(0);
        }
        Node prev=removed.prev;
        prev.next=tail;
        tail.prev=prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                String.format("index[%d] not found", index)
        );
    }
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p=head.next;
            @Override
            public boolean hasNext() {
                return p!=tail;
            }

            @Override
            public Integer next() {
                int value=p.value;
                p=p.next;
                return value;
            }
        };
    }
}