Stacks, queues and linked lists: dynamic data structures

In Year 4 of the technical school’s Computer Science and Telecommunications track (and the same goes for the applied-sciences high school), the computer science programme follows roughly this sequence: object-oriented programming, dynamic data structures, then HTML, CSS and JavaScript. At the start of October you are usually still on classes and objects. Dynamic data structures arrive in November, and the test, practical or written, falls between the end of November and December: from today, 5 October, that is 6-10 weeks. There is time, but this topic has one precise obstacle: it requires that you have really understood pointers. Anyone who left them half-learned in Year 3 or at the start of Year 4 pays the bill here. If you want to revise them, there is a post dedicated to pointers and memory in C.

In my lessons I see that the difficulty is not the code itself, which is short. It is keeping the picture in your head: who points to whom, and what happens if you move one arrow before another. That is why in this post I start from the picture and then get to the code.

Why an array is not enough

With an array you declare the size once and for all, and the elements sit next to each other in memory. This is convenient for reading: the element at index $i$ is reached in constant time, $O(1)$. There are two problems.

• Fixed size. If you need 100 slots and you declared 50, you are stuck. If you declare 10,000 to be safe, you waste memory.
• Inserting or removing in the middle is expensive. To insert an element at position $k$ you must shift every element after it by one place: in the worst case that is $n$ moves, that is $O(n)$. If complexity sounds unfamiliar, the post on complexity and big-O notation is the right place.

A dynamic data structure grows and shrinks while the program runs, asking for memory only for the elements that are really needed. The elements no longer sit next to each other: they are scattered, and each one knows where the next one is.

The node and the linked list

The basic unit is the node: a piece of data plus a pointer to the next node.

struct Node {
    int data;      // the stored value
    Node* next;    // pointer to the next node (nullptr if it is the last one)
};

A singly linked list is a chain of nodes. You only need a pointer to the first one, which we call the head. The last node has next equal to nullptr, and that is how the end is recognised. Drawn out:

head -> [10|*] -> [20|*] -> [40|nullptr]

An empty list is simply head == nullptr. This case must always be handled: we talk about it in the mistakes section.

Insertion at the head

This is the simplest and fastest operation, $O(1)$:

void insertAtHead(Node*& head, int value) {
    Node* fresh = new Node;   // allocate a node on the heap
    fresh->data = value;
    fresh->next = head;       // the new node points to the old head
    head = fresh;             // the head is now the new node
}

The order of the last two lines is everything. If you write head = fresh first, you have lost the only reference to the rest of the list. Note also Node*& head: I pass the pointer by reference, otherwise the function would modify a copy and the caller’s head would not change.

Insertion at the tail

Without a pointer to the tail you must walk the whole list, so $O(n)$:

void insertAtTail(Node*& head, int value) {
    Node* fresh = new Node;
    fresh->data = value;
    fresh->next = nullptr;
    if (head == nullptr) {        // empty list: the new node becomes the head
        head = fresh;
        return;
    }
    Node* p = head;
    while (p->next != nullptr) {  // stop on the last node, not beyond it
        p = p->next;
    }
    p->next = fresh;
}

Search

Node* find(Node* head, int value) {
    Node* p = head;
    while (p != nullptr && p->data != value) {
        p = p->next;
    }
    return p;   // nullptr if not found
}

The order of the two conditions in the while matters: if p is nullptr, the first condition is false and C++ does not evaluate the second, avoiding a read of p->data through a null pointer.

Deletion: the three cases

To remove a node you have to “step over” it and then free its memory. There are three cases.

1. Empty list: there is nothing to do.
2. Node at the head: I move the head to the second node.
3. Node in the middle or at the end: I need the previous node, because it is the one that must point to the successor of the deleted node. The last node is not a different case: its next is nullptr, so the previous node simply becomes the last one.

void remove(Node*& head, int value) {
    if (head == nullptr) return;            // case 1
    if (head->data == value) {              // case 2
        Node* toDelete = head;
        head = head->next;
        delete toDelete;
        return;
    }
    Node* prev = head;                      // case 3
    while (prev->next != nullptr && prev->next->data != value) {
        prev = prev->next;
    }
    if (prev->next != nullptr) {            // found
        Node* toDelete = prev->next;
        prev->next = toDelete->next;        // step over it
        delete toDelete;
    }
}

The pointer not to lose is toDelete: I save it before changing the links, so I can delete afterwards.

Stack: last in, first out

A stack is a LIFO structure (Last In, First Out): you always add and remove from the same side, like a pile of plates. The operations are:

• push(x): put x on top;
• pop(): remove the element on top;
• top(): look at the element on top without removing it;
• isEmpty(): tells you whether there are no elements.

It is implemented naturally on top of a list: the top of the stack is the head of the list, so push and pop are insertion and deletion at the head, both $O(1)$.

struct Stack {
    Node* topNode = nullptr;

    bool isEmpty() const { return topNode == nullptr; }

    void push(int x) {
        Node* fresh = new Node;
        fresh->data = x;
        fresh->next = topNode;
        topNode = fresh;
    }

    int pop() {                 // precondition: the stack is not empty
        Node* old = topNode;
        int value = old->data;
        topNode = topNode->next;
        delete old;
        return value;
    }

    int top() const { return topNode->data; }   // precondition: not empty
};

Real examples: the “undo” key of an editor (every action goes on top, undoing removes the last one), the browser’s “back” history, the handling of function calls, the checking of brackets.

For those who use Python, the same stack is written with a list used from one side only:

stack = []
stack.append(10)      # push
stack.append(20)
top = stack[-1]       # top -> 20
x = stack.pop()       # pop -> 20, the stack now contains [10]
is_empty = len(stack) == 0

Here Python hides the work with nodes, but the idea is the same: you always work on the end.

Queue: first in, first out

A queue is FIFO (First In, First Out): you insert from one side (the back) and remove from the other (the front), as when you stand in line at the checkout. The operations are enqueue(x) to join the queue and dequeue() to remove the first one. Examples: the print queue, requests to a server, waiting lists.

With a list that has only one pointer, insertion at the tail costs $O(n)$. The solution is to keep two pointers: head (the front) and tail (the last node).

struct Queue {
    Node* head = nullptr;   // elements are removed from here
    Node* tail = nullptr;   // elements are added here

    bool isEmpty() const { return head == nullptr; }

    void enqueue(int x) {
        Node* fresh = new Node;
        fresh->data = x;
        fresh->next = nullptr;
        if (tail == nullptr) {       // empty queue: first element
            head = tail = fresh;
        } else {
            tail->next = fresh;
            tail = fresh;
        }
    }

    int dequeue() {                  // precondition: queue not empty
        Node* old = head;
        int value = old->data;
        head = head->next;
        if (head == nullptr) tail = nullptr;   // the queue has become empty
        delete old;
        return value;
    }
};

The detail most often forgotten is exactly if (head == nullptr) tail = nullptr;: if you remove the last element and do not reset tail, the pointer is left hanging on a node that has already been deleted.

Costs compared

There is no structure that is best in absolute terms: it depends on what you do most often. If you constantly read by index, the array wins. If you insert and remove at the ends, a stack and a queue built on a list are perfect.

Typical mistakes

• Losing the reference to the rest of the list. Changing head or a next before saving where it pointed. Solution: first link the new node to the rest, then move the pointer.
• Forgetting the empty-list case. A head->next with head == nullptr is an access through a null pointer and the program stops. Every function must ask itself: what if it is empty? What if it has a single node?
• Not calling delete. Every new has its delete. If you remove a node by stepping over it but you do not free it, that memory stays occupied until the end of the program: it is a memory leak. Remember also to empty the whole structure at the end.
• Using a pointer after delete. After delete p; do not read p->data any more. Save what you need first.
• Unchecked nullptr. while (p->next != nullptr) is right if you are sure that p is not null; otherwise check p first.

If you feel you always make the same kind of mistake, it is almost always a problem with the picture: before writing the code, draw the diagram with the arrows.

Worked exercises

Exercise 1: insertion at the head and deletion in the middle

Start from the list

head -> [10] -> [20] -> [40] -> nullptr

Insert 5 at the head, then delete the node with value 20.

Insertion of 5.

1. I create the node fresh = [5|?].
2. fresh->next = head: the new node points to 10.

fresh -> [5] -> [10] -> [20] -> [40] -> nullptr
head ----------^

3. head = fresh: now the head points to 5.

head -> [5] -> [10] -> [20] -> [40] -> nullptr

Deletion of 20. The value is not at the head (the head is 5), so we are in case 3. prev starts from 5 and moves along until prev->next->data is 20:

• prev = node 5: prev->next->data = 10, different from 20, I move on.
• prev = node 10: prev->next->data = 20, I stop.

Then toDelete = prev->next (the node 20), then prev->next = toDelete->next: the node 10 now points to 40.

head -> [5] -> [10] -> [40] -> nullptr
                         [20] (detached)

Finally delete toDelete frees the node 20. Final list: 5, 10, 40.

Exercise 2: balanced brackets with a stack

Rule: I scan the string. Every opening bracket ((, [, {) goes on the stack. Every closing bracket must match the one on top of the stack: if the stack is empty or the top does not match, the string is unbalanced. At the end the stack must be empty.

String 1: {[(a+b)*c]-d}. I consider only the brackets, in order: { [ ( ) ] }.

Stack empty at the end: balanced.

String 2: ([)].

I stop: unbalanced, even though there are two opening and two closing brackets. Counting the brackets is not enough, you need the order, and that is exactly what the stack gives.

Exercise 3: a sequence of enqueue and dequeue

The queue is initially empty. Operations: enqueue(5), enqueue(8), dequeue(), enqueue(3), enqueue(9), dequeue(), dequeue(), enqueue(7). What is the final state?

I write the queue with the first element on the left.

1. enqueue(5): [5]
2. enqueue(8): [5, 8]
3. dequeue(): 5 leaves, [8] remains
4. enqueue(3): [8, 3]
5. enqueue(9): [8, 3, 9]
6. dequeue(): 8 leaves, [3, 9] remains
7. dequeue(): 3 leaves, [9] remains
8. enqueue(7): [9, 7]

Final state: 9 at the front, 7 at the back. The elements that left, in order, are 5, 8, 3: the same order in which they came in, which is the signature of a FIFO. With a stack, for the same operations, the first pop would have removed 8, not 5.

Practice and practice tests

There is not yet a computer science practice test on the site for this topic. For the other subjects you can look at the high school practice tests category, while the Computer Science page explains how I work on the subject. My practical advice for the test: rewrite by hand, without looking, insertion at the head, deletion and push/pop; then run the code with three cases (empty list, one node, many nodes). When those three cases work, you have understood.

To see what all this is for, it may also help to read how to think about classes and objects in C++, because stacks and queues are often asked for exactly as classes, and how the same “linked nodes” pattern then leads to graphs, trees and BFS and DFS traversals. If instead your basics with arrays still feel shaky, start from loops and arrays.

If something does not add up

Dynamic data structures are one of those topics where either the right picture clicks, or you stay stuck on the same mistake for weeks. If you recognise yourself, you can write to me from the contact page: we do a free introductory call, look at where the reasoning jams and decide whether you really need a lesson or a few targeted pointers are enough.