循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。
循环链表的运算与单链表的运算基本一致。所不同的有以下几点:
1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。
2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。
代码:
public class CircularLinkedList< E> {
private Node< E> head;
private int length; //the length of the list
public CircularLinkedList() {
head = new Node< E>(null, head);
length = 0;
}
public void insertAtPrior(E item) {//在头节点之后加一个节点
Node< E> node = new Node< E>(item, null); //encpsule the item to an node
node.setNext(head.getNext()); //node.next = head.next
head.setNext(node); //head.next = node
length ++;
}
public void add(E item) {//在最后节点上添加一个节点
Node< E> tmp = head;
if (isEmpty()) { // if the list is null
Node< E> node = new Node< E>(item, head); // .. if next == null ?
head.setNext(node);
} else {
Node< E> node = new Node< E>(item, head);
// find the end node of the list
while (head != tmp.getNext()) {
tmp = tmp.getNext();
}
tmp.setNext(node);
}
length++;
}
public E get(int index) { //获取索引处的节点的数据
// 先判断索引正确性
if (index >length || index < 0) {
throw new RuntimeException("索引值有错:" + index);
}else if(isEmpty()){
return null;
}else{
Node< E> tmp =head;
int i= 1;
while (head != tmp.getNext() && i <= index) {
tmp = tmp.getNext();
i++;
}
E e = tmp.getData();
return e;
}
}
public void insert(int index, E item) {//在索引处后添加节点
Node< E> node = new Node< E>(item, null);
Node< E> tmp = head;
int i = 1;
if (index > length || index < 0) {
System.out.println("the index is out of bounds");
} else if (0 == length && 1 == index) {
node.setNext(head);
head.setNext(node);
length++;
} else {
//find the node index
while (head != tmp.getNext() && i <= index) {
tmp = tmp.getNext();
i++;
}
node.setNext(tmp.getNext());
tmp.setNext(node);
length++;
}
}
public void removeFromFront() {//删除头节点之后的第一个节点
Node< E> tmp = head;
if (length < 1) {
System.out.println("The list is null and you can not delete any node!");
} else if (1 == length) {
head.setNext(head);
length--;
} else {
head.setNext(tmp.getNext().getNext());
length--;
}
}
public void remove(int index) {//删除索引处的节点
if (length < 1 || index > length) {
System.out.println("index is out of bounds");
} else if (1 == length && 1 == index) {
head.setNext(head);
length--;
} else {
Node< E> tmp = head;
int i = 1;
//get the node before index
while (head != tmp.getNext() && i < index) {
tmp = tmp.getNext();
i++;
}
tmp.setNext(tmp.getNext().getNext());
length--;
}
}
public void removeFromLast() {//删除最后一个节点
if (length < 1) { // if the list is null
System.out.println("The list is null and you can not delete");
} else if (1 == length) {
head.setNext(head);
length--;
} else {
Node< E> tmp1 = head;
Node< E> tmp2 = head.getNext(); //set tmp2 -tmp1 = 1
while (head != tmp2.getNext()) {
tmp2 = tmp2.getNext();
tmp1 = tmp1.getNext();
}
tmp1.setNext(head);
length--;
}
}
public int getLength() {
return length;
}
public boolean isEmpty() {
return length==0;
}
public void display() {
if (length < 1) {
System.out.println("The list is null");
} else {
Node< E> tmp = head;
while (head != tmp.getNext()) {
tmp = tmp.getNext();
System.out.print(tmp.getData() + " ");
}
}
}
//test the list
public static void main(String[] args) {
CircularLinkedList< Integer> l = new CircularLinkedList< Integer>();
System.out.println(l.isEmpty());
l.add(1);
l.add(2);
l.insertAtPrior(3);
l.insert(2, 4);
l.add(5);
System.out.println("the list is : ");
l.display();
System.out.println();
System.out.println("the length is :" + l.getLength());
l.removeFromFront();
l.removeFromLast();
l.display();
// System.out.println(l.get(3));
}
}
public class Node< E> {
private Node< E> next;
private E data;
public Node(E data) {
this.data = data;
next = null;
}
public Node(E data, Node< E> nextNode) {
this.data = data;
next = nextNode;
}
public void setData(E data) {
this.data = data;
}
public void setNext(Node< E> next) {
this.next = next;
}
public E getData() {
return data;
}
public Node< E> getNext() {
return next;
}
}
分享到:
相关推荐
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
用Java定义一个循环链表,实现链表的基本操作: 初始化*、获取头结点、添加新元素*、删除链表元素 、获取链表元素*、查找链表元素*、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空...
NULL 博文链接:https://bbwang8088.iteye.com/blog/2391835
列举了java中双向循环列表的各个主要类的代码以及迭代器构造方法。
约瑟夫环,用循环链表实现,语言为Java。假设数到三的数出列。程序输出1到10的出列顺序。
JAVA 循环链表, 模板类. 后续将提交JavaScript版本, C语言版本及C++版本
有序链表合并算法动态演示系统是在B/S模式下,在MyEclipse 7.5环境中开发出来的,主要用于教学,对提高教学质量有很大的帮助。
由于在项目中需要用到循环链表,然而在JDK没有其实现,所以用Java语言实现了循环链表,供大家学习和参考。若有任何问题请发送E-Mail:wn_lut@126.com,以交流及改进。 Package:com.utilities.structs 打开方式:...
JAVA实现链表_双向链表
使用java语言编译循环双链表,有三个类,分别是一个接口类,一个循环双链表继承接口的实现类,一个循环双链表的测试类
主要介绍了JAVA 数据结构链表操作循环链表的相关资料,需要的朋友可以参考下
这个循环链表是基于引用的,现实的算法比较简单,但是可以作为参考之用。
类似约瑟夫环问题。有一群人组成一个圈。从头开始按照顺时针方向从1开始依次报数。报到到9的人就离开圈子。其左手边的人接着从1开始报数。依此进行,直到剩最后一个人为止。
循环链表源码,分别用C、C++、JAVA实现,仅供参考
NULL 博文链接:https://128kj.iteye.com/blog/1744646
用java语言将双向链表和循环链表结合起来,数据结构吧课程设计的题目
Amazon 面试题,如何用O(N)实现在链表中找出 是否出现循环(Loop),算法也可以用在其他语言(C,C++等)
05.循环链表仿真链表以及循环链表应用
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
约瑟夫环求解,循环链表的使用,经典问题