5.2 ~35 min easy

Stacks with a Linked List

The same stack ADT, but the top is the head of a linked list. No fixed capacity, push and pop stay O(1), and the bracket-matching application.

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

02Mental model

An array stack is a box with a fixed number of slots. A linked-list stack is a pile that can grow forever: each new plate is a new node, linked to the plate under it.

The trick is choosing which end is the top. In a singly linked list, the head is the only end where both insert and delete are O(1). So:

push(x) = insert at the front: top = new Node{x, top};
pop() = delete the front: save top, move top = top->next, delete the old node.

There is no isFull(). The list only fills up if the whole heap runs out.

Array or linked list?

	Array stack	Linked-list stack
Capacity	fixed (MAX)	grows as needed
Memory per item	just the value	value + pointer
Speed	O(1), cache-friendly	O(1), one `new`/`delete` each
Can overflow?	yes	no (until the heap is exhausted)

Application: balanced brackets

Scan the string left to right. Push every opening bracket. At a closing bracket the stack’s top must be its partner; pop it. Fail if the stack is empty or the partner is wrong. At the end the stack must be empty.

03Visualize

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

Loading visualizer…

Each push creates a node in front of the old top. Each pop unlinks the top node and deletes it.

04C++ code

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

stack-list.cpp40 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
#include <string>
using namespace std;

class Stack {
    struct Node { char data; Node* next; };
    Node* top = nullptr;
public:
    bool isEmpty() const { return top == nullptr; }
    void push(char x) { top = new Node{x, top}; }
    char pop() {
        if (isEmpty()) return '\0';
        Node* temp = top;
        char x = temp->data;
        top = top->next;
        delete temp;
        return x;
    }
    char peek() const { return isEmpty() ? '\0' : top->data; }
    ~Stack() { while (!isEmpty()) pop(); }
};

// Classic stack application: are the brackets balanced?
bool balanced(const string& s) {
    Stack st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char o = st.pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return st.isEmpty();
}

int main() {
    for (string s : {"{[()()]}", "([)]", "((", "a*(b+c)"})
        cout << s << " -> " << (balanced(s) ? "balanced" : "not balanced") << "\n";
}

#include <iostream>
#include <string>
using namespace std;

class Stack {
    struct Node { char data; Node* next; };
    Node* top = nullptr;
public:
    bool isEmpty() const { return top == nullptr; }
    void push(char x) { top = new Node{x, top}; }
    char pop() {
        if (isEmpty()) return '\0';
        Node* temp = top;
        char x = temp->data;
        top = top->next;
        delete temp;
        return x;
    }
    char peek() const { return isEmpty() ? '\0' : top->data; }
    ~Stack() { while (!isEmpty()) pop(); }
};

// Classic stack application: are the brackets balanced?
bool balanced(const string& s) {
    Stack st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char o = st.pop();
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{')) return false;
        }
    }
    return st.isEmpty();
}

int main() {
    for (string s : {"{[()()]}", "([)]", "((", "a*(b+c)"})
        cout << s << " -> " << (balanced(s) ? "balanced" : "not balanced") << "\n";
}

Expected output

{[()()]} -> balanced
([)] -> not balanced
(( -> not balanced
a*(b+c) -> balanced

05Complexity

push (insert at head)	O(1)
pop (delete head)	O(1)
peek / isEmpty	O(1)
Extra space	O(n), one node (data + pointer) per item

Use the head as the top. Pushing and popping at the tail of a singly linked list would be O(n), because you would need the node before the tail.

06Watch

Linked List implementation of stacks

mycodeschool · 10:58

Why this one: Shows why the head (not the tail) must be the top, and writes push/pop in C/C++.

Watched

Introduction to stack

mycodeschool · 8:26

Why this one: A recap of the stack ADT if you skipped the array version.

Watched

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

07Exam lens

Likely questions

Implement a stack using a singly linked list. Which end is the top and why?
Compare array and linked-list stacks (capacity, memory, speed).
Use a stack to check whether {[()]} and ([)] are balanced. Show the stack at each step.
Why does the linked-list stack have no isFull()?

Common mistakes

Using the tail as the top, making pop O(n).
Forgetting delete in pop (memory leak).
Reading top->data after deleting the node. Save the value first.
In bracket matching, forgetting that the stack must be empty at the end ((( is not balanced).

08Quick check

1.In a linked-list stack, push is the same as…
2.Bracket check on ([)]: what happens at )?
3.What is wrong with this pop?
```
Node* temp = top;
delete temp;
int x = top->data;
top = top->next;
```
4.Main advantage of the linked-list stack over the array stack?

09Practice

🟢 Trace by hand

Run the bracket checker on {[()()]} and a*(b+c)). Write the stack after each bracket.

Show answer

{[()()]}: { → {[ → {[( → {[ → {[( → {[ → { → empty. Balanced.

a*(b+c)): ( → empty (matched) → second ) finds an empty stack. Not balanced.

🟡 Implement it

Write string toPostfix(string infix) for single-letter operands with + - * / and brackets, using your stack.

Hint

Letters go straight to output. ( is pushed. ) pops until (. An operator pops every operator of higher or equal precedence first, then is pushed. Pop the rest at the end.

🔴 Solve problems

Valid Parentheses easyleetcode.com
Hint
This page's balanced() function, almost unchanged.
Simplify Path mediumleetcode.com
Hint
Split by /. Push folder names, pop on .., ignore . and empty parts. Join what is left.
Score of Parentheses mediumleetcode.com
Hint
Push a 0 for each (. On ), pop v; add max(2*v, 1) to the new top.

10Mastery checklist

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

I can implement push and pop on a linked list in O(1).
I can explain why the head is the top.
I can check balanced brackets with a stack and trace it.
I can compare array and linked-list stacks.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet