Deque

什么是Deque

Deque（Double Ended Queue）就是 双端队列，特点是：

• 可以在两端插入元素（头插、尾插）。
• 可以在两端删除元素（头删、尾删）。
  用 双向链表（Doubly Linked List） 来实现 Deque，原因是：
• 双向链表支持在任意位置快速插入和删除，不需要整体移动元素。
• 相比数组，链表在 Deque 场景下更高效（如果只关心两端操作）。

此外还可基于Array进行实现

实现核心：Node节点和哨兵节点

1.Node节点

public class Node {
    T item;
    Node next;
    Node prev;
}

• item：保存实际元素。

• next：指向下一个节点。

• prev：指向上一个节点。

2.Sentinel哨兵节点

• 哨兵（sentinel）本身不存数据（item=null）。

• 它的 next 指向第一个元素，prev 指向最后一个元素。

• 当链表是空时：sentinel.next == sentinel 且 sentinel.prev == sentinel。

• 这样可以避免对头插、尾插写特殊判断，因为哨兵把链表首尾“连起来”了。

插入到头节点

1.场景

假设：

sentinel 是哨兵，不存实际数据。

• 当前链表：
• sentinel <-> A <-> B <-> C <-> sentinel

此时 sentinel.next 是 A，sentinel.prev 是 C。

2.现在要把 X 插到最前面，也就是放到 A 前面。

所以插入后应该是：
sentinel <-> X <-> A <-> B <-> C <-> sentinel

3.执行的逻辑

✅ newNode.prev = sentinel;

意思是：

• 新节点 X 的 prev 指针要指向 sentinel。
• 因为 X 是新的第一个元素，它前面就是 sentinel。

✅ newNode.next = sentinel.next;

意思是：

• 新节点 X 的 next 指针要指向原来的第一个节点（就是 A）。
• 因为 X 插在最前面，它后面就是原来的第一个节点。

✅ sentinel.next.prev = newNode;

意思是：

• 原来的第一个节点 A 的 prev 指针，要改成指向 X。
• 因为 A 的前驱变成了 X（之前是 sentinel）。

✅ sentinel.next = newNode;

意思是：

• sentinel 的 next 指针要指向 X。
• 因为现在 X 是新的第一个节点。

@Override
public void addFirst(T x) {
    Node newNode = new Node(x, null, null);
    newNode.prev =  sentinel;
    newNode.next = sentinel.next;
    sentinel.next.prev = newNode;
    sentinel.next = newNode;
}

— 2025年7月17日