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

  • A+
所属分类:数据结构

什么是单向循环链表?

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

如下图所示:
单向循环链表常用方法代码实现

从上图可以看出,其循环就是尾节点的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节点做特殊处理,后续有时间会补上固定头节点的代码实现方式。

  • 我的微信
  • 加好友一起交流!
  • weinxin
  • 微信公众号
  • 关注公众号获取分享资源!
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: