双链表介绍：
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用于存放数据，其中一个指针域用来指向后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存放数据，指向前驱结点的指针域值为null,指向后继结点的指针域指向第一个真正存储数据的结点。

按照面向对象的思想，我们需要设计一个类来实现双向链表，由于结点是属于链表的，所以我们把结点类作为链表类的一个内部类来实现

双链表的四个成员变量

head头结点是整个双链表的入口，last用来表示链表的最后一个结点，N记录双链表长度，Node内部类实现结点

结点类的实现

    private class Node{
        //指向前一个结点
        private Node pre;
        //指向后一个结点
        private Node next;
        private T item;
        //构造方法
        public Node(T item,Node pre, Node next ) {
            this.pre = pre;
            this.next = next;
            this.item = item;
        }
    }

双向链表的构造方法

初始化头结点（没有数据域，没有前驱结点，没有后继结点）和链表长度

//双向链表的构造方法
     public TwoWayList(){
        //初始化头结点和尾结点
        this.N=0;
        this.head=new Node(null,null,null);
        //刚开始不存在尾结点
        this.last=null;
    }

在双链表尾部添加元素

首先判断链表是否为空，为空则直接让新结点的上一个结点成为头结点，让头结点的下一个结点成为新结点，并让新结点成为尾结点；
若不为空则让原本尾部的结点的下一个结点变为新结点，让新结点的上一个结点变为原来的尾部结点，让新结点成为尾部结点

    //在链表最后插入元素
    public void insert(T item){
        //链表为空，插在头结点后面
        if (isEmpty()){
            //创建新结点，新结点前面指向头结点
            Node newNode = new Node(item, head, null);
            //新节点作为尾结点
            last=newNode;
            //头结点指向尾结点
            head.next=last;
        }
        //链表不为空
        else{
        //创建新结点，新结点前面指向尾结点
        Node newNode = new Node(item, last, null);
        //让尾结点指向新结点
        last.next=newNode;
        //使新结点成为尾结点
        last=newNode;
        }
        N++;
    }

在指定的下标位置添加元素

找到指定下标位置的前一个元素，找到指定下标的元素，创建新结点（前面指向前一个元素，后面指向指定下标的元素）
让前一个元素的下一个结点变为新结点，让指定下标的元素的上一个结点变为新结点，让新结点成为尾部结点

  //在双链表的i索引处插入值为item的数据元素
    public void insert(int i,T item){
        Node pre=head;
        //找到i-1处的结点
        for (int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i索引处的结点
        Node curr=pre.next;
        //创建新结点，新结点上一个结点是i-1处，下一个结点是i处
        Node newNode = new Node(item, pre, curr);
        //让i位置的前一个结点的下一个结点变为新结点
        pre.next=newNode;
        //让i位置的前一个结点变为新结点
        curr.pre=newNode;
        N++;
    }

获取指定下标位置的元素

从下标0处开始遍历，找到指定的位置停下来，每次遍历指针往后移一位

 //获取指定索引的结点值
    public T get(int i){
        Node node=head;
        for (int index=0;index<=i;index++){
            node=node.next;
        }
        return node.item;
    }

删除指定下标位置的元素

找到指定下标位置的前一个元素，找到指定下标的元素，找到指定下标的下一个元素
首先判断要删除的元素是不是链表的最后一个元素,如果是则让前一个元素的next域不指向任何元素，让前一个元素成为尾部结点
如果是删除中间元素，则让上一个元素的下一个结点成为下一个结点，让下一个结点的前一个结点成为上一个元素

//删除双链表i索引处的结点，并返回该结点的值
    public T remove(int i){
        Node pre=head;
        //找到位置i-1的结点（i位置的前一个结点）
        for(int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i位置的结点
        Node curr=pre.next;
        //找到位置i的下一个结点
        Node nextNode=curr.next;
        //删除的是最后一个结点
        if(nextNode==null){
            pre.next=null;
            last=pre;
        }
        //删除的是中间结点
        else{
            //让i位置的前一个结点的下一个结点变为i位置的下一个结点
            pre.next=nextNode;
            //让i位置的下一个结点的上一个结点变为i位置的前一个结点
            nextNode.pre=pre;
        }
        N--;
        return  curr.item;
    }

返回元素在双链表中第一次出现的下标

从0下标开始遍历查找，直到遍历完整个链表

//返回结点item第一次出现的索引位置,若不存在，返回-1
    public int  indexOf(T item){
        Node node=head;
        for(int index=0;node.next!=null;index++){
            node=node.next;
            //相等，返回下标索引
            if(node.item.equals(item)){
                return  index;
            }
        }
        return -1;
    }

遍历整个双向链表

双链表的遍历与单链表一模一样，只是我们还可以倒序遍历双链表

遍历原理：我们可以学习集合ArrayList的forEach遍历方法，去实现Iterator迭代器我们通过链表类去实现Iterable接口，重写Iterable的Iterator方法，实现迭代器，由于Iterator方法的返回值是接口类型的Iterator,所以我们还创建了一个内部类去实现这个Iterator接口，以实现Iterator的类的对象返回。

 @Override
    public Iterator<T> iterator() {
        //用内部类实现Iterator接口
        return new LIterator();
    }

    //内部类
    private class LIterator implements Iterator{
        private Node node;
        public LIterator(){
            this.node=head;
        }
        @Override
        public boolean hasNext() {
            return node.next!=null;
        }

        @Override
        public Object next() {
            node=node.next;
            return node.item;
        }
    }

原文链接:https://blog.csdn.net/zbcwmq/article/details/122332250