数据结构与算法(四)-线性表之循环链表

前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到了尾部标识就停止了向后链的操作。也就是说只能向后走,如果走过了,就回不去了,还得重头开始遍历,所以就衍生出了循环链表

一、简介

  定义:将单链表中中断结点的指针端有空指针改为指向头结点,就使整个单链表形成一个环,这种头尾详解的单链表称为单循环链表,简称循环链表;

  特性: 

  • 若链表为空,则头结点的next结点还是指向其本身,即head.next=head;
  • 尾节点的next指针指向head结点,即头尾相连;
  • 判断是否遍历了完,直接判断next==head即可;
  • 由单链表变化的循环也成为单向循环链表;
  • 循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活;

二、单向循环链表的实现

  循环链表是在单链表(线性单链表)的基础上,将尾节点的next指向了head,所以基本的结构是类似的,所以下面,直接贴代码了;

public class LoopChain<T> {

    //尾结点直接引用
    private Node<T> tail;

    //链长度
    private Integer size;

    //初始化
    LoopChain() {
        tail = new Node<T>();
        tail.setNext(tail);
    }

    public Node<T> remove(Integer index) throws Exception {
        //获取该位置的上一个节点
        Node<T> s = getNode(index - 1);
        //获取该位置节点的下一个节点
        Node<T> next = getNode(index).getNext();
        //将本节点的next节点放在本节点的前一个节点的next节点位置
        s.setNext(next.getNext());
        return next;
    }

    public void add(T t,Integer index) throws Exception {
        //获取该位置的上一个节点
        Node<T> s = getNode(index - 1);
        //创建新节点
        Node<T> p = new Node<>();
        p.setObject(t);
        //将本节点的next节点放入新节点的next节点
        p.setNext(s.getNext());
        //将新节点放入本节点的next节点位置
        s.setNext(p);
    }

    public T get(Integer index) throws Exception {
        return (T)getNode(index).getObject();
    }

    private Node<T> getNode(Integer index) throws Exception {
        if (index > size || index < 0)
            throw new Exception("index outof length");
        //取头节点
        Node<T> p = tail.next;
        for (int i = 0; i < index; i++)
            p = p.getNext();
        return p;
    }

    class Node<T> {

        private Object object;

        private Node next;

        public Object getObject() {
            return object;
        }

        public void setObject(Object object) {
            this.object = object;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

    }

}

  获取元素:

    public T get(Integer index) throws Exception {
        return (T)getNode(index).getObject();
    }

    private Node<T> getNode(Integer index) throws Exception {
        if (index > size || index < 0)
            throw new Exception("index outof length");
        //取头节点
        Node<T> p = tail.next;
        for (int i = 0; i < index; i++)
            p = p.getNext();
        return p;
    }

  插入元素:

    public void add(T t,Integer index) throws Exception {
        //获取该位置的上一个节点
        Node<T> s = getNode(index - 1);
        //创建新节点
        Node<T> p = new Node<>();
        //将本节点的next节点放入新节点的next节点
        p.setNext(s.getNext());
        //将新节点放入本节点的next节点位置
        s.setNext(p);
    }

  移除元素:

    public Node<T> remove(Integer index) throws Exception {
        //获取该位置的上一个节点
        Node<T> s = getNode(index - 1);
        //获取该位置节点的下一个节点
        Node<T> next = getNode(index).getNext();
        //将本节点的next节点放在本节点的前一个节点的next节点位置
        s.setNext(next.getNext());
        return next;
    }

在之前学习单链表的时候,我们使用头结点来代表一个链表,可以用O(1)的时间访问第一个节点,但是在访问尾节点时,需要使用O(n)的时间,而循环链表则不同,完全可以使用O(1)的时间来访问第一个节点和尾节点。

三、问题

判断单链表中是否有环?

  思考:有环的定义是,链表的尾节点指向了链表中的某个节点;

  那么怎么判断是否有环的存在呢?

1、使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,p走的步数是否与q走的步数一致,若不一致则说明存在环;

  若链表长度为3,当p走完一圈后,会出现p的步数为4,而q的步数为1,不相等,则存在环。

2、使用p、q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p==q,则存在环;

  使用了快慢原理来进行判断是否存在环。

注意:

  ①循环链表中没有NULL指针。涉及遍历操作时,其终止条件就不再是像非循环链表那样判别p或p->next是否为空,而是判别它们是否等于某一指定指针,如头指针或尾指针等。

  ②在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。

本系列参考书籍:

  《写给大家看的算法书》

  《图灵程序设计丛书 算法 第4版》

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

44711
来自专栏眯眯眼猫头鹰的小树杈

leetcode347. Top K Frequent Elements

这里有一个额外要求即时间复杂度要优于O(n log n),也就是说我们无法采用先排序再顺序计算的方式来进行统计,因为最好的排序算法其平均的时间复杂度也需要O(n...

782
来自专栏码云1024

List Set Map比较

3424
来自专栏java一日一条

HashMap的实现原理

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒...

2592
来自专栏WD学习记录

牛客网 从上往下打印二叉树

711
来自专栏专注研发

java大数(BigInteger)

 Math类:   java.lang.Math类中包含基本的数字操作,如指数、对数、平方根和三角函数。   java.math是一个包,提供用于执行任意精度整...

3222
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

2576
来自专栏java技术学习之道

HashMap的实现原理

1192
来自专栏程序员互动联盟

读 Java Arrays 源码 笔记

Arrays.java是Java中用来操作数组的类。使用这个工具类可以减少平常很多的工作量。了解其实现,可以避免一些错误的用法。 它提供的操作包括: 排序 so...

36912
来自专栏老马说编程

(55) 容器类总结 / 计算机程序的思维逻辑

从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结: 用法和特点 数据结构和算法 设计思维和模式 用法和特点 我们在52节...

2187

扫码关注云+社区