当前位置：网站首页>动态链表4单向循环链表(LoopSingle实现)
动态链表4单向循环链表(LoopSingle实现)
2022-07-27 16:08:00 【zh_Tnis】
1.单向循环链表的定义。
- 单向循环链表的元素存储和队列的顺序存储ArrayQueueLoop的优化有点像，元素是围绕着连接在一起的，(存放元素)就像一个圆环一样的结构，而不是一条直线。
- 单向循环链表图示。
- 单向循环链表为空时，头指针head和尾指针rear同时指向一个null。
- 单向循环链表实现的接口是List，不像栈链LinkedStack和队列链表LinkedQueue一样相当于调用线性表的链式LinkedList。
2.LoopSingle的定义。
list：是单向循环链表LoopSingle要实现的接口类。
Node：
1、是单向循环链表LoopSingle的内部类。
2、E data 是数据域，用来存放元素。
3、E next是指针域，用来存放下一个元素的地址。
4、Node() 是无参构造函数，创建Node的对象，不传值那么就默认调用这个构造函数。
5、Node(E data,Node null) 是有参构造函数，创建Node类型的对象时，传值那么就调用这个构造函数。
LoopSingle：
1、Node head 是头指针，就是定义了一个Node类型的head变量。用来存放第一个元素。
2、Node rear 是尾指针，就是定义一个Node类型的rear变量。用来存放最后一个元素，也可以用来.next来连接第一个元素，形成一个循环链表。
3、int size 是一个变量，用来存放记录循环链表有几个元素。
4、LoopSingle() 是循环链表的无参构造函数，主函数创建该类的对象时，未传值便调用这个构造函数。
5、LoopSingle(E[] arr) 是循环链表有参构造函数，主函数创建该类对象时，传值便调用该构造函数。
6、boolean equals(Object obj) 是循环链表的一个比较内容方法。
7、String toString() 是循环链表的一个文本表示字符串的方法。
3.单向循环链表元素进链。
1、首先判断插入的位置是否超出范围，超出的话抛异常。
2、再创建一个Node类型的变量n，用来存放插入元素的数据。
3、然后判断元素size的值是否为0，也就是头指针head和尾指针rear都指向一个null。成立的话直接将头指针head和尾指针rear移动到第一个元素位置，进而将尾指针rear的下一跳指向头指针hear的位置，也就是n处。
4、接着判断插入位置是否是index=0的位置，是的话将尾指针的下一跳指向n，n的下一跳指向头指针head，再将头指针head移动到n处。
5、紧接着判断index是不是尾插，也就是index=size，是的话将n的下一跳指向head，再将头指针head的下一跳指向n，最后将头指针head移动到n处。
6、最后如果插入位置是头尾内部位置，创建一个Node类型的p等于头指针head，主要用于遍历到插入位置的上一个元素。然后到达位置后，进行将n的下一跳指向p的下一跳，最后将p的下一跳指向n。
7、每次插入元素记得元素记录符号size累加1。
public void add(int index, E e) {
if(index<0||index>size){ //1
throw new IllegalArgumentException("插入角标非法!");
}
Node n=new Node(e,null); //2
if(isEmpty()){ //特殊情况 3
head=n;
rear=n;
rear.next=head; //循环链表
}else if(index==0){ //头插 4
rear.next=n;
n.next=head;
head=n;
}else if(index==size){//尾插 5
n.next=head;
rear.next=n;
rear=n;
}else{ //一般情况 6
Node p=head;
for(int i=0;i<index-1;i++){
p=p.next;
}
n.next=p.next;
p.next=n;
}
size++; //7
}4.单向循环链表的元素删除。
1、首先判断插入的位置是否超出范围，超出的话抛异常。
2、再创建一个泛型E的变量res，先用来存放一个null。其实就是为了存放删除元素的数据
3、然后判断元素size的值是否为1，也就是整个链表只存在一个元素，那么便删除它。令res存放删除元素的数据，再接着让头指针hear和尾指针rear都指向一个null。
4、接着判断删除位置是否是index=0的位置，是的话继续令res存放删除元素的数据，也就是head.data。然后将头指针head移动到下一跳位置。
5、紧接着判断index是不是尾删，也就是index=size，是的话继续令res存放删除元素的数据，也就是rear.data，在这里需要创建一个Node类型的变量p，主要需要遍历使p移动到删除元素位置的上一个位置。到了后开始让p的下一跳指向尾指针rear的下一跳，最后将尾制作rear移动到p处。
6、最后如果删除位置是头尾内部位置，创建一个Node类型的p等于头指针，主要用于遍历到删除位置的上一个元素。然后到达位置后，创建一个Node类型的del用来存放p的下一跳的数据，其实就是删除元素位置的数据。然后让前边定义的res存放del.data，最后将p的下一跳指向del的下一跳就完成了。
7、每次删除元素后记得元素记录符号size累减1。
public E remove(int index) {
if(index<0||index>=size){ //1
throw new IllegalArgumentException("删除角标非法!");
}
E res=null; //2
if(size==1){ //特殊情况 //3
res=head.data;
head=null;
rear=null;
}else if(index==0){ //4
res=head.data;
head=head.next;
rear.next=head;
}else if(index==size-1){ //5
res=rear.data;
Node p=head;
while(p.next!=rear){
p=p.next;
}
p.next=rear.next;
rear=p;
}else{ //6
Node p=head;
for(int i=0;i<index-1;i++){
p=p.next;
}
Node del=p.next;
res=del.data;
p.next=del.next;
}
size--; //7
return res;
}5.单向循环链表的元素修改。
1、先判断需要修改位置的角标是否合法，不合法抛异常处理。
2、再对需要修改位置进行判断，若是修改位置是头指针head位置的元素，直接令头指针head.data等于e。
3、然后判断修改位置是否为链表最后一个元素，是的话直接令尾指针rear.data等于e。
4、最后就是修改头尾指针中间的元素了，创建一个Node类型的变量p，用来遍历到达修改元素的位置，紧接令p.data等于e就完成修改了。
public void set(int index, E e) {
if(index<0||index>=size){ //1
throw new IllegalArgumentException("修改角标非法!");
}
if(index==0){ //2
head.data=e;
}else if(index==size-1){ //3
rear.data=e;
}else{ //4
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
p.data=e;
}
}6.单向循环链表的元素查找。
1、先判断该循环链表是否为空，空的话直接返回一个初始值-1。
2、然后创建一个Node类型的变量p等于头指针head的数据，主要用来遍历是链表往下走。加上定义一个index为0，用来记录走到那个位置。
3、开始一个while循环，条件为p.data不等于e。循环内容是p每次都指向p的下一跳，指向完后记录位置，也就是使index累加1，再接着判断位置p是否循环回到头指针head位置了，回到原处，循环结束返回-1.
4、循环结束后，如果找到链表中有等于e的元素，那么最后返回index，也就是记录位置的变量值。
public int find(E e) {
if(isEmpty()){ //1
return -1;
}
Node p=head; //2
int index=0; //2
while(p.data!=e){ //3
p=p.next;
index++;
if(p==head){
return -1;
}
}
return index; //4
}7.单向循环链表的比较方法。
1、先对传入的对象obj判断是否为空，为空则返回false。
2、再对该对象obj与this直接判断是否相等，相等直接返回true。
3、最后比较里边内容，将obj强转成LoopSingle<E>即可开始。
4、紧接判断两个对象的元素总和是否相等，相等开始定义一个for循环，从0~getSize()位置移动，循环里边再进行两个对象每个位置都比较一次元素，不相等则返回false，for循环运行完都没有出现不等，那么就可以返回true了。
public boolean equals(Object obj) {
if(obj==null){ //1
return false;
}
if(obj==this){ //2
return true;
}
if(obj instanceof LoopSingle){
LoopSingle<E> l=(LoopSingle<E>) obj; //3
if(this.getSize()==l.getSize()){ //4
for(int i=0;i<getSize();i++){
if(get(i)!=l.get(i)){
return false;
}
}
return true;
}
}
return false;
}8.单向循环链表的以文本方式输出方法。
1、使用线程不安全的StringBuilder类创建对象sb。
2、对循环链式判断是否为空，为空直接返回sb.append("[ ]");。
3、不为空则先连接sb.append("[");。
4、之后创建一个Node类型的p变量，先存放头指针head的数据。
5、然后开始一个while的循环，循环条件为true，开始连接p.data，也就是元素，再进行判断后边加逗号，还是加 ] 。只有满足条件p.data等于rear.data的时候就连接上 ] 。其他元素后边加上逗号，。每次连接完 ] 或者逗号，后记得p指向p的下一跳。
public String toString() {
StringBuilder sb=new StringBuilder(); //1
sb.append("LoopSingle:size="+getSize()+"\n");
if(isEmpty()){ //2
sb.append("[]");
}else{
sb.append('['); //3
Node p=head; //4
while(true){ //5
sb.append(p.data);
if(p.next==head){
sb.append(']');
break;
}else{
sb.append(',');
}
p=p.next;
}
}
return sb.toString();
}9.单向循环链表的全部代码实现。
package com.oupeng.p5链表;
import com.oupeng.p1线性表.List;
public class LoopSingle<E> implements List<E> {
private class Node{
E data; //数据域
Node next; //指针域
@SuppressWarnings("unused")
public Node(){
this(null,null); //无参构造函数
}
public Node(E data,Node next){//元素||数据域 地址||指针域
this.data=data;
this.next=next;
}
@Override
public String toString() { //数据的toString方法
return data.toString();
}
}
private Node head; //头指针变量Node类型
private Node rear; //尾指针变量Node类型
private int size; //记录元素数量
public LoopSingle() { //单向循环链表的无参构造函数
head=null;
rear=null;
size=0;
}
public LoopSingle(E[] arr){ //单向循环链表的有参构造函数
}
@Override
public int getSize() { //获得元素总和的方法
return size;
}
@Override
public boolean isEmpty() { //判断单向循环链表是否为空
return size==0&&head==null&&rear==null;
}
@Override
public void add(int index, E e) { //单向循环链表插入元素方法
if(index<0||index>size){
throw new IllegalArgumentException("插入角标非法!");
}
Node n=new Node(e,null);
if(isEmpty()){ //特殊情况
head=n;
rear=n;
rear.next=head; //循环链表
}else if(index==0){ //头插
rear.next=n;
n.next=head;
head=n;
}else if(index==size){//尾插
n.next=head;
rear.next=n;
rear=n;
}else{ //一般情况
Node p=head;
for(int i=0;i<index-1;i++){
p=p.next;
}
n.next=p.next;
p.next=n;
}
size++;
}
@Override
public void addFirst(E e) { //头插
add(0,e);
}
@Override
public void addLast(E e) { //尾插
add(size,e);
}
@Override
public E get(int index) { //单向循环链表的元素获取
if(index<0||index>=size){
throw new IllegalArgumentException("查找角标非法!");
}
if(index==0){
return head.data;
}else if(index==size-1){
return rear.data;
}else{
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
return p.data;
}
}
@Override
public E getFirst() { //头指针元素获取
return get(0);
}
@Override
public E getLast() { //尾指针元素获取
return get(size-1);
}
@Override
public void set(int index, E e) { //单向循环模式的元素修改
if(index<0||index>=size){
throw new IllegalArgumentException("修改角标非法!");
}
if(index==0){
head.data=e;
}else if(index==size-1){
rear.data=e;
}else{
Node p=head;
for(int i=0;i<index;i++){
p=p.next;
}
p.data=e;
}
}
@Override
public boolean contains(E e) { //判断单向循环链表是否包含e元素
return find(e)!=-1;
}
@Override
public int find(E e) { //获取单向循环链表的元素e的位置
if(isEmpty()){
return -1;
}
Node p=head;
int index=0;
while(p.data!=e){
p=p.next;
index++;
if(p==head){
return -1;
}
}
return index;
}
@Override
public E remove(int index) { //删除单向循环链表的元素
if(index<0||index>=size){
throw new IllegalArgumentException("删除角标非法!");
}
E res=null;
if(size==1){ //特殊情况
res=head.data;
head=null;
rear=null;
}else if(index==0){
res=head.data;
head=head.next;
rear.next=head;
}else if(index==size-1){
res=rear.data;
Node p=head;
while(p.next!=rear){
p=p.next;
}
p.next=rear.next;
rear=p;
}else{
Node p=head;
for(int i=0;i<index-1;i++){
p=p.next;
}
Node del=p.next;
res=del.data;
p.next=del.next;
}
size--;
return res;
}
@Override
public E removeFirst() { //头删
return remove(0);
}
@Override
public E removeLast() { //尾删
return remove(size-1);
}
@Override
public void removeElement(E e) { //删除指定元素e
remove(find(e));
}
@Override
public void clear() { //单向循环链表的清空方法
head=null;
rear=null;
size=0;
}
@Override
public boolean equals(Object obj) { //判断两个对象的内容是否相等的方法
if(obj==null){
return false;
}
if(obj==this){
return true;
}
if(obj instanceof LoopSingle){
LoopSingle<E> l=(LoopSingle<E>) obj;
if(this.getSize()==l.getSize()){
for(int i=0;i<getSize();i++){
if(get(i)!=l.get(i)){
return false;
}
}
return true;
}
}
return false;
}
@Override
public String toString() { //单向循环链表的文本模式输出的方法
StringBuilder sb=new StringBuilder();
sb.append("LoopSingle:size="+getSize()+"\n");
if(isEmpty()){
sb.append("[]");
}else{
sb.append('[');
Node p=head;
while(true){
sb.append(p.data);
if(p.next==head){
sb.append(']');
break;
}else{
sb.append(',');
}
p=p.next;
}
}
return sb.toString();
}
}
边栏推荐
- Knowledge dry goods: basic storage service novice Experience Camp
- 【学习笔记】热点账户问题的解决方案
- Application of knowing things and learning | correlation graph analysis in anti cheating business
- Class not found: “com.parkManagement.dao.DaoTest 测试找不到测试类
- mysql解决唯一索引重复导致的插入失败问题
- 【云图说】 第249期 移动应用安全服务—App的体检中心，全面检测，安全上路！
- js工具-cookie简单封装
- 注释中的{@code}、{@Link} 与＜p＞等标签
- 备份表恢复表
- Hutool string utility class
猜你喜欢
Code compliance: five reasons why developers use helix QAC
解决Reids不能被其他IP访问
XStream reports an error abstractreflectionconverter$unknownfield exception when parsing XML
Convolutional neural network -- Translation of yolov2 (yolo9000) papers
Yanrong technology was selected as Beijing's "specialized and innovative" in 2022 to lead hybrid cloud file storage
Class not found: “com.parkManagement.dao.DaoTest 测试找不到测试类
GIS数据漫谈（五）— 地理坐标系统
Machine learning: IOU of concept understanding
Understand │ what is cross domain? How to solve cross domain problems?
Convolutional neural network -- from r-cnn, fast r-cnn to fast r-cnn, mask r-cnn
随机推荐
golang 等待一组goroutine完成，并带返回值(2)
@DateTimeFormat 接收不到时分秒，转换时报类型异常
Six relationships of classes -- the difference between dependency and Association
Convolutional neural network -- Translation of yolov1 thesis
力压谷歌、英伟达！阿里含光800芯片再获权威测试世界第一
被“赶出”比特大陆之后，詹克团首度发声：将通过法律途径尽快回归！
施耐德电气、欧莱雅等企业巨头如何开放式创新？DEMO WORLD世界创新峰会揭秘
携手三星，vivo将推Exynos980双模5G手机！
WPF做登陆界面
2022 safety officer-c certificate special operation certificate examination question bank and answers
[MCU] 2.3 CPU of AT89S52
[user article] examples of P4 consolidation practice guide disassemble resolve
Convolutional neural network -- Introduction to FPN (feature pyramid networks)
Understand JVM language
Es query limit 10000 data solutions
MySQL solves the problem of insert failure caused by duplicate unique indexes
Knowing things by learning | app slimming down, the way of safety reinforcement under the new generation AAB framework
Configuration and basic use of vim
Big gap? Requirements and conditions for candidates with different academic qualifications to take the postgraduate entrance examination
Profiles vs Permission Sets