Queue (Linked List Implementaion) Visualization

A queue as a linked list

A queue is a first-in, first-out (FIFO) collection. Enqueue adds an item at the back, and dequeue removes the item at the front, which is always the one that has waited longest. This page builds a queue from linked nodes instead of an array. The queue grows one node at a time, so it never becomes "full" (as long as memory lasts), and both operations still take O(1) time.

The idea in plain words

Each node holds one value and a next pointer to the node that joined the line after it. We keep two pointers into the chain:

• head points to the front node (the oldest item). That is where we dequeue.
• tail points to the back node (the newest item). That is where we enqueue.

The links go from front to back. Removing the front node only needs head = head.next, and adding a node at the back only needs tail.next = new node. Neither needs a walk through the list. Why this direction? If the links went from back to front, a dequeue would have to find the node before the front node. In a singly linked list that means walking the whole list.

What the animation shows

The Head box is at the top left and the Tail box at the bottom left. A box with a slash is a null pointer. The nodes are drawn from left to right, from the front to the back of the queue (8 per row), with arrows for the next links. On Enqueue a new node appears at the top and gets the value. Then the old back node's link and the Tail pointer are redirected to it, and the nodes slide into place. On Dequeue the front value moves up to "Dequeued Value", Head is moved to the second node, and the old front node disappears. The animation shows at most 32 nodes.

The operations

Node:  value, next
head = null;  tail = null

isEmpty():  return head == null

enqueue(x):
    n = new Node(x);  n.next = null
    if tail == null:          // queue was empty
        head = n
        tail = n
    else:
        tail.next = n         // old back node links to the new one
        tail = n

dequeue():
    if head == null: error "queue empty"
    x = head.value
    head = head.next
    if head == null:          // we removed the only node
        tail = null
    return x                  // (free the old node in C/C++)

front():  return head.value     // if not empty

The two ifs are the empty-queue special cases. When the queue is empty, both pointers change on an enqueue, because the new node is both the front and the back. When the last node is dequeued, both must become null again.

A worked example

operation     pointer changes                               queue (front → back)
start         head = null, tail = null                      (empty)
enqueue 10    new node N10; tail was null, so               10
              head = N10, tail = N10
enqueue 20    new node N20; N10.next = N20; tail = N20      10 → 20
enqueue 30    new node N30; N20.next = N30; tail = N30      10 → 20 → 30
dequeue       x = 10; head = N10.next = N20                 20 → 30        returns 10
dequeue       x = 20; head = N20.next = N30                 30              returns 20
              (head == tail == N30 now: one node)
dequeue       x = 30; head = N30.next = null,               (empty)         returns 30
              so also tail = null
enqueue 40    new node N40; tail is null again, so          40
              head = N40, tail = N40

Look at the third dequeue. If we forgot tail = null, then tail would still point at the removed node N30. The next enqueue would then do N30.next = N40 on a dead node and leave head null. N40 would be lost and the queue would look empty. That is the most common bug in this data structure.

Why it is correct

The invariant is: either the queue is empty and head == tail == null, or head points to the oldest item, following next from it visits every item in the order they arrived, and tail is the last node (its next is null). Enqueue keeps this true because the new node is attached after the last node and becomes the new last node. On an empty queue the new node is the only node, so it is both first and last. Dequeue keeps it true because the second-oldest node becomes the new first node. If there is none, the queue has become empty and both pointers are null. Since items are only added after the last node and only removed at the first, they leave in the order they arrived: FIFO.

Time and space complexity

• enqueue, dequeue, front and isEmpty are all O(1) in the worst case: a fixed number of pointer assignments and no loops. Array queues are only O(1) amortized when they have to grow. A linked queue never copies anything.
• Keeping a count field makes size() O(1) too. Without it, counting takes O(n).
• Space is O(n) for n items, but each item also carries a pointer, and every node is a separate memory allocation. The nodes are scattered in memory, which makes a linked queue slower in practice than a circular-array queue because of cache misses and allocation cost.

Common mistakes, edge cases and variants

• Not setting tail = null when the last node is dequeued (see the example above).
• On an enqueue into an empty queue, setting tail but forgetting head.
• Linking in the wrong direction (back to front), which turns dequeue into an O(n) walk.
• Keeping only head: then enqueue has to walk to the end, which is O(n). A neat alternative is a circular singly linked list with just a tail pointer, where tail.next is the front.
• Sentinel (dummy) node: start with one dummy node that head and tail both point to. Then the queue is never physically empty, and the special cases disappear.
• Deque: with a doubly linked list (prev and next pointers), you can add and remove at both ends in O(1).
• Priority queue: items leave by priority, not by arrival time. Use a heap (see Heap).
• Stack vs queue: a linked stack pushes and pops at the same end (the head), so it needs only one pointer (see Stack (linked list) and Stack (array)).

Where it is used

• Queues with no fixed size limit: job and message queues, event queues in GUI toolkits, and request queues in servers.
• Operating-system scheduler run queues and I/O wait lists, which are often intrusive linked lists where the next pointer lives inside the task structure.
• Lock-free concurrent queues (the Michael–Scott queue, used for example in Java's ConcurrentLinkedQueue), which are built on exactly these head and tail pointers plus a sentinel node.
• Breadth-first search and level-order tree traversal.

References

Queue (abstract data type)