# 5.4 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.

Chapter: Stacks & Queues · ~30 min · easy
URL: https://dsa.fetehadin.com/learn/queue-list

## Mental 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

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

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

## C++ code: queue-list.cpp

```cpp
#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:

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

## Complexity

| Case | Cost |
| --- | --- |
| enqueue (insert after rear) | O(1) |
| dequeue (delete front) | O(1) |
| peek / isEmpty | O(1) |

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.

## Videos

- [Linked List implementation of Queue](https://youtu.be/A5_XdiK4J8A) (mycodeschool): Explains why you need both front and rear, and writes enqueue/dequeue in C/C++.

## Exam 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.

## Quick check

1. Where does a linked-list queue insert and delete?
   A. insert at front, delete at rear
   B. insert at rear, delete at front
   C. both at front
   D. both at rear
   Answer: B. Deleting the head is O(1); inserting after a known tail is O(1). Deleting the tail would be O(n).

2. The queue has one node. After dequeue, what must be true?
   A. front == rear, both pointing at freed memory
   B. front == nullptr and rear == nullptr
   C. only front == nullptr
   D. rear->next == nullptr
   Answer: B. If rear still points to the deleted node, the next enqueue writes to freed memory.

3. Without a rear pointer, enqueue costs…
   A. O(1)
   B. O(log n)
   C. O(n)
   D. O(n²)
   Answer: C. You would have to walk from front to the last node every time.

## Practice

**Trace by hand.** Draw front, rear and the nodes after: enqueue 4, enqueue 9, dequeue, dequeue, enqueue 1.

Solution:

- 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.

**Problems:**

- [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/) (easy). Hint: A queue of timestamps. Drop the old ones from the front.
- [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) (easy). Hint: Two stacks. Amortised O(1) per operation.

## Mastery checklist

- [ ] 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.