循环链表

在循环链表中最后一个节点指向第一个节点，形成一个环。循环链表可以使用单向链表实现也可以使用双向链表实现。

单向链表：最后一个节点的后继指针指向第一个节点
双向链表：最后一个节点的后继指针指向第一个节点，第一个节点的前驱指针指向最后一个节点。

循环链表的结构

在循环链表中，没有明确的末尾节点，因此遍历时需要额外的条件来判断是否完成了一轮循环。

在本文中只将双向链表的实现。

节点的存储结构

双向循环链表中的节点定义与双向链表一致。

@NoArgsConstructor
@Data
public class Node<T> {
    /**
     * 数据
     */
    private T data;
    /**
     * 指向后继节点的指针
     */
    private Node<T> next;
    /**
     * 指向前驱节点的指针
     */
    private Node<T> prev;

    public Node(T data) {
        this.data = data;
    }

    // debug中使用，避免循环依赖导致toString的栈溢出。
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}
java

提示

在 Debug 时，对象后面显示的信息是通过 toString 方法获取的。因此 Debug 过程中会经常调用对象的 toString 方法。切记不要在 toString 方法中对对象实例进行任何修改，否则会出现 Debug 和运行时程序的运行结果不一致。

基本操作

循环链表的定义与双向链表的定义相同。如下：

public class CircularLinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    private int size;
}
java

添加元素

头插法

为了便于理解，我们单独处理首次添加，和链表中已存在元素的情况。循环链表的关键在于将链表的首尾相接，具体代码如下，

public void addFirst(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        head = tail = node;
        node.setNext(node); 
        node.setPrev(node);
    } else {
        node.setNext(head); 1
        head.setPrev(node); 2
        head = node;        3
        head.setPrev(tail); 4
        tail.setNext(head); 5
    }
    size++;
}
java

与双向链表相比，有如下区别

添加第一个节点时，要将前驱后后继指针都指向自己。
添加第二个及之后的节点时，1 2 3 步与双向链表一致。4 5 的目的在于使链表首尾相接，形成一个环。

因此可以看出处理循环链表的关键在于首尾，而与普通的链表相比，多了将首尾相接的步骤。后续在尾插法中，也是一样的。而中间的插入只要不涉及到首尾，与普通链表的操作是一致的。

提示

如何让链表的首尾相接？

将尾节点的后继指针指向首节点，即 tail.setNext(head);
将首节点的前驱指针指向尾节点，即 tail.setNext(head);

循环链表的头插法

无论是一个节点，还是多个节点，都有将链表首尾相接的动作。因此上面的代码可以优化成下面的样子。

public void addFirst(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        head = tail = node;
    } else {
        node.setNext(head); 1
        head.setPrev(node); 2
        head = node;        3
    }
    head.setPrev(tail); 4
    tail.setNext(head); 5
    size++;
}
java

首先将多个元素组成一个链表，最后将链表首尾相接。

尾插法

尾插法与头插法一样，可以先参考双向链表的尾插法操作。在完成链表元素的添加后，再将链表首尾相接。具体代码如下：

public void addLast(T data) {
    Node<T> node = new Node<>(data);
    if (head == null) {
        head = tail = node;
    } else {
        tail.setNext(node);
        node.setPrev(tail);
        tail = node;
    }
    head.setPrev(tail);
    tail.setNext(head);
    size++;
}
java

图示如下：

循环链表的尾插法

插入元素

插入元素与双向链表的插入元素一致。虽然插入元素也会涉及到头尾节点，但是在代码中进行了判断，向链表头插入元素直接调用了 addFirst 方法，向链表尾部插入元素直接调用了 addLast 方法，而在插入元素的方法内相当于只处理了中间节点（即存在直接后继和直接前驱）的连接关系。

public void add(int index, T data) {
    if (index < 0 || index > size) return;
    if (index == 0) {
        addFirst(data);
    } else if (index == size) {
        addLast(data);
    }else {
        Node<T> node = new Node<>(data);
        Node<T> next = get(index);    1

        node.setPrev(next.getPrev()); 2
        node.setNext(next);  3
        next.getPrev().setNext(node); 4
        next.setPrev(node);  5

        size++;
    }
}

public Node<T> get(int index) {
    if (index < 0 || index >= size) return null;
    Node<T> node = head;
    for (int i = 0; i < index; i++) {
        node = node.getNext();
    }
    return node;
}
java

提示

由于此插入方法是向索引所在位置插入元素，因此原索引位置的元素会变成后一个，因此这里使用 next 变量接收当前索引位置元素。

代码图示如下：

合并添加/插入代码

在循环链表中无论哪个节点都可以直接获取到其前驱和后继节点，哪怕这个节点指向了自己。因此我们能否直接通过下面的代码完成节点的添加和插入呢？

Node<T> node = new Node<>(data);
Node<T> next = get(index); // 索引位置的元素

node.setPrev(next.getPrev()); 1
node.setNext(next);           2
next.getPrev().setNext(node); 3
next.setPrev(node);           4
java

抛开索引位置，插入元素相当于是向当前元素之前插入一个元素。因此此方法可以用于头插法。但是不能用于尾插法。而由于链表是循环链表，首尾相接，向链表尾部插入元素，就相当于是头尾之间插入元素。这时候只要将 next 指向 head，依然可以用上面了逻辑完成元素的插入。只是需要尤为注意头尾指针的处理。具体代码如下：

public void add(int index, T data) {
    if (index < 0 || index > size) return;
    Node<T> node = new Node<>(data);
    if (head == null) {
        // 当头部节点为空时，说明是第一次插入元素，直接将头节点指向当前节点，当前节点的前驱及后继指针都指向自己，形成一个环。
        head = tail = node;
        head.setPrev(tail);
        tail.setNext(head);
    } else {
        Node<T> next;
        if (index == size) {
            // index = size时，表示插入到尾部，将 next 指向头节点
            next = head;
        } else {
            // 否则，将 next 指向当前节点
            next = get(index);
        }
        node.setPrev(next.getPrev());
        node.setNext(next);
        next.getPrev().setNext(node);
        next.setPrev(node);
    }
    if (index == 0) {
        // 当索引位置为0时，证明是向头部插入元素，需要将头节点指向当前节点
        head = node;
    } else if (index == size) {
        // 当索引位置为size时，证明是向尾部插入元素，需要将尾节点指向当前节点
        tail = node;
    }
    size++;
}
java

代码图示如下：

这时候 addFirst 和 addLast 就可以改为

public void addFirst(T data) {
    this.add(0, data);
}

public void addLast(T data) {
    this.add(size, data);
}
java

只有循环链表可以借助其首尾相接的特性进行此优化。

删除元素

同样的，由于循环链表是一个环，因此我们可以使用相同的逻辑来删除头节点、尾节点和中间节点。步骤如下：

将当前节点指向的后继节点的 pre 指针，指向当前节点的前驱节点。这里的当前节点指要删除的节点，下同。
将当前节点的前驱节点的 next 指针，指向当前节点的后继节点。
对于首尾节点需要特殊处理其首尾指针

由于我们总是能获取到任何节点的前驱和后继，因此这一套逻辑可以处理链表中的任何一个节点。具体代码如下：

public void remove(int index) {
    if (index < 0 || index > size) return;
    if (index == 0 && size == 1) {
        // 仅有一个节点时，需要将头节点和尾节点都置为null
        head = tail = null;
    }

    Node<T> current = get(index);

    current.getNext().setPrev(current.getPrev());
    current.getPrev().setNext(current.getNext());

    // 当删除头尾节点时修改头尾指针指向
    if (index == 0) {
        head = current.getNext();
    } else if (index == size - 1) {
        tail = current.getPrev();
    }

    current.setPrev(null);
    current.setNext(null);
    size--;
}
java

代码图示如下：

说明

这里只提供删除头节点和中间节点的图示说明，删除尾节点与头节点类似，有兴趣的可以字节尝试画一下。

删除头尾节点的方法可以直接调用 remove 方法来实现。如下：

public Node<T> removeFirst() {
    return remove(0);
}

public Node<T> removeLast() {
    return remove(size - 1);
}
java

遍历元素

由于链表是循环链表，因此不能再通过判断是否有下一个节点来确定是否到达链表尾部。可以通过两种方式来判断是否到达链表尾部

通过 size 判断：遍历时创建一个 index 变量记录当前索引位置，当 index = size - 1 说明到达了链表尾部。或者只要 index < size 说明还没有到达链表尾部。
通过 tail 指针判断：用 equals 来判断节点是否为尾节点。

这两种方式同样适用于普通链表。本例中使用第二种方式判断，具体代码如下：

public Iterator<T> iterator() {
    return new Iterator<>() {
        private Node<T> node = head;
        @Override
        public boolean hasNext() {
            return node != null;
        }
        @Override
        public T next() {
            if (node == null) {
                throw new NoSuchElementException("链表为空或已遍历至链表尾部");
            }
            T data = node.getData();
            if (Objects.equals(node, tail)) {
                node = null;
            } else {
                node = node.getNext();
            }
            return data;
        }
    };
}
java

注意

不能直接在 hasNext 方法中使用 Objects.equals(node, tail) 来判断是否有下一个节点，这样会导致丢失最后一个节点。当然如果想在 hasNext 中判断是否有下个节点也是可以的，使用 Objects.equals(node.getPrev(), tail) 即可。

定长循环链表

顾名思义，定长循环链表是长度固定的循环链表。主要应用循环队列中，在循环队列中，当元素填满后，添加新元素时，旧元素按照先进先出的顺序被删除。常用于限流器和消息队列。其具体实现在循环队列部分再做讨论。

节点的存储结构​

基本操作​

添加元素​

头插法​

尾插法​

插入元素​

合并添加/插入代码​

删除元素​

遍历元素​

定长循环链表​

节点的存储结构

基本操作

添加元素

头插法

尾插法

插入元素

合并添加/插入代码

删除元素

遍历元素

定长循环链表