JAVA实现双向循环链表

写在前面

最近在学习数据结构与算法，学习到链表部分，对照着视频练习了单链表，然后决定自己尝试写一下双向链表。

实现原理

双向链表相较单链表，只是在每个节点中多了一个成员用于存储上一个节点。如下图：

双向循环链表就是在双线链表的基础上首尾相连（第一个节点的prev指向最后一个节点，最后一个节点的next指向第一个节点），此处，我选择增加了一个虚拟头节点，这样虽然浪费了一点内存空间，但是对于内部实现来说，更加的容易，而对于使用则没有太大的差异（对于用户来说，看不到底层的实现）。

示意图如下（画的图很蹩脚，大概就那么个意思……..）：

本例中实现了链表的增删改查操作，虽然并不是每个方法都是链表常用的操作，但是写底层的实现有助于理解链表的结构。

增加：在要增加元素的位置，先新建节点newNode，将他的prev、next分别指向前一个和后一个节点，同时还需要将前一个节点的next和后一个节点的prev指向newNode，这样就完成了插入的操作。（此处需要注意插入时索引的有效性判断和当前链表是否为空，即只有dummyHead虚拟头节点）

删除：断开待删除节点与前后节点的连接，并将前后节点重新建立连接

改、查：其实修改和查询差不多，只要循环找到元素然后进行对应的操作即可

代码实现

本例中，Node节点类是作为LinkedList的内部类的。

/**
 * @author 小光
 * @date 2019/8/8 16:17
 * className: LoopLinkedList
 * description: 循环双向链表
 * ***************************************************************************
 * Copyright(C),2018-2019,https://blog.xgblack.cn  .All rights reserved.
 * ***************************************************************************
 */
public class LoopLinkedList<E> {

    /**
     * 节点类
     * 私有的内部类
     */
    private class Node{
        public E e;
        public Node prev;
        public Node next;

        public Node(E e, Node prev, Node next) {
            this.e = e;
            this.prev = prev;
            this.next = next;
        }

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

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

        @Override
        public String toString() {
            return e.toString();
        }
    }


    private Node dummyHead;
    private int size;

    public LoopLinkedList(){
        dummyHead = new Node(null,dummyHead,dummyHead);
        size = 0;
    }

    /**
     * 获取链表容量
     * @return
     */
    public int getSize(){
        return size;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed.Illegal index");
        }
        /*if (index == size) {
            Node prevNode = dummyHead;
            for (int i = 0; i < index; i++) {
                prevNode = prevNode.next;
            }

        }*/

        Node prevNode = dummyHead;
        if (prevNode.next == null) {
            Node newNode = new Node(e, dummyHead, dummyHead);
            dummyHead.next = newNode;
            dummyHead.prev = newNode;
        } else {
            for (int i = 0; i < index; i++) {
                prevNode = prevNode.next;
            }
            Node nextNode = prevNode.next;
            Node newNode = new Node(e, prevNode, nextNode);
            prevNode.next = newNode;
            nextNode.prev = newNode;
        }

        size ++;
    }

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

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

    /**
     * 获得链表index（0-based）位置的元素
     * 链表中不常用
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed.Illegal index");
        }
        Node curNode = dummyHead.next;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        return curNode.e;
    }

    public E getFirst() {
        return get(0);
    }
    public E getLast() {
        return get(size - 1);
    }

    /**
     * 修改链表index（0-based）位置的元素
     * 链表中不常用
     */
    public void set(int index,E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed.Illegal index");
        }
        Node curNode = dummyHead.next;
        for (int i = 0; i < index; i++) {
            curNode = curNode.next;
        }
        curNode.e = e;
    }

    /**
     * 查找链表是否存在元素e
     */
    public boolean contains(E e) {
        Node curNode = dummyHead.next;
        while (curNode != null && curNode != dummyHead) {
            if (curNode.e == e) {
                return true;
            } else {
                curNode = curNode.next;
            }
        }
        return false;
    }

    /**
     * 删除索引位置的元素
     * @param index
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Delete failed.Illegal index");
        }

        Node prevNode = dummyHead;
        for (int i = 0; i < index; i++) {
            prevNode = prevNode.next;
        }
        Node delNode = prevNode.next;
        Node nextNode = delNode.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
        E ret = delNode.e;
        delNode = null;
        size --;
        return ret;
    }

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

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

    public void removeElement(E e) {
        Node curNode = dummyHead.next;
        while (curNode != null && curNode != dummyHead ) {

            if (curNode.e == e) {
                Node prevNode = curNode.prev;
                Node nextNode = curNode.next;
                nextNode.prev = prevNode;
                prevNode.next = nextNode;
            }
            curNode = curNode.next;
        }
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

        Node curNode = dummyHead.next;
        while (curNode != null && curNode != dummyHead ) {
            res.append(curNode.e + "->");
            curNode = curNode.next;
        }

        res.append("NULL");
        return res.toString();
    }
}

使用测试

/**
 * @author 小光
 * @date 2019/8/8 10:04
 * className: TestBidirectionLinkedList
 * description:
 * ***************************************************************************
 * Copyright(C),2018-2019,https://blog.xgblack.cn  .All rights reserved.
 * ***************************************************************************
 */
public class TestLoopLinkedList {
    public static void main(String[] args) {
        LoopLinkedList<Integer> linkedList = new LoopLinkedList<>();

        System.out.println("空链表：" + linkedList);

        linkedList.add(0,10);
        System.out.println("0索引处添加元素10：" + linkedList);


        for (int i = 2; i < 5; i++) {
            linkedList.add(1,i * 10);
            System.out.printf("1索引处添加元素%d：" + linkedList,i * 10);
            System.out.println();
        }
        for (int i = 5; i < 8; i++) {
            linkedList.add(3, i * 10);
            System.out.printf("3索引处添加元素%d：" + linkedList,i * 10);
            System.out.println();
        }

        linkedList.addFirst(80);
        System.out.printf("在链表头添加元素%d：" + linkedList,80);
        System.out.println();

        linkedList.addLast(90);
        System.out.printf("在链表尾添加元素%d：" + linkedList,90);
        System.out.println();

        System.out.printf("链表5索引处的元素为：%d%n",linkedList.get(5));
        System.out.printf("链表头的元素为：%d%n",linkedList.getFirst());
        System.out.printf("链表尾的元素为：%d%n",linkedList.getLast());
        System.out.println();

        System.out.println("链表中是否存在元素100：" + linkedList.contains(100));
        System.out.println("修改链表2索引位置元素为100");
        linkedList.set(2,100);
        System.out.println("修改链表2索引位置元素为100后：" + linkedList);
        System.out.println("链表中是否存在元素100：" + linkedList.contains(100));

        System.out.println("删除链表头的元素：" + linkedList.removeFirst());
        System.out.println("删除后：" + linkedList);

        System.out.println("删除链表尾的元素：" + linkedList.removeLast());
        System.out.println("删除后：" + linkedList);

        System.out.println();

        linkedList.removeElement(10);
        System.out.println("删除元素10之后：" + linkedList);

        linkedList.removeElement(20);
        System.out.println("删除元素20之后：" + linkedList);
    }
}

运行结果如下：