专栏首页好好学java的技术栈“365算法每日学计划”:06打卡-单向循环链表

“365算法每日学计划”:06打卡-单向循环链表

一、单向循环链表:

1、概念:

单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。

和单链表相比,循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时,适合于采用循环单链表。

和单链表相同,循环单链表也有带头结点结构和不带头结点结构两种,带头结点的循环单链表实现插入和删除操作时,算法实现较为方便。

带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同,差别仅在于:

(1)在构造函数中,要加一条head.next = head 语句,把初始时的带头结点的循环单链表设计成上图中(a)所示的状态。

(2)在index(i)成员函数中,把循环结束判断条件current != null改为current != head。

2、单链表的代码实现:

1、结点类Node的实现代码

 public class Node {  
        public Object data;//保存当前结点的数据  
        public Node next;//指向下一个结点  

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

2、循环链表类CircleList的实现代码

  public class CircleList {  
        private Node head;  

        public CircleList(){  
            head = new Node(0);  
            head.next = null;  
        }  

        //在指定位置插入结点  
        public boolean insert(Object data,int pos){  
            boolean ret = (head != null) && (data != null) && (pos >= 0);  

            if(ret){  
                Node node = new Node(data);  

                if(head.next == null){  
                    //插入的结点前,循环链表中没有结点。  
                    head.next = node;  
                    node.next = node;  
                }else{  
                    if(pos >= (Integer)head.data){  
                        pos = (Integer)head.data;  
                    }  

                    Node currentNode = head.next;  

                    //若currentNode.next == head.next,就说明currentNode是最后一个结点  
                    for(int i = 0;(i < pos) && (currentNode.next != head.next);i++){  
                        currentNode = currentNode.next;  
                    }  

                    node.next = currentNode.next;  
                    currentNode.next = node;  

                    //插入位置的下标为0时  
                    if(pos == 0){  
                        head.next = node;  
                    }  
                }  

                head.data = (Integer)head.data + 1;  
            }  

            return ret;  
        }  

        //获取链表中下标为pos的结点  
        public Object get(int pos){  
            Object ret = null;  

            if(head != null && pos >= 0 && pos < (Integer)head.data){  
                Node node = head;//头结点  

                //找到要删除的结点  
                for(int i = 0;i<=pos;i++){  
                    node = node.next;  
                }  

                if(node != null){  
                    ret = node.data;  
                }  
            }  

            return ret;  
        }  

        //删除链表中下标为pos的结点  
        public Object delete(int pos){  
            Object ret = null;  

            if(head != null && pos >= 0 && pos < (Integer)head.data){  
                Node node = head;//头结点  
                Node currentNode = null;//要删除的结点  

                //找到要删除结点的前一个结点  
                for(int i = 0;i<pos;i++){  
                    node = node.next;  
                }  

                currentNode = node.next;  

                //获取要删除结点的数据  
                if(currentNode != null){  
                    ret = currentNode.data;  
                }  

                //要删除的结点是循环链表中的第一个结点  
                if(head.next == currentNode){  
                    head.next = currentNode.next;  
                }  

                //删除结点  
                node.next = currentNode.next;  

                head.data = (Integer)head.data - 1;  
            }  

            return ret;  
        }  

        //清空链表  
        public void clear(){  
            if(head != null){  
                head.data = 0;  
                head.next = null;  
            }  
        }  

        //注销链表  
        public void destroy(){  
            if(head != null){  
                head = null;  
            }  
        }  

        //获取链表中结点的个数  
        public int length(){  
            int ret = -1;  

            if(head != null){  
                ret = (Integer)head.data;  
            }  

            return ret;  
        }  

        //打印循环链表中的数据  
        public void display(){  
            if(head != null){  
                Node node = head;  

                for(int i = 0;i < (Integer)head.data;i++){  
                    node = node.next;  
                    System.out.print(node.data+"  ");  
                }  
            }  
        }  
    } 

3、测试类Test的代码

 public class Test {  

        public static void main(String[] args) {  
            CircleList list = new CircleList();  

            list.insert("结点1", 0);  
            list.insert("结点2", 1);  
            list.insert("结点3", 2);  
            list.insert("结点4", 3);  
            list.insert("结点5", 4);  
            list.insert("结点6", 5);  

            System.out.println("链表中的元素为:");  
            list.display();  
            System.out.println("\n链表中结点的个数:"+list.length());  

            System.out.println("\n获取链表中下标为2的结点:"+list.get(2));  
            System.out.println("删除链表中下标为0的结点:"+list.delete(0));  
            System.out.println("链表中的元素为:");  
            list.display();  
            System.out.println("\n链表中结点的个数:"+list.length());  

            list.clear();  
            list.destroy();  
        }  
    }  

4、程序运行结果

链表中的元素为: 结点1 结点2 结点3 结点4 结点5 结点6 链表中结点的个数:6 获取链表中下标为2的结点:结点3 删除链表中下标为0的结点:结点1 链表中的元素为: 结点2 结点3 结点4 结点5 结点6 链表中结点的个数:5

本文分享自微信公众号 - 好好学java(SIHAIloveJAVA)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微信公众号支付开发全过程(java版)

    首先我们到微信支付的官方文档的开发步骤(https://pay.weixin.qq.com/wiki/doc/api/jsapi.php?chapter=7_3...

    好好学java
  • 使用Spring Boot进行参数校验

    原文:cnblogs.com/cjsblog/p/8946768.html 编辑自公众号:Java后端

    好好学java
  • java实现沙箱测试环境支付宝支付和整合微信支付和支付宝支付到ssm(附源码)

    下载地址:https://docs.open.alipay.com/270/106291/

    好好学java
  • 链表的天然递归结构性质

    1、在一个头结点+更小的链表基础上,从更小的链表中删除指定元素,得到一个全新的链表--图中红丝的方块。

    wfaceboss
  • 【go】剑指offer: 删除链表结点O(1)时间复杂度

    给定单链表的头指针和一个结点指针,定义一个函数在O(1)时间删除结点,链表结点与函数的定义如下:

    陌无崖
  • 面试现场如何实现链表的逆序?

    前几天一位小伙伴去面试,被要求现场写如何实现链表的逆序?写完一种问还有没有其他方式?

    用户4143945
  • 二十一世纪领先的是科技也是人工智能

    人工智能 近日一阵人工智能的热潮进入大众的视野。2017年,人脸识别、语音识别、无人驾驶、AI芯片等领域不断取得新突破。人工智能(Artificial Inte...

    企鹅号小编
  • 快速学习-Skywalking的RPC调用-Dubbo的最佳实践

    接下来为大家提供一些简单使用Dubbo服务调用的项目代码演示, 大家可以参考下面简单版 或者详细请参照Demo中的脚手架示例scaffold-dubbo-de...

    cwl_java
  • SQN算法效果及代码: Breakout-ram-v4 打砖块

    再看LunarLander-v2的效果(也是比较简单了。。。),AverageEpRet就是不上300... : (

    用户1908973
  • 剑指offer第4题:从头到尾打印链表

    题目要求我们从尾到头打印数组,首先应该想到我们肯定是需要对整个链表进行一个反序操作。所以联想到我们之前做过的反转链表题目,这道就解出来了。

    鹏-程-万-里

扫码关注云+社区

领取腾讯云代金券