文章目录
- 简介
- Java 实现
单向循环链表,是在单向链表的基础上增加了循环这一个特性,单向循环链表可以使用两个结点,头结点和尾结点,但是如果只是用一个结点的话方便与两个单向循环链表的拼接
下方代码实现中实现了两个单向循环链表的拼接
逻辑思路
// 结点
class Node {
int data;
Node next = null;
}
// 单向循环链表
public class SinglyLinkedCircularList {
// 头结点
private Node head;
// 初始化
public SinglyLinkedCircularList() {
head = new Node();
head.next = head;
}
// 头插法创建单向循环链表(倒序)
public void createFromHead(int[] arr) {
for (int i = 0; i < arr.length; i++) {
Node node = new Node();
node.data = arr[i];
node.next = head.next;
head.next = node;
}
}
// 尾插法创建单向循环链表(正序)
public void createFromTail(int[] arr) {
Node h = head;
for (int i = 0; i < arr.length; i++) {
Node node = new Node();
node.data = arr[i];
node.next = h.next;
h.next = node;
h = node;
}
}
// 新增
public void add(Node n) {
Node h;
for (h = head; h.next != head; h = h.next);
n.next = h.next;
h.next = n;
}
// 查找
public void search(int num) {
int k = 0;
for (Node h = head; h.next != head; k++,h = h.next);
if (num < 1 || num > k)
throw new Exception("数字超过范围!");
Node h = head;
for (int i = 1; i <= num; i++,h = h.next);
return h.data;
}
// 插入
public void insert(int num, Node n) throws Exception {
int k = 0;
for (Node h = head; h.next != head; k++,h = h.next);
if (num < 1 || num > k)
throw new Exception("数字超过范围!");
Node h = head;
for (int i = 1; i < num; i++,h = h.next);
n.next = h.next;
h.next = n;
}
// 删除
public int delete(int num) throws Exception {
int k = 0;
for (Node h = head; h.next != head; k++,h = h.next);
if (num < 1 || num > k)
throw new Exception("数字超过范围!");
Node h = head;
for (int i = 1; i < num; i++,h = h.next);
int e = (h.next).data;
h.next = (h.next).next;
return e;
}
// 得到单向循环链表中结点个数
public int getCapability() {
int count = 0;
for (Node h = head; h.next != head; count++,h = h.next);
return count;
}
// 得到单链表头结点
public Node getHead() {
return head;
}
// 将新单向循环链表拼接到尾部
public void spliceSinglyLinkedCircularList(SinglyLinkedCircularList slcl) {
Node h;
for (h = head; h.next != head; h = h.next);
Node h2;
for (h2 = slcl.getHead(); h2.next != slcl.getHead(); h2 = h2.next);
h2.next = h.next;
h.next = slcl.getHead();
}
}