单向循环链表常用方法代码实现

什么是单向循环链表？

将单链表中终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

如下图所示：

从上图可以看出，其循环就是尾节点的next指针域指向头节点的元素位置，头与尾相连形成循环状。

节点信息

单向循环链表与单链表的结构类似，没有太大变化，如下代码：

package link.singlelooplink;
/**
 * @Description 链表节点 单体循环链表
 * @author lmx.zh
 * @date 2019-06-14 16:39
 * @Copyright 2019 Alibaba.com All right reserved.
 */
public class Node {

    /**
     * 链表元素
     */
    Object data;
    /**
     * 链表后续节点
     */
    Node next;

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}

附上单向循环链表的一些必要的变量

/**
 * @Description 单体循环链表
 * @Author lmx.zh
 * @date 2019-06-19 15:47
 * @Copyright 2019 Alibaba.com All right reserved.
 */
public class SingleLoopLink {

    /**
     * 头节点
     */
    Node head;

    /**
     * 链表大小
     */
    int size;

    /**
     * 尾节点
     */
    Node last;
}

1. head 节点记录链表的头节点;
2. size 记录链表的大小，每增加或减少一个节点都做相应的递增或递减;
3. last 节点记录链表的尾节点，在增加节点时也可以作为临时节点;

增加节点

   /**
     * 增加元素
     *
     * @param item
     */
    public void addItem(Object item) {
        //临时节点
        Node tmp = last;
        Node newNode = new Node(item, null);
        //设置最后节点为新节点
        last = newNode;
        //如果节点为空时，则标识该链表为空节点
        if (tmp == null) {
            //设置头节点
            head = newNode;
            //因为是循环单链表，设置头节点的下一个节点是自己
            head.next = newNode;
        } else {
            //上一个节点的指针为新节点
            tmp.next = newNode;
            //设置最后一个节点为头节点
            last.next = head;
        }
        //链表递增
        ++size;
    }

增加节点与单链表大体相似，只需对头节点与尾节点做特殊处理
1. 如果链表只有头节点一个，头节点的next指针域指向自己;
2. 如果有多个节点，链表的尾节点不在指向null，而是指向头节点;

删除节点

   /**
     * 删除元素
     *
     * @param item
     * @return
     */
    public boolean removeItem(Object item) {
        boolean loop = true;
        boolean flag = false;
        //首节点
        Node p = head;
        //需要删除的节点
        Node n = head.next;
        //根据条件循环整个循环单链表
        while (loop) {
            //判断节点中的元素是否是将要删除的元素
            if (n.data.equals(item)) {
                //如果需要删除的节点是头节点
                if (n == head) {
                    //则将上一个节点，也就是尾节点的指针指向头节点的下一个节点 即 p.next -> head.next
                    p.next = n.next;
                    //将头节点设置为第二个节点，即头节点的下一个节点 head(头节点) -> n(需要删除的节点，是当前的头节点).next
                    head = n.next;
                }//如果需要删除的是尾节点
                else if (n.next == head) {
                    //尾节点的指针指向的是头节点，所以将上一个节点的指针指向头节点 即p.next -> head
                    p.next = head;
                } //如果需要删除的是中间节点
                else {
                    //直接将上一个节点的指针指向需要删除节点的下一个节点 即 p.next -> n.next
                    p.next = n.next;
                }
                //将需要删除的节点的指针指向空 n.next -> null
                n.next = null;
                //为了防止内存泄露，将删除的节点设置为null,也就是手动回收掉 n -> null
                n = null;
                //设置循环条件为fasle，停止循环
                loop = false;
                //删除成功标识
                flag = true;
                //节点条数递减
                --size;
                //跳出循环
                break;
            }
            //如果需要删除的元素没有匹配上，则继续循环，将p设置下个节点，n设置为下下一个节点，依次循环链表
            p = n;
            n = n.next;
        }
        //返回最终删除标志
        return flag;
    }

删除节点因为没有定义固定的头节点，所以需要对第一个节点和最后一个节点进行特殊处理，写的有点复杂了
1. 从第一个节点开始依次循环单向循环链表;
2. 如果循环的节点中数据元素匹配到待删除元素，则进行判断
3. 如果待删除的元素为第一个节点，将尾节点的指针域next指向第一个节点的下一个节点，即 p.next = head.next，将head节点设置为第二个节点，即 head = n.next;
4. 如果待删除的元素为尾节点，将尾节点上一个节点的next指针域指向第一个节点，即 p.next = n.next(head);
5. 如果为中间节点，将上一个节点的next指针域指向下一个节点的next指针域，即 p.next = n.next;
6. 最后将待删除的节点next指针域以及数据元素置空。

查询节点数据元素

   /**
     * 查询节点元素
     *
     * @return
     */
    public Object[] queryItem() {
        //设置循环后元素数组
        Object[] o = null;
        if (size != 0) {
            o = new Object[size];
            //设置头节点，依次循环
            Node first = head;
            //设置头节点元素
            o[0] = first.data;
            //设置第二个节点
            Node current = first.next;
            //链表下标
            int i = 1;
            //如果当前节点不是头节点，继续循环取及诶单元素
            while (current != first) {
                //存储链表中的元素
                o[i] = current.data;
                //循环链表下一个节点，知道节点为头节点跳出循环
                current = current.next;
                ++i;
            }
        }
        return o;
    }

查找元素与单链表思想一致，循环当前节点，将节点数据元素放入数组中，并且返回即可。

总结

单向循环链表其实最需要注意的就是head节点和last节点，增加节点时，如果只有head节点，则next指针域指向自己，如果存在多个节点last节点next指针域不再指向null，需要指向head节点。删除节点时，一定要关注head节点与last节点，也就是说无论是删除head节点还是last节点，最终结果head节点都要与last节点相连，这样才会是完整的单向循环链表。还是那句老话，写代码之前先画图，看图写代码就再也不会找到指针域了。

ps:上述的例子中，没有使用固定的头节点，使用固定的头节点会使链表操作更简单，不用去对head节点与last节点做特殊处理，后续有时间会补上固定头节点的代码实现方式。