Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Deque Implementation

Problem Statement

Write a Java program that implements a double-ended queue (deque) using a doubly linked list. The doubly linked list consists of nodes, each containing an integer value, a reference to the next node, and a reference to the previous node. The deque should support methods to add elements at the front (head) and back (tail), and remove elements from the front and back, maintaining the list’s bidirectional structure. Test the implementation with a sequence of operations, including adding and removing elements at both ends, and handling edge cases like empty deques and single-element deques. You can visualize this as managing a queue of numbered cards where you can add or remove cards from either the front or the back of the deck.

Input:

  • A sequence of operations, where each operation is:
    • addFront(value): Add a value to the front of the deque.
    • addBack(value): Add a value to the back of the deque.
    • removeFront(): Remove and return the front value, or -1 if empty.
    • removeBack(): Remove and return the back value, or -1 if empty.
    • printDeque(): Print the deque in forward order. Output: For each operation, print the action performed (e.g., "Added 5 at front", "Removed 3 from back", or the deque as a string). Return -1 for remove operations on an empty deque. Constraints:
  • The deque size is between 0 and 10^5.
  • Values are integers in the range [-10^9, 10^9].
  • The deque may be empty. Example:
  • Input: Operations = [addFront(1), addBack(2), addFront(3), printDeque, removeFront, printDeque, removeBack, printDeque]
  • Output: 
    Added 1 at front
Added 2 at back
Added 3 at front
Deque: 3 1 2
Removed 3 from front
Deque: 1 2
Removed 2 from back
Deque: 1
  • Input: Operations = [removeFront, printDeque]
  • Output: 
    Removed -1 from front
Deque: []

Pseudocode

CLASS DoublyNode
    SET value to integer
    SET next to DoublyNode (null by default)
    SET prev to DoublyNode (null by default)
ENDCLASS

CLASS Deque
    SET head to null
    SET tail to null

    FUNCTION addFront(value)
        CREATE newNode as new DoublyNode(value)
        IF head is null THEN
            SET head to newNode
            SET tail to newNode
        ELSE
            SET newNode.next to head
            SET head.prev to newNode
            SET head to newNode
        ENDIF
    ENDFUNCTION

    FUNCTION addBack(value)
        CREATE newNode as new DoublyNode(value)
        IF tail is null THEN
            SET head to newNode
            SET tail to newNode
        ELSE
            SET newNode.prev to tail
            SET tail.next to newNode
            SET tail to newNode
        ENDIF
    ENDFUNCTION

    FUNCTION removeFront()
        IF head is null THEN
            RETURN -1
        ENDIF
        SET value to head.value
        SET head to head.next
        IF head is null THEN
            SET tail to null
        ELSE
            SET head.prev to null
        ENDIF
        RETURN value
    ENDFUNCTION

    FUNCTION removeBack()
        IF tail is null THEN
            RETURN -1
        ENDIF
        SET value to tail.value
        SET tail to tail.prev
        IF tail is null THEN
            SET head to null
        ELSE
            SET tail.next to null
        ENDIF
        RETURN value
    ENDFUNCTION

    FUNCTION toString()
        IF head is null THEN
            RETURN "[]"
        ENDIF
        CREATE result as new StringBuilder
        SET current to head
        WHILE current is not null
            APPEND current.value to result
            IF current.next is not null THEN
                APPEND " " to result
            ENDIF
            SET current to current.next
        ENDWHILE
        RETURN result as string
    ENDFUNCTION
ENDCLASS

FUNCTION testDeque(operations)
    CREATE deque as new Deque
    FOR each operation in operations
        IF operation.type equals "addFront" THEN
            CALL deque.addFront(operation.value)
            PRINT added value at front
        ELSE IF operation.type equals "addBack" THEN
            CALL deque.addBack(operation.value)
            PRINT added value at back
        ELSE IF operation.type equals "removeFront" THEN
            SET value to deque.removeFront()
            PRINT removed value from front
        ELSE IF operation.type equals "removeBack" THEN
            SET value to deque.removeBack()
            PRINT removed value from back
        ELSE IF operation.type equals "print" THEN
            PRINT deque using toString
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testDeque(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a DoublyNode class with: a. An integer value. b. A next pointer to the next node. c. A prev pointer to the previous node.
  2. Define a Deque class with: a. head and tail pointers to track both ends. b. addFront: Add node at head, update prev and tail if needed. c. addBack: Add node at tail, update next and head if needed. d. removeFront: Remove head, update head and tail, return value or -1. e. removeBack: Remove tail, update tail and head, return value or -1. f. toString: Print list forward, return "[]" if empty.
  3. In testDeque: a. Create a Deque. b. For each operation:
    • addFront: Call addFront, print action.
    • addBack: Call addBack, print action.
    • removeFront: Call removeFront, print value.
    • removeBack: Call removeBack, print value.
    • print: Call toString, print deque.
  4. In main, test with sequences including adds/removes at both ends and edge cases.

Java Implementation

import java.util.*;

public class DequeImplementation {
    // Node class for the doubly linked list
    static class DoublyNode {
        int value;
        DoublyNode next;
        DoublyNode prev;

        DoublyNode(int value) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }

    // Deque class using doubly linked list
    static class Deque {
        private DoublyNode head;
        private DoublyNode tail;

        public void addFront(int value) {
            DoublyNode newNode = new DoublyNode(value);
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.next = head;
                head.prev = newNode;
                head = newNode;
            }
        }

        public void addBack(int value) {
            DoublyNode newNode = new DoublyNode(value);
            if (tail == null) {
                head = newNode;
                tail = newNode;
            } else {
                newNode.prev = tail;
                tail.next = newNode;
                tail = newNode;
            }
        }

        public int removeFront() {
            if (head == null) {
                return -1;
            }
            int value = head.value;
            head = head.next;
            if (head == null) {
                tail = null;
            } else {
                head.prev = null;
            }
            return value;
        }

        public int removeBack() {
            if (tail == null) {
                return -1;
            }
            int value = tail.value;
            tail = tail.prev;
            if (tail == null) {
                head = null;
            } else {
                tail.next = null;
            }
            return value;
        }

        public String toString() {
            if (head == null) {
                return "[]";
            }
            StringBuilder result = new StringBuilder();
            DoublyNode current = head;
            while (current != null) {
                result.append(current.value);
                if (current.next != null) {
                    result.append(" ");
                }
                current = current.next;
            }
            return result.toString();
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        Integer value;

        Operation(String type, Integer value) {
            this.type = type;
            this.value = value;
        }
    }

    // Tests deque operations
    public void testDeque(List<Operation> operations) {
        Deque deque = new Deque();
        for (Operation op : operations) {
            if (op.type.equals("addFront")) {
                deque.addFront(op.value);
                System.out.println("Added " + op.value + " at front");
            } else if (op.type.equals("addBack")) {
                deque.addBack(op.value);
                System.out.println("Added " + op.value + " at back");
            } else if (op.type.equals("removeFront")) {
                int value = deque.removeFront();
                System.out.println("Removed " + value + " from front");
            } else if (op.type.equals("removeBack")) {
                int value = deque.removeBack();
                System.out.println("Removed " + value + " from back");
            } else if (op.type.equals("print")) {
                System.out.println("Deque: " + deque.toString());
            }
        }
    }

    // Main method to test deque implementation
    public static void main(String[] args) {
        DequeImplementation manager = new DequeImplementation();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal operations
        testCases.add(Arrays.asList(
            new Operation("addFront", 1),
            new Operation("addBack", 2),
            new Operation("addFront", 3),
            new Operation("print", null),
            new Operation("removeFront", null),
            new Operation("print", null),
            new Operation("removeBack", null),
            new Operation("print", null)
        ));
        
        // Test case 2: Empty deque
        testCases.add(Arrays.asList(
            new Operation("removeFront", null),
            new Operation("removeBack", null),
            new Operation("print", null)
        ));
        
        // Test case 3: Single element
        testCases.add(Arrays.asList(
            new Operation("addFront", 5),
            new Operation("print", null),
            new Operation("removeFront", null),
            new Operation("print", null)
        ));
        
        // Test case 4: Mixed operations with duplicates
        testCases.add(Arrays.asList(
            new Operation("addFront", 1),
            new Operation("addBack", 1),
            new Operation("addFront", 2),
            new Operation("print", null),
            new Operation("removeFront", null),
            new Operation("removeBack", null),
            new Operation("print", null)
        ));

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            manager.testDeque(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Added 1 at front
Added 2 at back
Added 3 at front
Deque: 3 1 2
Removed 3 from front
Deque: 1 2
Removed 2 from back
Deque: 1

Test case 2:
Removed -1 from front
Removed -1 from back
Deque: []

Test case 3:
Added 5 at front
Deque: 5
Removed 5 from front
Deque: []

Test case 4:
Added 1 at front
Added 1 at back
Added 2 at front
Deque: 2 1 1
Removed 2 from front
Removed 1 from back
Deque: 1

Explanation:

  • Test case 1: Adds 1 (front), 2 (back), 3 (front), prints "3 1 2", removes 3 (front), prints "1 2", removes 2 (back), prints "1".
  • Test case 2: Removes from empty deque (returns -1), prints "[]".
  • Test case 3: Adds 5 (front), prints "5", removes 5 (front), prints "[]".
  • Test case 4: Adds 1 (front), 1 (back), 2 (front), prints "2 1 1", removes 2 (front), 1 (back), prints "1".

How It Works

  • DoublyNode: Stores an integer value, a next pointer, and a prev pointer.
  • Deque:
    • addFront: Adds node at head, updates prev and tail, O(1).
    • addBack: Adds node at tail, updates next and head, O(1).
    • removeFront: Removes head, updates head and tail, returns value or -1, O(1).
    • removeBack: Removes tail, updates tail and head, returns value or -1, O(1).
    • toString: Traverses forward, returns space-separated string or "[]".
  • testDeque: Executes operations, printing actions and results.
  • Example Trace (Test case 1):
    • addFront(1): head=1↔null, tail=1.
    • addBack(2): head=1↔2, tail=2.
    • addFront(3): head=3↔1↔2, tail=2.
    • print: "3 1 2".
    • removeFront: Removes 3, head=1↔2, tail=2, returns 3.
    • print: "1 2".
    • removeBack: Removes 2, head=1, tail=1, returns 2.
    • print: "1".
  • Main Method: Tests normal operations, empty deque, single element, and duplicates.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Add FrontO(1)O(1)
Add BackO(1)O(1)
Remove FrontO(1)O(1)
Remove BackO(1)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the deque.
  • Time complexity: O(1) for addFront, addBack, removeFront, removeBack (constant-time operations); O(n) for toString (traverse list).
  • Space complexity: O(1) for add/remove operations (constant pointers); O(n) for toString (StringBuilder).
  • Worst case: O(n) time, O(n) space for output with large deques.

✅ Tip: Use a doubly linked list for a deque to enable O(1) operations at both ends by maintaining head and tail pointers. Test edge cases like empty deques and single-element deques to ensure robustness.

⚠ Warning: Always update both head and tail pointers correctly during add and remove operations to maintain deque integrity. Check for null pointers to handle empty deque cases.