Dequeue Using Linked List in DSA Java - Build from Scratch

Dequeue Using Linked List

📖 Scenario: Imagine you are managing a line of customers at a bank where people can join or leave from both ends of the line. This line is called a dequeue (double-ended queue). You will build this using a linked list in Java.

🎯 Goal: Create a dequeue using a linked list that supports adding and removing elements from both the front and the rear.

📋 What You'll Learn

Create a Node class with an integer data and a next pointer

Create a Dequeue class with front and rear pointers

Implement methods to add elements at front and rear

Implement methods to remove elements from front and rear

Print the dequeue elements from front to rear

💡 Why This Matters

🌍 Real World

Dequeue structures are used in real-world scenarios like task scheduling, undo operations in software, and managing buffers where elements can be added or removed from both ends.

💼 Career

Understanding dequeue implementation helps in software development roles that require efficient data handling, such as backend development, systems programming, and algorithm design.

1

Create Node and Dequeue classes with front and rear pointers

Create a class called Node with an integer variable data and a Node variable next. Then create a class called Dequeue with two Node variables called front and rear, both initialized to null.

DSA Java

// Your code here

Hint

Start by defining the Node class with data and next. Then define the Dequeue class with front and rear pointers set to null.

2

Add method to insert element at the rear

In the Dequeue class, add a method called addRear that takes an integer value. This method should create a new Node with value and add it at the rear of the dequeue. If the dequeue is empty, set both front and rear to the new node. Otherwise, link the current rear to the new node and update rear.

DSA Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Dequeue {
    Node front = null;
    Node rear = null;

    // Add addRear method here
    // Your code here
}

Hint

Check if rear is null. If yes, set both front and rear to the new node. Otherwise, link the current rear to the new node and update rear.

3

Add method to remove element from the front

In the Dequeue class, add a method called removeFront that returns an integer. This method should remove the node at the front of the dequeue and return its data. If the dequeue is empty, return -1. Update front to the next node. If after removal front becomes null, set rear to null as well.

DSA Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Dequeue {
    Node front = null;
    Node rear = null;

    void addRear(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    // Add removeFront method here
    // Your code here
}

Hint

Check if front is null. If yes, return -1. Otherwise, save front.data, move front to front.next, and if front is now null, set rear to null. Return the saved data.

4

Print all elements from front to rear

Add a method called printDequeue in the Dequeue class that prints all elements from front to rear separated by -> and ending with null. Then create a main method to add these elements at rear: 10, 20, 30, remove one element from front, and print the dequeue.

DSA Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class Dequeue {
    Node front = null;
    Node rear = null;

    void addRear(int value) {
        Node newNode = new Node(value);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    int removeFront() {
        if (front == null) {
            return -1;
        }
        int value = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return value;
    }

    // Add printDequeue method and main method here
    // Your code here
}

Hint

Traverse from front to rear, printing each data followed by -> . After the last node, print null. In main, add 10, 20, 30 at rear, remove one from front, then print.

Practice

1. What is the main advantage of using a linked list to implement a Dequeue compared to using an array?

easy

A. It uses less memory than arrays in all cases.

B. It allows dynamic memory allocation and easy insertion/deletion at both ends.

C. It provides faster access to elements by index.

D. It automatically sorts elements when inserted.

Solution

1. Step 1: Understand linked list properties

   A linked list can grow or shrink dynamically without fixed size limits.

2. Step 2: Compare with array limitations

   Arrays have fixed size and inserting/deleting at ends may require shifting elements, which is costly.

3. Final Answer:

   It allows dynamic memory allocation and easy insertion/deletion at both ends. -> Option B

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked list grows dynamically, arrays have fixed size [OK]

Common Mistakes:

• Thinking arrays always use less memory
• Confusing access speed with insertion speed
• Assuming linked list sorts elements automatically

2. Which of the following is the correct way to declare a node class for a doubly linked list used in a dequeue in Java?

easy

A. class Node { int data; Node next; }

B. class Node { int data; Node prev; }

C. class Node { int data; Node left; Node right; }

D. class Node { int data; Node next; Node prev; }

Solution

1. Step 1: Identify node requirements for dequeue

   A dequeue needs to insert/delete at both ends, so nodes must link forward and backward.

2. Step 2: Check node class fields

   Only class Node { int data; Node next; Node prev; } has both next and prev pointers for doubly linked list.

3. Final Answer:

   class Node { int data; Node next; Node prev; } -> Option D

4. Quick Check:

   Doubly linked list node = next + prev [OK]

Hint: Doubly linked list nodes have next and prev pointers [OK]

Common Mistakes:

• Using single pointer nodes for dequeue
• Confusing binary tree node pointers with linked list
• Omitting prev pointer needed for backward traversal

3. What will be the output after performing these operations on an empty dequeue implemented using a linked list?

dequeue.insertFront(10);
dequeue.insertRear(20);
dequeue.insertFront(5);
dequeue.deleteRear();
dequeue.display();

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 5 -> 20 -> null

D. 10 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   List becomes: 10 -> 20 -> null

2. Step 2: Perform insertFront(5)

   List becomes: 5 -> 10 -> 20 -> null

3. Step 3: Perform deleteRear()

   Removes 20, list becomes: 5 -> 10 -> null

4. Step 4: Display list

   Output is 5 -> 10 -> null

5. Final Answer:

   5 -> 10 -> null -> Option A

6. Quick Check:

   Front insertions add left, rear deletion removes right [OK]

Hint: Track insertFront and insertRear positions carefully [OK]

Common Mistakes:

• Deleting front instead of rear
• Mixing order of insertions
• Forgetting to update pointers after deletion

4. Consider this buggy method to delete from the front of a dequeue implemented using a linked list:

public void deleteFront() {
  if (front == null) {
    System.out.println("Dequeue is empty");
    return;
  }
  front = front.next;
  front.prev = null;
}

What error can occur when this method is called on a dequeue with only one element?

medium

A. NullPointerException when setting front.prev = null

B. ArrayIndexOutOfBoundsException

C. No error, method works fine

D. Infinite loop in linked list

Solution

1. Step 1: Analyze deleteFront on single element list

   If only one node, after front = front.next, front becomes null.

2. Step 2: Check next line front.prev = null

   Since front is null, accessing front.prev causes NullPointerException.

3. Final Answer:

   NullPointerException when setting front.prev = null -> Option A

4. Quick Check:

   Accessing null pointer causes NullPointerException [OK]

Hint: Check for null before accessing front.prev [OK]

Common Mistakes:

• Assuming front is never null after deletion
• Ignoring edge case of single element
• Confusing exception types

5. You want to implement a dequeue using a linked list that supports these operations efficiently:
1. Insert at front
2. Insert at rear
3. Delete from front
4. Delete from rear
5. Get size of dequeue

Which data members should your dequeue class maintain to achieve all operations in O(1) time?

hard

A. Pointer to rear node only, no size counter

B. Pointer to front node only, and an integer size counter

C. Pointers to front and rear nodes, and an integer size counter

D. Array to store elements and a size counter

Solution

1. Step 1: Identify pointers needed for O(1) insert/delete at both ends

   We need both front and rear pointers to access both ends directly.

2. Step 2: Identify how to get size in O(1)

   Maintain an integer size counter updated on each insert/delete.

3. Final Answer:

   Pointers to front and rear nodes, and an integer size counter -> Option C

4. Quick Check:

   Front + rear pointers + size counter = O(1) ops [OK]

Hint: Keep front, rear pointers and size counter for O(1) operations [OK]

Common Mistakes:

• Using only one pointer for both ends
• Not maintaining size counter for quick size retrieval
• Using array instead of linked list for dequeue