How is the Deque data structure implemented using LinkedList and how do they interact?

Deque (double-ended queue) is a data structure that allows adding and removing elements from both ends.

Implementation using LinkedList (doubly linked list) looks like this:

• Each element (node) contains a reference to the next and previous nodes.
• Deque stores pointers to the head (first element) and tail (last element) of the list.

Interaction:

• Adding to the beginning: a new node is created, its next points to the current head, the current head's prev is updated to the new node, then the head is updated.
• Adding to the end: similar, but with the tail.
• Removing from the beginning or end — simply updating the head or tail pointers and freeing the node.

Since LinkedList provides quick access to the beginning and end, insertion and deletion operations in Deque are performed in O(1).

Example in 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 and removeLast are implemented similarly
}

Thus, LinkedList provides an efficient implementation of Deque with double-ended access.