5.4 ~30 min easy

Queues with a Linked List

Keep two pointers, front and rear. Enqueue at the rear and dequeue at the front, both O(1), with no capacity limit.

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

Picture a conga line. Each dancer holds the shoulders of the dancer in front. New dancers join at the back; the leader leaves from the front.

A linked-list queue keeps two pointers:

front → the head node. Dequeue removes it: O(1).
rear → the last node. Enqueue links a new node after it: rear->next = n; rear = n;, O(1).

Why not the other way round? Removing the tail of a singly linked list needs the node before it, and finding that node means walking the whole list.

The two edge cases

Enqueue into an empty queue: there is no rear->next to set. Point both front and rear at the new node.
Dequeue the last node: front becomes nullptr. Set rear = nullptr too, or it will dangle.

There is no isFull(), and no wasted slots.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Dequeue until the queue is empty and watch rear reset to nullptr too.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

queue-list.cpp38 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

class Queue {
    struct Node { int data; Node* next; };
    Node* front = nullptr;
    Node* rear = nullptr;
public:
    bool isEmpty() const { return front == nullptr; }
    void enqueue(int x) {
        Node* n = new Node{x, nullptr};
        if (rear == nullptr) { front = rear = n; return; }
        rear->next = n;
        rear = n;
    }
    int dequeue() {
        if (isEmpty()) { cout << "Empty\n"; return -1; }
        Node* temp = front;
        int x = temp->data;
        front = front->next;
        if (front == nullptr) rear = nullptr;   // queue became empty
        delete temp;
        return x;
    }
    int peek() const { return isEmpty() ? -1 : front->data; }
    ~Queue() { while (!isEmpty()) dequeue(); }
};

int main() {
    Queue q;
    q.enqueue(4); q.enqueue(9); q.enqueue(6);
    cout << "front: " << q.peek() << "\n";
    cout << "served: ";
    while (!q.isEmpty()) cout << q.dequeue() << " ";
    cout << "\n";
    q.enqueue(1);                       // works again after becoming empty
    cout << "front after reuse: " << q.peek() << "\n";
}

#include <iostream>
using namespace std;

class Queue {
    struct Node { int data; Node* next; };
    Node* front = nullptr;
    Node* rear = nullptr;
public:
    bool isEmpty() const { return front == nullptr; }
    void enqueue(int x) {
        Node* n = new Node{x, nullptr};
        if (rear == nullptr) { front = rear = n; return; }
        rear->next = n;
        rear = n;
    }
    int dequeue() {
        if (isEmpty()) { cout << "Empty\n"; return -1; }
        Node* temp = front;
        int x = temp->data;
        front = front->next;
        if (front == nullptr) rear = nullptr;   // queue became empty
        delete temp;
        return x;
    }
    int peek() const { return isEmpty() ? -1 : front->data; }
    ~Queue() { while (!isEmpty()) dequeue(); }
};

int main() {
    Queue q;
    q.enqueue(4); q.enqueue(9); q.enqueue(6);
    cout << "front: " << q.peek() << "\n";
    cout << "served: ";
    while (!q.isEmpty()) cout << q.dequeue() << " ";
    cout << "\n";
    q.enqueue(1);                       // works again after becoming empty
    cout << "front after reuse: " << q.peek() << "\n";
}

Expected output

front: 4
served: 4 9 6 
front after reuse: 1

05Complexity

enqueue (insert after rear)	O(1)
dequeue (delete front)	O(1)
peek / isEmpty	O(1)
Extra space	O(n)

Both ends are O(1) only because we keep a rear pointer. Without it, enqueue would have to walk the whole list.

06Watch

Linked List implementation of Queue

mycodeschool · 14:16

Why this one: Explains why you need both front and rear, and writes enqueue/dequeue in C/C++.

Watched

Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity

07Exam lens

Likely questions

Implement a queue with a singly linked list. Which end is front, which is rear, and why?
What must happen to rear when the last node is dequeued?
Compare array and linked-list queues.

Common mistakes

Dequeuing from the tail (needs the previous node, so O(n)).
Forgetting rear = nullptr when the queue becomes empty. The next enqueue then writes through a dangling pointer.
Enqueue into an empty queue without setting both front and rear.
Forgetting delete in dequeue.

08Quick check

1.Where does a linked-list queue insert and delete?
2.The queue has one node. After dequeue, what must be true?
3.Without a rear pointer, enqueue costs…

09Practice

🟢 Trace by hand

Draw front, rear and the nodes after: enqueue 4, enqueue 9, dequeue, dequeue, enqueue 1.

Show answer

enqueue 4 → 4, front = rear = node(4)
enqueue 9 → 4 → 9, rear = node(9)
dequeue → returns 4, list 9, front = rear = node(9)
dequeue → returns 9, list empty, front = rear = nullptr
enqueue 1 → 1, front = rear = node(1)

🟡 Implement it

Add int size() in O(1) and a print() to the queue class.

Hint

Keep a count member. Increment it in enqueue, decrement it in dequeue.

🔴 Solve problems

Number of Recent Calls easyleetcode.com
Hint
A queue of timestamps. Drop the old ones from the front.
Implement Queue using Stacks easyleetcode.com
Hint
Two stacks. Amortised O(1) per operation.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can implement enqueue and dequeue with front and rear pointers.
I can handle the empty-queue and one-node cases.
I can explain why front is the head and rear is the tail.

0/3 ticked

My notes

View as Markdown · Chapter cheat sheet