public class CircularLinkedList<T> {
private Node<T> head; // 头节点
private Node<T> tail; // 尾节点
// 节点类
private static class Node<T> {
T data; // 节点存储的数据
Node<T> next; // 指向下一个节点的指针
Node(T data) {
this.data = data;
this.next = null;
}
}
// 在链表末尾添加节点
public void add(T data) {
Node<T> newNode = new Node<>(data);
if (head == null) {
head = newNode;
tail = newNode;
tail.next = head; // 将尾节点的next指向头节点,形成循环
} else {
tail.next = newNode; // 将尾节点的next指向新节点
tail = newNode; // 更新尾节点为新节点
tail.next = head; // 将尾节点的next指向头节点,形成循环
}
}
// 在链表指定位置插入节点
public void insert(int index, T data) {
if (index < 0 || index > size()) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
}
Node<T> newNode = new Node<>(data);
if (index == 0) {
newNode.next = head; // 将新节点的next指向头节点
head = newNode; // 更新头节点为新节点
tail.next = head; // 将尾节点的next指向头节点,形成循环
} else {
Node<T> current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next; // 找到要插入位置的前一个节点
}
newNode.next = current.next; // 将新节点的next指向当前节点的next
current.next = newNode; // 将当前节点的next指向新节点
if (current == tail) {
tail = newNode; // 如果插入位置是尾节点后面,则更新尾节点为新节点
}
}
}
// 删除链表指定位置的节点
public void remove(int index) {
if (index < 0 || index >= size()) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
}
if (index == 0) {
head = head.next; // 将头节点指向下一个节点
tail.next = head; // 将尾节点的next指向头节点,形成循环
} else {
Node<T> current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next; // 找到要删除节点的前一个节点
}
current.next = current.next.next; // 将当前节点的next指向要删除节点的下一个节点
if (current.next == head) {
tail = current; // 如果删除的是尾节点,则更新尾节点为当前节点
}
}
}
// 获取链表的大小
public int size() {
int count = 0;
Node<T> current = head;
while (current != null) {
count++;
current = current.next;
if (current == head) {
break; // 如果回到头节点,说明遍历完整个循环链表
}
}
return count;
}
}