Enqueue Using Linked List in DSA Java

Mental Model

Enqueue means adding an item to the end of a line. Using a linked list, we keep track of the last item to add new items quickly.

Analogy: Imagine a line of people holding hands. To add a new person, you only need to hold the last person's hand and add the new person there.

front -> 1 -> 2 -> 3 -> null ← rear
                   ↑rear points here

Dry Run Walkthrough

Input: Start with queue: 1 -> 2 -> 3 -> null, enqueue value 4

Goal: Add value 4 to the end of the queue using linked list pointers

Step 1: Create new node with value 4

front -> 1 -> 2 -> 3 -> null ← rear    newNode(4) isolated

Why: We need a new node to add to the queue

Step 2: Link rear node's next to new node

front -> 1 -> 2 -> 3 -> [rear->4] -> null

Why: Attach new node at the end of the queue

Step 3: Move rear pointer to new node

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Why: Rear must always point to the last node

Result:

front -> 1 -> 2 -> 3 -> 4 -> null ← rear

Annotated Code

DSA Java

public class LinkedListQueue {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    Node front, rear;

    public LinkedListQueue() {
        front = rear = null;
    }

    // Add value to the end of the queue
    public void enqueue(int value) {
        Node newNode = new Node(value); // create new node
        if (rear == null) { // if queue empty
            front = rear = newNode; // front and rear point to new node
            return;
        }
        rear.next = newNode; // link last node to new node
        rear = newNode; // move rear to new node
    }

    // Print queue from front to rear
    public void printQueue() {
        Node temp = front;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedListQueue queue = new LinkedListQueue();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.printQueue();
        queue.enqueue(4);
        queue.printQueue();
    }
}

Node newNode = new Node(value); // create new node

create a new node to add at the end

if (rear == null) { front = rear = newNode; return; }

handle empty queue by setting front and rear to new node

rear.next = newNode; // link last node to new node

attach new node after current rear

rear = newNode; // move rear to new node

update rear pointer to new last node

Output

1 -> 2 -> 3 -> null

1 -> 2 -> 3 -> 4 -> null

Complexity Analysis

Time: O(1) because we add the new node directly at the rear without traversing

Space: O(1) because we only create one new node for each enqueue

vs Alternative: Compared to using an array where adding at end may require shifting or resizing (O(n)), linked list enqueue is faster and simpler

Edge Cases

Empty queue

front and rear both point to the new node

DSA Java

if (rear == null) { front = rear = newNode; return; }

Single element queue

rear.next links new node, rear moves to new node

DSA Java

rear.next = newNode; rear = newNode;

When to Use This Pattern

When you need to add items to the end of a queue efficiently, use the enqueue linked list pattern to keep track of the rear pointer for O(1) insertion.

Common Mistakes

Mistake: Not updating the rear pointer after adding the new node
Fix: Always move rear to the new node after linking it

Mistake: Not handling empty queue case where front and rear are null
Fix: Check if rear is null and set both front and rear to new node

Summary

Adds a new element at the end of a queue using a linked list.

Use when you want fast enqueue operations without shifting elements.

Keep track of the rear pointer to add new nodes quickly at the end.

Practice

1. What does the enqueue operation do in a linked list implementation of a queue?

easy

A. Adds an element at the end (rear) of the linked list

B. Removes an element from the front of the linked list

C. Deletes the entire linked list

D. Adds an element at the front (head) of the linked list

Solution

1. Step 1: Understand enqueue operation in queue

   Enqueue means adding an element to the queue, which is done at the rear end.

2. Step 2: Linked list enqueue adds at the rear

   In linked list, adding at the rear means inserting the new node at the end of the list.

3. Final Answer:

   Adds an element at the end (rear) of the linked list -> Option A

4. Quick Check:

   Enqueue = add at rear [OK]

Hint: Enqueue always adds at the rear of the queue [OK]

Common Mistakes:

• Confusing enqueue with dequeue operation
• Thinking enqueue adds at the front
• Mixing linked list head and tail roles

2. Which of the following is the correct way to create a new node for enqueue in Java linked list?

easy

A. Node newNode = new Node(); newNode.data = value; newNode.next = null;

B. Node newNode = Node(value); newNode.next = null;

C. Node newNode = new Node(value); newNode.next = null;

D. Node newNode = new Node; newNode.data = value;

Solution

1. Step 1: Understand Java object creation syntax

   In Java, to create an object with a constructor that takes a value, use new Node(value).

2. Step 2: Check next pointer initialization

   After creating the node, set next to null to mark end of list.

3. Final Answer:

   Node newNode = new Node(value); newNode.next = null; -> Option C

4. Quick Check:

   Java new object with constructor = new Node(value) [OK]

Hint: Use 'new' keyword with constructor for object creation [OK]

Common Mistakes:

• Missing 'new' keyword when creating object
• Incorrect constructor call syntax
• Not setting next pointer to null

3. What will be the state of the queue after the following enqueue operations on an empty linked list queue?

enqueue(10); enqueue(20); enqueue(30);

medium

A. 10 -> 20 -> 30 -> null

B. 30 -> 20 -> 10 -> null

C. null -> 10 -> 20 -> 30

D. 20 -> 10 -> 30 -> null

Solution

1. Step 1: Enqueue 10 on empty queue

   Queue becomes: 10 -> null

2. Step 2: Enqueue 20 and 30 sequentially

   After enqueue(20): 10 -> 20 -> null
   After enqueue(30): 10 -> 20 -> 30 -> null

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   Enqueue adds at rear, order preserved [OK]

Hint: Enqueue adds at rear, so order is insertion order [OK]

Common Mistakes:

• Reversing order of elements after enqueue
• Confusing enqueue with push (stack)
• Assuming new elements added at front

4. Identify the error in the following enqueue method for a linked list queue:

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

medium

A. Should set front.next to newNode instead of rear.next

B. Missing update of rear pointer to newNode

C. New node should be created with next pointing to front

D. Should check if front is null instead of rear

Solution

1. Step 1: Analyze enqueue logic

   When queue is empty, front is set to newNode but rear is not updated.

2. Step 2: Check rear pointer update

   After adding newNode, rear should point to newNode to keep track of last element.

3. Final Answer:

   Missing update of rear pointer to newNode -> Option B

4. Quick Check:

   Rear must always point to last node [OK]

Hint: Always update rear to new node after enqueue [OK]

Common Mistakes:

• Forgetting to update rear pointer
• Updating front.next instead of rear.next
• Not handling empty queue case properly

5. Given a linked list queue with elements 5 -> 15 -> 25 -> null, what will be the queue state after enqueueing 35 and then dequeueing one element?

hard

A. 35 -> 15 -> 25 -> null

B. 5 -> 15 -> 25 -> 35 -> null

C. 25 -> 35 -> null

D. 15 -> 25 -> 35 -> null

Solution

1. Step 1: Enqueue 35 at rear

   Queue becomes: 5 -> 15 -> 25 -> 35 -> null

2. Step 2: Dequeue removes front element 5

   After dequeue: 15 -> 25 -> 35 -> null

3. Final Answer:

   15 -> 25 -> 35 -> null -> Option D

4. Quick Check:

   Enqueue adds rear, dequeue removes front [OK]

Hint: Enqueue rear, dequeue front; order shifts accordingly [OK]

Common Mistakes:

• Removing wrong element on dequeue
• Adding new element at front instead of rear
• Not updating front pointer after dequeue