PPractick

The problem

A print server receives an unpredictable number of jobs, so its FIFO queue must grow without limit. A singly linked list with two pointers does it in O(1) per operation: front is where jobs leave, and rear is where new jobs are attached. The classic bug is forgetting that removing the last node must also reset rear to null. Otherwise the next enqueue writes through a dangling pointer.

Example: enqueue(2), enqueue(3), dequeue() → 2, enqueue(4), dequeue() → 3.

Function signature

class LinkedQueue {
public:
    void enqueue(int x);
    int dequeue();         // -1 if empty
    int front() const;     // -1 if empty
    bool isEmpty() const;
    int size() const;
};

Test cases

Operations	Output	Explanation
enqueue(2) enqueue(3) dequeue() enqueue(4) dequeue()	2 3
dequeue() on an empty queue	-1
enqueue(1) dequeue() enqueue(2) front()	1 2	rear must be reset when the queue empties
enqueue(5) enqueue(6) size()	2
enqueue(7) dequeue() isEmpty()	7 true

(Confirm: O(1) per operation; −1 signals "empty"; no capacity limit; nodes are freed.)

How interviewers phrase it

• "Implement a queue using a linked list, with enqueue, dequeue and front" (GeeksforGeeks).

Clarifying questions to ask

1. What should dequeue return when the queue is empty?
2. Is there a maximum size? (No.)
3. Should all operations be O(1)? (Yes.)

Follow-ups to expect

1. "Why keep both front and rear pointers?"
2. "Why add at the rear and remove at the front, not the other way round?"
3. "What's the special case in dequeue?"
4. "What's the special case in enqueue?"
5. "Complexity?"

Related questions

• Introduction to Singly LinkedList Easy
• Insertion at the head of Linked List Easy
• Deletion of the head of LL Easy
• Find the length of the Linked List Easy
• Introduction to Doubly LL Easy
• Insert node before head in Doubly Linked List Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in