image.png

接口类：

public interface CircularDoubleLinkedList<E> {


        public int size();
        public void add(int index, E e);
        public void addFirst(E e);
        public void addLast(E e);
        public E remove(int index);
        public E removeFirst();
        public E removeLast();
        public E get(int index);
        public void set(int index, E e);
        public boolean contains(E e);
        public boolean isEmpty();
        void reversePrint();

//        public E showPre(int index);

}

实现类：

public class CircularDoubleLinkedListImpl<E> implements CircularDoubleLinkedList<E> {

    class Node{
        public E e;
        public Node preNode;
        public Node nextNode;

        public Node(E e , Node preNode ,Node nextNode){
            this.e = e;
            this.preNode = preNode;//存前一个结点的地址
            this.nextNode = nextNode;//存下一个结点的地址
        }

        public Node(){
            this.e = null;
            this.preNode = null;
            this.nextNode = null;
        }

        public Node(E e){
            this(e , null ,null);
        }

    }
    private Node dummyhead;
    private int size;

    public CircularDoubleLinkedListImpl(){
        dummyhead = new Node();
        dummyhead.nextNode = dummyhead;
        dummyhead.preNode = dummyhead;
        size = 0;
    }

    /**
     * 根据索引得到索引所在的结点的前一个结点
     * @param index
     * @return
     */
    private Node getNodeByIndex(int index){
        Node cur = dummyhead;
        if (index < size/2) {
            for (int i = 0; i < index; i++) {
                cur = cur.nextNode;
            }
        }
        else{
            for (int i = 0 ; i < size-index+1; i++){
                cur = cur.preNode;
            }

        }
        return cur;

    }


    @Override
    public int size() {
        return size;
    }

    @Override
    public void add(int index, E e) {
        //边界处理 索引是从0开始的 第一个结点索引为0
        if (index < 0 || index > size)
            throw new IllegalArgumentException("index is illegal,add is fail");
        Node pre = getNodeByIndex(index);
        Node node = new Node(e);
        node.nextNode = pre.nextNode;
        node.nextNode.preNode = node;
        pre.nextNode = node;
        node.preNode = pre;

        size++;

    }

    @Override
    public void addFirst(E e) {
        add(0,e);

    }

    @Override
    public void addLast(E e) {
       add(size,e);
    }

    @Override
    public E remove(int index) {

        if (index < 0 || index >= size )
            throw new IllegalArgumentException("the index is illegal,remove is fail");

        if (isEmpty()){
            throw new IllegalArgumentException("list is empty ,can`t remove anything");
        }
        Node pre = getNodeByIndex(index);

        Node temp = pre.nextNode;
        E re = temp.e;

        pre.nextNode = temp.nextNode;
        temp.nextNode.preNode = pre;


        size--;
        return re;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public E removeLast() {
        return remove(size-1);
    }

    @Override
    public E get(int index) {

        return getNodeByIndex(index).nextNode.e;
    }

    @Override
    public void set(int index, E e) {
       getNodeByIndex(index).nextNode.e = e;
    }

    @Override
    public boolean contains(E e) {

        Node cur = dummyhead.nextNode;
        while (cur != dummyhead){
           if (cur.e == e)
               return true;
           cur = cur.nextNode;
        }
        return false;

    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 正向遍历打印
     * @return
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node node = dummyhead.nextNode;

        while (node != dummyhead){
            res.append(node.e+"->");
            node = node.nextNode;
        }

        res.append(dummyhead.nextNode.e);

        return res.toString();
    }

    /**
     *反向遍历
     */
    public void reversePrint(){
        StringBuilder res = new StringBuilder();

        Node node = dummyhead.preNode;
        while (node != dummyhead){
            res.append(node.e +"->");
            node =node.preNode;
        }
        res.append(dummyhead.preNode.e);
        System.out.println(res.toString());
    }

}

测试：

public class Main {

    public static void main(String[] args) {
    CircularDoubleLinkedList<Integer> list = new CircularDoubleLinkedListImpl<>();

    for (int i = 0 ; i < 10 ; i++){
        list.add(i,i);
        System.out.println(list);
    }

    list.remove(0);
        System.out.println(list);

        list.reversePrint();
    }
}

image.png