Java数据结构--循环链表

一、简介

1.1 概念

对于单链表而言,最后一个结点的地址为空,如果表示最后一个结点的指针域指向头结点,整个链表形成一个环,就构成了单循环链表。
与单链表相比,只是将原来判断指针是否为空变为判断是否是头指针,没有其他的变化。
访问单循环链表某一结点,可以从任何一个结点开始,顺序向后遍历到达要访问的结点。

1.2 优点

插入、删除时,只要找到对应前驱结点,修改指针即可,无需移动元素;
采用动态存储分配,不会造成内存浪费和溢出。

1.3 缺点

在有些高级语言中, 不支持指针,不容易实现;
需要用额外空间存储线性表的关系,存储密度小;
不能随机访问,查找时要从头指针开始遍历,查找元素的时间复杂度较大。

1.4 结构图

在这里插入图片描述

二、简单实现

public class CirLinkedList<E> {
	Node front; // 循环链表表头指针
	Node rear; // 循环链表表尾指针
	int length; // 表长度 
	
	private class Node {
		public E e;
		public Node next;
		
		public Node() {
			e = null;
			next = null;
		}
	}

	public CirLinkedList(){
		this.rear = this.front = null;
		this.length = 0;
	}

	/**
	 * 插入元素
	 * @param e 需要插入的元素
	 */
	public void insert(E e) {
		Node node = new Node();
		node.e = e;

		if (this.length == 0) {
			front = rear = node;
		}else {
			rear.next = node;
			rear = node;
		}

		rear.next = front;
		this.length = length + 1;
	}

	/**
	 * 查询
	 * 1、在链表中查找某位置结点,则从链表头结点位置开始不断向下遍历链表,直到查找到对应位置的结点结束
	 * 2、返回查找结点,否则结点不存在。
	 *
	 * @param i 要查询的节点位置
	 * @return 要查询的节点
	 */
	public Node query(int i) {
		Node p = front;
		if (i < 0 || i > length) {
			return p;
		}
		if (i == 1) {
			return p;
		}
		for (int j = 1; j <= i; j++) {
			p = p.next;
		}
		return p;
	}

	/**
	 * 删除结点
	 *
	 * 1、找到删除结点直接前驱对应的位置,若存在则继续,否则结束;
	 * 2、若要删除的结点存在则继续,否则继续;
	 * 3、删除对应位置结点,结束。
	 *
	 * @param i 要删除节点的位置
	 */
	public Node delete(int i) {
		Node node = new Node(); // 保存删除的第i个结点

		// 判断删除位置是否正确
		if (i < 0 || i > length) {
			System.out.println("删除位置i无效");
			return null;
		}
		// 查找要删除结点的前一个元素
		Node p = query(i - 1);
		node = p.next;
		p.next = node.next;
		length--;
		return node;
	}
	
}

三、使用

	public static void main(String[] args) {
		CirLinkedList<String> cirLinkedList = new CirLinkedList<>();
		cirLinkedList.insert("1");
		cirLinkedList.insert("2");
		cirLinkedList.insert("3");

		System.out.println(cirLinkedList.query(1).e);

	}

在这里插入图片描述

热门文章

暂无图片
编程学习 ·

vue+element-ui JYAdmin后台管理系统模板-集成方案【项目搭建篇1】

项目搭建时间:2020-06-29 本章节:讲述基于vue/cli, 项目的基础搭建。 本主题讲述了vue+element-ui JYAdmin 后台管理系统模板-集成方案,从零到一的手写搭建全过程。 该项目不仅是一个持续完善、高效简洁的后台管理系统模板,还是一套企业级后台系统开发集成方案,致力…
暂无图片
编程学习 ·

JVM - G1&ZGC初探

文章目录GC概述参考GC概述 我们知道Serial 、Serial Old 、 Parallel 、 Parallel Old 、 ParNew 、CMS这些垃圾收集器都是基于分代收集理论,即将内存区域按照存储对象的不同分为年轻带、老年代和元空间。如下G1 和 ZGC 逐渐淡化了这种分代的概念,G1的堆内存分配如下堆被划分…
暂无图片
编程学习 ·

数据重删和数据压缩主流技术分析

数据压缩随着计算能力的不断提升,当代社会正在产生越来越巨量的数据,数据压缩也被应用在生活的方方面面,如在网上打开的图片、视频、音频等都是经过压缩的。压缩可以分为无损压缩和有损压缩。无损压缩可以通过压缩文件完全恢复原始文件;而有损压缩则会丢失一部分信息。对于…
暂无图片
编程学习 ·

都说Python容易自学,那如何系统的学习Python

做Python开发十年,给大家详细分析一下这个问题 首先告诉你的是,零基础学习开始系统学习Python肯定难,Python的专业程度本身就不简单,学习这事本来就是一件非常煎熬的事情,人都不愿意学习,可是没办法,为了生存掌握一个技能,你必须学,如果你认真的对待,你就找不到高薪水…
暂无图片
编程学习 ·

kubectl源码分析之config delete-context

发布一个k8s部署视频:https://edu.csdn.net/course/detail/26967课程内容:各种k8s部署方式。包括minikube部署,kubeadm部署,kubeasz部署,rancher部署,k3s部署。包括开发测试环境部署k8s,和生产环境部署k8s。腾讯课堂连接地址https://ke.qq.com/course/478827?taid=4373…
暂无图片
编程学习 ·

easyui datagrid deleteRow(删除行)的BUG

有时候想临时保存一些数据,等确定好后在批量一次提交,但EasyUI datagrid 用的时候添加可以正常,如果从中间删除那行号就全乱了。导致删除的时候有可能删除上一行数据。function addFileRow(){$(#FileTable).datagrid(appendRow,{ File_Name:"aaaa",File_Path:&qu…
暂无图片
编程学习 ·

深入浅出计算机组成原理 函数调用(自我提升第二十二天)

昨天6月30号,菜鸟去搞了半天的手机套餐什么的,然后我妈换了个华为的手机,忍不住想玩玩,所以鸽了/(ㄒoㄒ)/~~ 今天就补昨天的咯,然后再写一篇或者两篇,具体看看有没有什么事,话不多说,冲冲冲 这里我一篇是菜鸟提取的,不然就是讲单片机了,不是菜鸟自己总结的/(ㄒoㄒ)/~…
暂无图片
编程学习 ·

大学的生活给你的现在带来了什么?

《你的大学四年为现在的你提供什么优势了》初入大学的时候,我们每个人心里都存着渴望、好奇,有多少人在报完志愿的那一刻,心中的大学还是那些偶像剧中的样子。收到通知书的我们,都在彼此炫耀,终于走进了大学,可以自己做主的生活,没有家人约束的日子。走进大学的校门,多…
暂无图片
编程学习 ·

python pytest selenium 自动化测试框架搭建

python pytest selenium 自动化测试框架搭建公司一直有这个自动化测试需求,前期利用c++或者python进行了一些自动化脚本的编写。这几天没有版本更迭,基于前期的工作,把自动化测试整理了一部分功能模块。现在的状态基本达到预期:即搭建了一个AutoTest框架,基于此实现了logi…
暂无图片
编程学习 ·

老鸟带你回顾新人Java不容错过的八本好书

回头看看, 我进入Java 领域已经快15个年头了, 虽然学的也一般, 但是分享下我的心得,估计也能帮大家少走点弯路。 [入门] 我在2001年之前是C/C++阵营, 有C和面向对象的基础, 后来转到Java ,发现没有指针的Java真是好简单, 另外Java 的类库好用的让人哭啊。 后来我就看《…
暂无图片
编程学习 ·

windows 搭建es 集群 使用cerebro

1.2.一次修改三个节点下配置文件具体操作:主节点nodecluster.name: my-applicationnode.name: nodenode.master: truenode.attr.rack: r1network.host: 127.0.0.1http.port: 9200transport.tcp.port: 9300discovery.seed_hosts: ["127.0.0.1:9300","127.0.0.1:…
暂无图片
编程学习 ·

Portworx Essentials 视频讲解

Portworx Essentials vs. Portworx Enterprise:https://www.iqiyi.com/v_19rzfuk1yw.html欢迎回到Portworx讲解视频系列,我是Ryan Warner。今天我们来介绍一下Portworx Essentials版本,以及与Portworx Enterprise版本的区别。Portworx Essentials是在K8S上运行数据管理的最必…
暂无图片
编程学习 ·

解决 java “错误:编码GBK 的不可映射字符”

今天一个学弟遇到这样的问题,如下图所示。 看到这样的问题,我的思考是: 1.首先是使用javac -version查看环境变量是否正确 2.然后查看编译路径是否存在中文 3.查看代码本身是否有中英文符号混淆 4.右击dos窗口,查看其属性中的编码集是否是utf-8 代码本身没问题,可以在exli…
暂无图片
编程学习 ·

k8s(1)

k8s-集群搭建的三种方式,目前主流的搭建k8s集群的方式有kubeadm、minikube,二进制包。kubeadm 是一个工具,用于快速搭建kubernetes集群,目前应该是比较方便和推荐的,简单易用 kubeadm是Kubernetes 1.4开始新增的特性 kubeadm init 以及 kubeadm join 这两个命令可以快速创…