1. Introduction

A Deque (short for “double-ended queue”) is a type of queue allowing insertion and removal of elements from both ends. Thus, it supports operations like addFirst, addLast, removeFirst, and removeLast. Implementing a deque using a linked list is advantageous due to its ability to grow and shrink dynamically. In this post, we will detail how to implement a deque using a linked list in Java.

2. Program Steps

1. Define a Node class that will represent each element in the linked list.

2. Create a Deque class that will use the Node class to store elements.

3. Implement the main deque operations:

– addFirst: Add an element to the front of the deque.

– addLast: Add an element to the end of the deque.

– removeFirst: Remove and return the front element from the deque.

– removeLast: Remove and return the last element from the deque.

– peekFirst: View the front element without removing it.

– peekLast: View the last element without removing it.

– isEmpty: Check if the deque is empty.

4. Demonstrate the deque operations in the main function.

3. Code Program

class Deque<T> {

    private Node<T> front;
    private Node<T> rear;

    private static class Node<T> {
        private T data;
        private Node<T> next;
        private Node<T> prev;

        Node(T data) {
            this.data = data;
        }
    }

    public void addFirst(T data) {
        Node<T> newNode = new Node<>(data);
        if (front != null) {
            front.prev = newNode;
            newNode.next = front;
        }
        front = newNode;
        if (rear == null) {
            rear = front;
        }
    }

    public void addLast(T data) {
        Node<T> newNode = new Node<>(data);
        if (rear != null) {
            rear.next = newNode;
            newNode.prev = rear;
        }
        rear = newNode;
        if (front == null) {
            front = rear;
        }
    }

    public T removeFirst() {
        if (front == null) {
            System.out.println("Deque is empty. Cannot remove from front.");
            return null;
        }
        T item = front.data;
        front = front.next;
        if (front != null) {
            front.prev = null;
        } else {
            rear = null;
        }
        return item;
    }

    public T removeLast() {
        if (rear == null) {
            System.out.println("Deque is empty. Cannot remove from rear.");
            return null;
        }
        T item = rear.data;
        rear = rear.prev;
        if (rear != null) {
            rear.next = null;
        } else {
            front = null;
        }
        return item;
    }

    public T peekFirst() {
        if (front == null) {
            System.out.println("Deque is empty. Nothing to peek at front.");
            return null;
        }
        return front.data;
    }

    public T peekLast() {
        if (rear == null) {
            System.out.println("Deque is empty. Nothing to peek at rear.");
            return null;
        }
        return rear.data;
    }

    public boolean isEmpty() {
        return front == null && rear == null;
    }

    public static void main(String[] args) {
        Deque<Integer> deque = new Deque<>();
        deque.addFirst(10);
        deque.addLast(20);
        System.out.println("Front element: " + deque.peekFirst());
        System.out.println("Rear element: " + deque.peekLast());
        System.out.println("Removed front element: " + deque.removeFirst());
        System.out.println("Removed rear element: " + deque.removeLast());
        System.out.println("Is deque empty? " + deque.isEmpty());
    }
}

Output:

Front element: 10
Rear element: 20
Removed front element: 10
Removed rear element: 20
Is deque empty? true

4. Step By Step Explanation

1. We start by defining a Node class with data, next, and prev properties. This structure allows for forward and backward traversal.

2. The Deque class has references to the front and rear nodes.

3. In the addFirst method, we insert a new node at the beginning. The prev property of the original front node is updated to point to the new node.

4. Similarly, the addLast method adds a node at the end. The next property of the original rear node is updated to point to the new node.

5. The removeFirst and removeLast methods delete nodes from the front and rear, respectively, and return their data.

6. peekFirst and peekLast allow us to view the data at the front and rear without deletion.

7. The isEmpty method checks if both front and rear are null.

8. The main function demonstrates the functionality