Linked Queue in C++: Leaks, Empty Dequeue, Benchmarks

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled the linked queue with Apple clang 21 (-Wall -Wextra: no warnings) and the sample output still matches: 80, 90, 89. But the program leaks every node it dequeues (5 leaks, found with the macOS leaks tool), and a dequeue on an empty queue dereferences a null pointer, which UBSan and ASan both catch. Below are those reports, a fixed class that owns its nodes, and timings against a ring buffer, std::queue and C# Queue<T>.

This article is for anyone writing a queue on top of linked nodes in C or C++, whether for a class, an interview or a job scheduler, and for C# developers comparing it with Queue<T>. A queue is first in, first out (FIFO): you enqueue at the rear and dequeue at the front. The linked version needs no capacity limit and both operations are O(1), but it makes two mistakes easy: forgetting who frees a node, and touching front when there is none. It was also about 16 times slower than an array ring buffer in our measurements.

How a linked queue works

Picture a line at a ticket machine: newcomers join at the back, the person at the front leaves. A linked queue keeps two pointers:

• front, the node to remove next,
• rear, the last node, so that enqueue does not have to walk the list.

Enqueue creates a node, links it after rear, and moves rear to it. Dequeue takes front and moves front to the next node. When the last node leaves, rear must be reset too, or it keeps pointing at freed memory. Unlike the circular queue, there is no "full" state; the queue grows until memory runs out. If you need a refresher on nodes and next pointers, see linked lists.

Running the 2021 code: output correct, nodes leaked

The 2021 class had enqueue, a dequeue that returned Node*, isEmpty, getSize, and a destructor that dequeued and deleted until the queue was empty. The sample main did:

lq.enqueue(50); lq.enqueue(60); lq.dequeue();
lq.enqueue(80); lq.enqueue(90); lq.dequeue();
lq.enqueue(89);
size = lq.getSize();
for (int i = 0; i < size; i++)
    cout << "dequeued: " << lq.dequeue()->data << endl;

Output with clang 21, same values as in 2021:

dequeued: 80
dequeued: 90
dequeued: 89

The destructor looks responsible, but it only frees nodes that are still in the queue. Every node returned by dequeue() became the caller's job, and main dropped all of them: the two bare lq.dequeue(); calls ignore the return value, and lq.dequeue()->data reads the value and loses the pointer. By the time the destructor runs, the queue is empty, so it frees nothing.

AddressSanitizer's leak detection is not available on Apple Silicon macOS (detect_leaks is not supported on this platform), so the ASan run was clean and told us nothing. The system leaks tool did:

$ leaks --atExit -- ./linked_queue_2021
Process 64094: 5 leaks for 160 total leaked bytes.
    5 (160 bytes) ROOT LEAK: <malloc in LinkedQueue::enqueue(int)> [32]

Five nodes in, five dequeued, five leaked. This is the trap of returning an owning raw pointer: nothing in the signature Node* dequeue() says "you must delete this".

Dequeue on an empty queue

The 2021 dequeue starts with:

Node* temp = front;
if (front->nextNode == NULL)   // "one node or fewer"

The comment says "one node or fewer", but with zero nodes front is NULL and the very first line of the check reads through it. We added one more dequeue() after the loop:

plain build:  exit code 139 (segmentation fault)

UBSan:  lq_2021.cpp:22:20: runtime error: member access within null pointer of type 'Node'
ASan:   ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008
            #0 in LinkedQueue::dequeue() lq_2021.cpp:22
            #1 in main lq_2021.cpp:41

Address 0x8 is the offset of nextNode inside Node (after a 4-byte int and 4 bytes of padding). The 2021 destructor is safe only because it checks isEmpty() before each dequeue(); any other caller has to remember to do the same.

The fixed linked queue

The fix moves both responsibilities into the class: dequeue checks for empty, copies the value out, resets rear when the queue becomes empty, and deletes the node itself. Copying is disabled so two queues never share nodes.

class LinkedQueue {
    struct Node { int data; Node* next; };
    Node* front_ = nullptr; Node* rear_ = nullptr; int size_ = 0;
public:
    LinkedQueue() = default;
    ~LinkedQueue() { int v; while (dequeue(v)) {} }          // frees every node still queued
    LinkedQueue(const LinkedQueue&) = delete;
    LinkedQueue& operator=(const LinkedQueue&) = delete;
    void enqueue(int v) {
        Node* n = new Node{v, nullptr};
        if (rear_) rear_->next = n; else front_ = n;
        rear_ = n; ++size_;
    }
    bool dequeue(int& out) {                                 // empty queue -> false
        if (!front_) return false;
        Node* n = front_;
        out = n->data;
        front_ = n->next;
        if (!front_) rear_ = nullptr;
        delete n;                                            // the queue owns its nodes
        --size_; return true;
    }
    bool empty() const { return front_ == nullptr; }
    int size() const { return size_; }
};

Running the same sequence, then one extra dequeue, then leaving two items in the queue on purpose so the destructor has work to do:

dequeued: 80
dequeued: 90
dequeued: 89
dequeue on empty -> false

ASan/UBSan: no report
leaks:      Process 64434: 0 leaks for 0 total leaked bytes.

If the queue holds objects rather than int, the same idea works with std::optional<T> dequeue(), or with std::unique_ptr<Node> links so ownership is enforced by the type system.

Built-in equivalents: std::queue and C# Queue

std::queue<T> is an adapter over std::deque<T> by default. front() and pop() on an empty std::queue are undefined behavior, so check empty() first, exactly as with our class.

In C#, Queue<T> is a growable circular array, and it reports an empty dequeue with an exception. Verified on .NET 10:

var q = new Queue<int>([50, 60]);
q.Dequeue(); q.Enqueue(80); q.Enqueue(90); q.Dequeue(); q.Enqueue(89);
while (q.TryDequeue(out var v)) Console.Write($"{v} ");   // 80 90 89
Console.WriteLine(q.TryDequeue(out _));                     // False
q.Dequeue();   // InvalidOperationException: Queue empty.

The garbage collector removes the leak problem entirely, which is the main thing the managed version buys you; the empty case still needs TryDequeue or a Count check.

Measured: linked vs ring buffer vs std::queue vs C

Two workloads on int, three runs each. C++ with Apple clang 21 -O2, C# with .NET 10.0.14 Release, Apple M1 Pro.

• Fill and drain: 10 million enqueues, then 10 million dequeues.
• Steady state: 1,000 items queued, then 10 million enqueue+dequeue pairs (a job queue that never grows).

The 2021 article concluded that the linked queue is simpler while the circular queue is faster, and the numbers agree: about 16 times slower to fill and drain, and about 20 times slower in steady state, where the ring buffer reuses the same 4 KB of memory and the linked queue still calls new and delete for every item. A doubly linked std::list is slower still because each node carries two pointers. The C# runs exclude JIT warm-up (the first of four runs was discarded).

When a linked queue is still the right choice

The same ownership question appears in the stack article, where the 2021 linked stack leaked all six of its nodes for the same reason.

Tested with Apple clang 21.0.0 (-Wall -Wextra, -fsanitize=address,undefined -g), macOS leaks, and .NET SDK 10.0.403 / runtime 10.0.14 on an Apple M1 Pro.