java数据结构单向循环链表的实现

一、
由图可以看出&＃xff0c;单项循环链表和普通单链表的区别在于尾节点&＃xff0c;普通单链表的为节点指向一个空的位置&＃xff0c;表示这个节点是链表的族最末端&＃xff0c;而循环链表的尾节点则指向该链表的头结点&＃xff0c;形成一个环状结构&＃xff0c;首尾相连。
二、
1、空表的循环列表是头结点的后继指针指向首结点自身 head.next&＃61;head&＃xff1b;
2、循环列表中&＃xff0c;尾结点后继指针指向了头结点 rear.next&＃61;head
3、与单链表的区别还有一点&＃xff0c;就是关于循环遍历链表时的判断条件&＃xff0c;单链表的循环体的结束条件是p &＃61; &＃61; null&＃xff0c;而单向循环链表的循环判断条件是p.next &＃61; &＃61; head&＃xff0c;如下代码所示&＃xff1a;

//单链表
Node p &＃61; this.head
while(p!&＃61;null){}
//单向循环链表
Node p &＃61; this.head
while(p.next!&＃61;head){
}


3.1首先每个链表都是有节点组成的&＃xff0c;每个节点都包含该节点所存储的数据和该节点后继得地址&＃xff0c;所以需要定义一个节点类

/*** 结点类* &＃64;author Administrator*/public class Node {private E data;//存储数据private Node next;public Node(E data){this.data&＃61;data;}public Node(E data,Node next){this.data&＃61;data;this.next&＃61;next;}}


3.2循环链表的接口与单链表一致&＃xff0c;为线性表

/*** 链表的接口,包含所有* 链表的基本方法* &＃64;author Administrator**/
public interface List {//判断链表是否为空boolean isEmpty();//链表长度int length();//获取元素E get(int index);//根据index添加元素dataE set(int index,E data);//根据index添加元素databoolean add(E data);//根据index插入元素boolean add (int index,E data);//删除指定位置的元素E remove(int index);//删除指定元素boolean remove(E data);//根据data移除所有相同元素E removeAll(E data);//清空链表void clear();//是否包含特定元素boolean contains(E data);//获取元素的位置int indexOf(E data);//根据data值查询最后一个出现在顺序表的下标int lastIndexOf(E data);// 输出格式String toString();
}

3.3在SingLoop类中实现List接口,声明头结点和尾节点以及其构造方法

private Node head; //头结点private Node rear; //尾节点private int size; //链表的长度public LoopSingle() {head &＃61; null;rear &＃61; null;size &＃61; 0;}public LoopSingle(E[] arr) {this();for(E e:arr) {addLast(e);}}


判断链表是否为空&＃xff1a;由于链表的结构特点&＃xff0c;头结点是链表的开始位置&＃xff0c;所有判断链表是否为空&＃xff0c;只要判断链表的头结点是为空

public boolean isEmpty() {return size &＃61;&＃61; 0&&head &＃61;&＃61; null&&rear &＃61;&＃61; null;
}


获取元素&＃xff1a;由于链表的结构特点&＃xff0c;获取链表首先声明变量count&＃xff08;从0开始&＃xff09;来表示结点指向的位置&＃xff0c;需要依次按照后继指针循环直到获取结点从而取得结点存储的数据。从程序来看&＃xff0c;链表获取元素在最坏情况下需要依次遍历所结点&＃xff0c;最好情况下时间复杂度为O&＃xff08;1&＃xff09;&＃xff0c;最坏情况下时间复杂度O&＃xff08;n&＃xff09;。而特别注意结点的结束判断&＃xff0c;避免死循环。

public E get(int index) {if(index<0||index>&＃61;size) {throw new IllegalArgumentException("查找角标非法");}if(index &＃61;&＃61; 0){return head.data;}else if(index &＃61;&＃61; size) {return rear.data;}else {Node p &＃61; head;for(int i &＃61; 0;i}


修改指定位置的元素&＃xff1a;在获取元素位置时&＃xff0c;与获取元素位置相同&＃xff0c;修改元素只是在获取元素后用新的存储数据替换旧的存储数据data。在时间复杂度上&＃xff0c;与获取元素相同。

public void set(int index, E e) {if(index<0||index>&＃61;size) {throw new IllegalArgumentException("修改角标非法");}if(index &＃61;&＃61; 0){head.data &＃61; e;}else if(index &＃61;&＃61; size) {rear.data &＃61; e;}else {Node p &＃61; head;for(int i &＃61; 0;i}


添加元素&＃xff1a;单链表添加元素主要分为四种场景&＃xff0c;a.空链表插入结点&＃xff1b;b.头结点插入元素&＃xff0c;新增结点为头结点&＃xff1b;c.中间情况插入节点&＃xff1b;d.尾结点插入元素&＃xff0c;也就是在插入在单链表末尾

public void add(int index, E e) {if(index<0||index>size) {throw new IllegalArgumentException("插入角标非法");}Node n &＃61; new Node(e,null);if(isEmpty()) { //为空的情况head &＃61; n;rear &＃61; n;rear.next&＃61;head;}else if(index &＃61;&＃61; 0) { //头插n.next &＃61; head;head &＃61; n;rear.next &＃61; head;}else if(index &＃61;&＃61; size){ //尾插n.next &＃61; head;rear.next &＃61; n;rear &＃61; n;}else { //一般情况Node p &＃61;head;for(int i &＃61; 0;i}


删除指定位置的元素&＃xff1a;删除元素与插入结点类型&＃xff0c;首先要先找到要删除指定位置的索引位置分为三种情况&＃xff0c;删除头结点&＃xff0c;删除中间位置结点&＃xff0c;删除尾结点

public E remove(int index) {if(index<0||index>&＃61;size) {throw new IllegalArgumentException("删除角标非法");}E res &＃61; null;if(size &＃61;&＃61; 1) {res &＃61; head.data;head &＃61; null;rear &＃61; null;}else if(index &＃61;&＃61; 0) {res &＃61; head.data;head &＃61; head.next;rear.next &＃61; head;}else if(index &＃61;&＃61; size-1) {res &＃61; rear.data;Node p &＃61; head;while(p.next!&＃61;rear) {p&＃61;p.next;}p.next &＃61; rear.next;rear &＃61; p;}else {Node p &＃61; head;for(int i &＃61; 0;i}


查找链表中是否存在某个元素&＃xff1a;如果链表为空则返回-1&＃xff0c;否则定义一个指针从第一个节点开始判断&＃xff0c;每部循环都对index进行&＃43;1操作&＃xff0c;如果查找到&＃xff0c;则返回index&＃xff0c;否则返回-1

public int find(E e) {if(isEmpty()) {return -1;}Node p &＃61; head;int index &＃61; 0;while(p.data!&＃61;e) {p &＃61; p.next;index&＃43;&＃43;;if(p &＃61;&＃61; head) {return -1;}}return index;
}


清空链表&＃xff1a;可以直接使头结点和尾节点指向空&＃xff0c;size&＃61;0。

public void clear() {head &＃61; null;rear &＃61; null;size &＃61; 0;}


最后输出格式&＃xff1a;

public String toString() {StringBuilder sb &＃61; new StringBuilder();sb.append("loopSingle:size &＃61; " &＃43; getsize() &＃43; "\n");if(isEmpty()) {sb.append("[]");}else{sb.append(&＃39;[&＃39;);Node p &＃61; head;while(true) {sb.append(p.data);if(p.next &＃61;&＃61; head) {sb.append(&＃39;]&＃39;);break;}else {sb.append(&＃39;,&＃39;);}p &＃61; p.next;}}return sb.toString(); }


总结&＃xff1a;单向循环链表与普通链表的区别主要是在尾结点的判断&＃xff0c;查询的时间复杂度都为O&＃xff08;1&＃xff09;&＃xff0c;插入和删除的时间复杂度为O&＃xff08;n&＃xff09;