- A+
什么是单向循环链表?
将单链表中终端节点的指针端由空指针改为指向头节点,就使整个单链表形成一个环,这种头尾相接的单链表称为单循环链表,简称循环链表。
如下图所示:
从上图可以看出,其循环就是尾节点的next指针域指向头节点的元素位置,头与尾相连形成循环状。
节点信息
单向循环链表与单链表的结构类似,没有太大变化,如下代码:
package link.singlelooplink;
/**
* @Description 链表节点 单体循环链表
* @author lmx.zh
* @date 2019-06-14 16:39
* @Copyright 2019 Alibaba.com All right reserved.
*/
public class Node {
/**
* 链表元素
*/
Object data;
/**
* 链表后续节点
*/
Node next;
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
附上单向循环链表的一些必要的变量
/**
* @Description 单体循环链表
* @Author lmx.zh
* @date 2019-06-19 15:47
* @Copyright 2019 Alibaba.com All right reserved.
*/
public class SingleLoopLink {
/**
* 头节点
*/
Node head;
/**
* 链表大小
*/
int size;
/**
* 尾节点
*/
Node last;
}
- head 节点记录链表的头节点;
- size 记录链表的大小,每增加或减少一个节点都做相应的递增或递减;
- last 节点记录链表的尾节点,在增加节点时也可以作为临时节点;
增加节点
/**
* 增加元素
*
* @param item
*/
public void addItem(Object item) {
//临时节点
Node tmp = last;
Node newNode = new Node(item, null);
//设置最后节点为新节点
last = newNode;
//如果节点为空时,则标识该链表为空节点
if (tmp == null) {
//设置头节点
head = newNode;
//因为是循环单链表,设置头节点的下一个节点是自己
head.next = newNode;
} else {
//上一个节点的指针为新节点
tmp.next = newNode;
//设置最后一个节点为头节点
last.next = head;
}
//链表递增
++size;
}
增加节点与单链表大体相似,只需对头节点与尾节点做特殊处理
1. 如果链表只有头节点一个,头节点的next指针域指向自己;
2. 如果有多个节点,链表的尾节点不在指向null,而是指向头节点;
删除节点
/**
* 删除元素
*
* @param item
* @return
*/
public boolean removeItem(Object item) {
boolean loop = true;
boolean flag = false;
//首节点
Node p = head;
//需要删除的节点
Node n = head.next;
//根据条件循环整个循环单链表
while (loop) {
//判断节点中的元素是否是将要删除的元素
if (n.data.equals(item)) {
//如果需要删除的节点是头节点
if (n == head) {
//则将上一个节点,也就是尾节点的指针指向头节点的下一个节点 即 p.next -> head.next
p.next = n.next;
//将头节点设置为第二个节点,即头节点的下一个节点 head(头节点) -> n(需要删除的节点,是当前的头节点).next
head = n.next;
}//如果需要删除的是尾节点
else if (n.next == head) {
//尾节点的指针指向的是头节点,所以将上一个节点的指针指向头节点 即p.next -> head
p.next = head;
} //如果需要删除的是中间节点
else {
//直接将上一个节点的指针指向需要删除节点的下一个节点 即 p.next -> n.next
p.next = n.next;
}
//将需要删除的节点的指针指向空 n.next -> null
n.next = null;
//为了防止内存泄露,将删除的节点设置为null,也就是手动回收掉 n -> null
n = null;
//设置循环条件为fasle,停止循环
loop = false;
//删除成功标识
flag = true;
//节点条数递减
--size;
//跳出循环
break;
}
//如果需要删除的元素没有匹配上,则继续循环,将p设置下个节点,n设置为下下一个节点,依次循环链表
p = n;
n = n.next;
}
//返回最终删除标志
return flag;
}
删除节点因为没有定义固定的头节点,所以需要对第一个节点和最后一个节点进行特殊处理,写的有点复杂了
1. 从第一个节点开始依次循环单向循环链表;
2. 如果循环的节点中数据元素匹配到待删除元素,则进行判断
3. 如果待删除的元素为第一个节点,将尾节点的指针域next指向第一个节点的下一个节点,即 p.next = head.next,将head节点设置为第二个节点,即 head = n.next;
4. 如果待删除的元素为尾节点,将尾节点上一个节点的next指针域指向第一个节点,即 p.next = n.next(head);
5. 如果为中间节点,将上一个节点的next指针域指向下一个节点的next指针域,即 p.next = n.next;
6. 最后将待删除的节点next指针域以及数据元素置空。
查询节点数据元素
/**
* 查询节点元素
*
* @return
*/
public Object[] queryItem() {
//设置循环后元素数组
Object[] o = null;
if (size != 0) {
o = new Object[size];
//设置头节点,依次循环
Node first = head;
//设置头节点元素
o[0] = first.data;
//设置第二个节点
Node current = first.next;
//链表下标
int i = 1;
//如果当前节点不是头节点,继续循环取及诶单元素
while (current != first) {
//存储链表中的元素
o[i] = current.data;
//循环链表下一个节点,知道节点为头节点跳出循环
current = current.next;
++i;
}
}
return o;
}
查找元素与单链表思想一致,循环当前节点,将节点数据元素放入数组中,并且返回即可。
总结
单向循环链表其实最需要注意的就是head节点和last节点,增加节点时,如果只有head节点,则next指针域指向自己,如果存在多个节点last节点next指针域不再指向null,需要指向head节点。删除节点时,一定要关注head节点与last节点,也就是说无论是删除head节点还是last节点,最终结果head节点都要与last节点相连,这样才会是完整的单向循环链表。还是那句老话,写代码之前先画图,看图写代码就再也不会找到指针域了。
ps:上述的例子中,没有使用固定的头节点,使用固定的头节点会使链表操作更简单,不用去对head节点与last节点做特殊处理,后续有时间会补上固定头节点的代码实现方式。
- 我的微信
- 加好友一起交流!
-
- 微信公众号
- 关注公众号获取分享资源!
-