双向环形链表（一个哨兵）
双向环形链表介绍
双向环形链表是双向链表的一种特殊形式，其特点是链表的头节点和尾节点相互连接，形成一个环。相较于普通双向链表，环形结构使得链表可以在任意节点上循环遍历，非常适合某些场景，例如实现循环队列、游戏中的回合逻辑等。
双向环形链表的特点
1，环形结构：头节点的 prev 指向尾节点，尾节点的 next 指向头节点。
2，双向性：每个节点都可以通过 prev 向前，或者通过 next 向后遍历。
3，没有 null 节点：对于非空链表，遍历过程中不会遇到 null。
4，动态长度：节点数量可以随插入或删除操作动态调整。
应用场景
1，循环队列：在固定大小的数据结构中实现循环访问。
2，游戏设计：实现玩家的回合制逻辑。
3，操作系统：任务调度器中，双向环形链表可以高效管理任务队列。
代码实现
import java.util.Iterator;
//带（一个）哨兵节点
public class CircularDoublyLinked implements Iterable<Integer> {
private static class Node {
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
}
private Node sentinel = new Node(null,-1,null);//实例化
public CircularDoublyLinked() {
sentinel.prev = sentinel;//初始化
sentinel.next = sentinel;//初始化
}
public void addFirst(int value) {//头插
Node prev = sentinel;
Node next = sentinel.next;
Node inserted = new Node(prev,value,next);
prev.next = inserted;
next.prev = inserted;
}
public void removeFirst() {//头删
Node removed = sentinel.next;
if (removed == sentinel) {
throw illegalIndex(0);
}
Node prev = sentinel;
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
public void addLast(int value) {//尾插
Node next = sentinel;
Node prev = sentinel.prev;
Node inserted = new Node(prev,value,next);
next.prev = inserted;
prev.next = inserted;
}
public void removeLast() {//尾删
Node removed = sentinel.prev;
if (removed == sentinel) {
throw illegalIndex(0);
}
Node next = sentinel;
Node prev = sentinel.prev;
prev.next = next;
next.prev = prev;
}
public void insert(int index,int value) {//插入节点
if (index == 0) {
addFirst(value);
}else {
Node prev = findNode(index - 1);
if (prev == null) {
throw illegalIndex(index);
}
Node next = prev.next;
Node inserted = new Node(prev,value,next);
prev.next = inserted;
next.prev = inserted;
}
}
private Node findNode(int index){//寻找节点
int i = 0;
Node p = sentinel.next;
while (p != sentinel) {
if (i == index) {
return p;
}
i++;
p = p.next;
}
return null;
}
public void removeByValue(int value) {//根据值来删除
Node removed = findByValue(value);
if (removed == null) {
return;
}
Node prev = removed.prev;
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
private Node findByValue(int value) {//返回相应值的节点
Node p = sentinel.next;
while (p != sentinel) {
if (p.value == value) {
return p;
}
p = p.next;
}
return null;
}
@Override
public Iterator<Integer> iterator() {//迭代器
return new Iterator<Integer>() {
Node p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
public void showList() {//遍历链表
if (sentinel.next == sentinel) {
System.out.println("链表为空");
return;
}
System.out.print("链表遍历： ");
forEach(integer -> {
System.out.print(integer + " ");
});
System.out.println("");
}
private IllegalArgumentException illegalIndex(int index) {//异常信息
return new IllegalArgumentException(
String.format("索引：Index[%d]，不合法 %n", index));
}
}