“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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2277
来自专栏nnngu

Java中ArrayList与LinkedList的区别

Java中ArrayList与LinkedList的区别 一般大家都知道ArrayList和LinkedList的区别:       1. ArrayList的...

4426
来自专栏武培轩的专栏

剑指Offer-求1+2+3+...+n

package Other; /** * 求1+2+3+...+n * 求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、...

3144
来自专栏俞其荣的博客

ArrayList内部原理解析Header源码分析Footer

2698
来自专栏积累沉淀

JDK源码分析-ArrayList分析

花了两个晚上的时间研究了一下ArrayList的源码, ArrayList 继承自AbstractList 并且实现了List, RandomAccess,...

1775
来自专栏java系列博客

Iterator在ArrayList中的源码实现

1772
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题24二叉搜索树的后序遍历序列

本题有bug,欢迎大神指教! /** * 题目:输入一个整数数组,判断该数组书不是某二叉搜索数的后序遍历的结果。如果是返回true,否则返回false。假设输...

2848
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1092
来自专栏IT可乐

JDK1.8源码(五)——java.util.ArrayList 类

  关于 JDK 的集合类的整体介绍可以看这张图,本篇博客我们不系统的介绍整个集合的构造,重点是介绍 ArrayList 类是如何实现的。 1、ArrayLis...

41111
来自专栏闻道于事

Java常用工具类之时间转换

import java.text.DecimalFormat; import java.text.ParseException; import java...

3376

扫码关注云+社区

领取腾讯云代金券