“365算法每日学计划”：06打卡-单向循环链表
“365算法每日学计划”：06打卡-单向循环链表
好好学java
发布于 2018-08-01 16:32:56
发布于 2018-08-01 16:32:56
一、单向循环链表：
1、概念：
单向循环链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。
和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。
和单链表相同，循环单链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作时，算法实现较为方便。
带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于：
（1）在构造函数中，要加一条head.next = head 语句，把初始时的带头结点的循环单链表设计成上图中（a）所示的状态。
（2）在index(i)成员函数中，把循环结束判断条件current != null改为current != head。
2、单链表的代码实现：
1、结点类Node的实现代码
public class Node {
public Object data;//保存当前结点的数据
public Node next;//指向下一个结点
public Node(Object data){
this.data = data;
}
} 2、循环链表类CircleList的实现代码
public class CircleList {
private Node head;
public CircleList(){
head = new Node(0);
head.next = null;
}
//在指定位置插入结点
public boolean insert(Object data,int pos){
boolean ret = (head != null) && (data != null) && (pos >= 0);
if(ret){
Node node = new Node(data);
if(head.next == null){
//插入的结点前，循环链表中没有结点。
head.next = node;
node.next = node;
}else{
if(pos >= (Integer)head.data){
pos = (Integer)head.data;
}
Node currentNode = head.next;
//若currentNode.next == head.next，就说明currentNode是最后一个结点
for(int i = 0;(i < pos) && (currentNode.next != head.next);i++){
currentNode = currentNode.next;
}
node.next = currentNode.next;
currentNode.next = node;
//插入位置的下标为0时
if(pos == 0){
head.next = node;
}
}
head.data = (Integer)head.data + 1;
}
return ret;
}
//获取链表中下标为pos的结点
public Object get(int pos){
Object ret = null;
if(head != null && pos >= 0 && pos < (Integer)head.data){
Node node = head;//头结点
//找到要删除的结点
for(int i = 0;i<=pos;i++){
node = node.next;
}
if(node != null){
ret = node.data;
}
}
return ret;
}
//删除链表中下标为pos的结点
public Object delete(int pos){
Object ret = null;
if(head != null && pos >= 0 && pos < (Integer)head.data){
Node node = head;//头结点
Node currentNode = null;//要删除的结点
//找到要删除结点的前一个结点
for(int i = 0;i<pos;i++){
node = node.next;
}
currentNode = node.next;
//获取要删除结点的数据
if(currentNode != null){
ret = currentNode.data;
}
//要删除的结点是循环链表中的第一个结点
if(head.next == currentNode){
head.next = currentNode.next;
}
//删除结点
node.next = currentNode.next;
head.data = (Integer)head.data - 1;
}
return ret;
}
//清空链表
public void clear(){
if(head != null){
head.data = 0;
head.next = null;
}
}
//注销链表
public void destroy(){
if(head != null){
head = null;
}
}
//获取链表中结点的个数
public int length(){
int ret = -1;
if(head != null){
ret = (Integer)head.data;
}
return ret;
}
//打印循环链表中的数据
public void display(){
if(head != null){
Node node = head;
for(int i = 0;i < (Integer)head.data;i++){
node = node.next;
System.out.print(node.data+" ");
}
}
}
} 3、测试类Test的代码
public class Test {
public static void main(String[] args) {
CircleList list = new CircleList();
list.insert("结点1", 0);
list.insert("结点2", 1);
list.insert("结点3", 2);
list.insert("结点4", 3);
list.insert("结点5", 4);
list.insert("结点6", 5);
System.out.println("链表中的元素为：");
list.display();
System.out.println("\n链表中结点的个数："+list.length());
System.out.println("\n获取链表中下标为2的结点："+list.get(2));
System.out.println("删除链表中下标为0的结点："+list.delete(0));
System.out.println("链表中的元素为：");
list.display();
System.out.println("\n链表中结点的个数："+list.length());
list.clear();
list.destroy();
}
} 4、程序运行结果
链表中的元素为： 结点1 结点2 结点3 结点4 结点5 结点6 链表中结点的个数：6 获取链表中下标为2的结点：结点3 删除链表中下标为0的结点：结点1 链表中的元素为： 结点2 结点3 结点4 结点5 结点6 链表中结点的个数：5
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-07-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录