双向链表（有哨兵节点）
双向链表介绍
双向链表（Doubly Linked List）是一种链式存储结构，每个节点不仅包含数据，还包含两个指针，分别指向前驱节点和后继节点。它相比单向链表有更高的灵活性，因为可以从任意节点向前或向后遍历。
双向链表的特点
1，双向指针：每个节点包含两个指针，分别指向前驱节点和后继节点。
2，灵活遍历：既可以从头节点开始遍历，也可以从尾节点开始遍历。
3，插入和删除：在已知节点位置的情况下，插入和删除操作更高效，因为不需要像数组那样移动大量元素。
4，额外空间：因为需要两个指针，所以相比单向链表占用更多的内存。
应用场景
1，浏览器的前进和后退功能。
2，实现缓存（如 LRU 缓存）。
3，适用于需要双向遍历的场景。
代码解析
1，节点类：
包含 value、prev 和 next 属性。
prev 指向前驱节点，next 指向后继节点。
2，双向链表类：
使用 head 和 tail 分别指向链表的头节点和尾节点。
提供添加、删除和遍历功能。
3，核心方法：
addLast(int data)：在链表尾部添加新节点。
removeFirst()：从链表头部删除节点。
printForward() 和 printBackward()：分别实现正向（从head.next开始）和反向遍历（从tail.prev开始）。
Java代码
import java.util.Iterator;
//双向链表（带哨兵）
public class DoublyLinkedListSentinel implements Iterable<Integer> {
static class Node {
Node prev;
int value;
Node next;
public Node(Node prev, int value, Node next) {
this.next = next;
this.prev = prev;
this.value = value;
}
}
private Node head;
private Node tail;
public DoublyLinkedListSentinel() {
head = new Node(null, -1, null);
tail = new Node(null, -1, null);
head.next = tail;//初始化
tail.prev = head;//初始化
}
private Node findNode(int index) {//根据索引位置找到节点
int i = -1;
for (Node p = head; p != tail; p = p.next, i++) {//p指向尾节点结束循环
if (i == index) {
return p;
}
}
return null;
}
public void addFirst(int value) {//添加头节点
insert(0,value);
}
public void removeFirst() {//删除头节点
remove(0);
}
public void addLast(int value) {//添加尾节点
//双向链表特色
Node next = tail;
Node prev = tail.prev;
Node inserted = new Node(prev,value,next);
prev.next = inserted;
next.prev = inserted;
}
public void removeLast() {//删除尾节点
//双向链表特色
Node removed = tail.prev;
if (removed == head) {
throw illegalIndex(0);
}
Node prev = removed.prev;
prev.next = tail;
tail.prev = prev;
}
public void insert(int index,int value) {//添加节点
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;
}
public void remove(int index) {
Node prev = findNode(index - 1);
if (prev == null) {//如果前一个节点找不到抛出异常
throw illegalIndex(index);//包含了待删节点是头哨兵的情况
}
Node removed = prev.next;//待删除节点
if (removed == tail) {//如果待删除节点是尾哨兵抛出异常
throw illegalIndex(index);
}
Node next = removed.next;
prev.next = next;
next.prev = prev;
}
private IllegalArgumentException illegalIndex(int index) {//异常信息
return new IllegalArgumentException(
String.format("索引：Index[%d]，不合法 %n", index));
}
public Iterator<Integer> iterator() {//迭代器
return new Iterator<Integer>() {
Node p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
public void showList() {//正向遍历链表
System.out.print("遍历链表： ");
forEach( i -> {
System.out.print(i + " ");
});
}
}