Deque (двунаправленная очередь) — структура данных, позволяющая добавлять и удалять элементы с обоих концов.

Реализация через LinkedList (двусвязный список) выглядит так:

Каждый элемент (узел) содержит ссылку на следующий и предыдущий узлы.
Deque хранит указатели на голову (первый элемент) и хвост (последний элемент) списка.

Взаимодействие:

Добавление в начало: создаётся новый узел, его next указывает на текущую голову, у текущей головы prev обновляется на новый узел, затем голова обновляется.
Добавление в конец: аналогично, но с хвостом.
Удаление с начала или конца — просто обновление указателей головы или хвоста и освобождение узла.

Так как LinkedList обеспечивает быстрый доступ к началу и концу, операции вставки и удаления в Deque выполняются за O(1).

Пример на Java:

class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

class Deque<E> {
    private Node<E> head;
    private Node<E> tail;

    void addFirst(E e) {
        Node<E> newNode = new Node<>();
        newNode.item = e;
        newNode.next = head;
        if (head != null) head.prev = newNode;
        head = newNode;
        if (tail == null) tail = newNode;
    }

    void addLast(E e) {
        Node<E> newNode = new Node<>();
        newNode.item = e;
        newNode.prev = tail;
        if (tail != null) tail.next = newNode;
        tail = newNode;
        if (head == null) head = newNode;
    }

    // Аналогично реализуются removeFirst и removeLast
}

Таким образом, LinkedList обеспечивает эффективную реализацию Deque с двунаправленным доступом.

Как структура данных Deque реализована с помощью LinkedList и как они взаимодействуют?