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

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

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

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

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

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

## Complexity

| Case | Cost |
| --- | --- |
| push (insert at head) | O(1) |
| pop (delete head) | O(1) |
| peek / isEmpty | O(1) |

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.

## Videos

- [Linked List implementation of stacks](https://youtu.be/MuwxQ2IB8lQ) (mycodeschool): Shows why the head (not the tail) must be the top, and writes push/pop in C/C++.
- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): A recap of the stack ADT if you skipped the array version.

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

## Quick check

1. In a linked-list stack, push is the same as…
   A. insert at the end
   B. insert at the front (head)
   C. insert at a position
   D. sorting the list
   Answer: B. The head is the top, so push is an O(1) insert at the front.

2. Bracket check on `([)]`: what happens at `)`?
   A. top is `(`, match
   B. top is `[`, mismatch, so not balanced
   C. stack is empty
   D. it is skipped
   Answer: B. After `(` and `[` the top is `[`, which does not match `)`.

3. What is wrong with this pop?

```cpp
Node* temp = top;
delete temp;
int x = top->data;
top = top->next;
```
   A. Nothing
   B. It reads freed memory after delete
   C. It never moves top
   D. It leaks memory
   Answer: B. Read the data and move top first, then delete.

4. Main advantage of the linked-list stack over the array stack?
   A. Faster push
   B. No fixed capacity
   C. Less memory per item
   D. Random access
   Answer: B. It grows as needed. The cost is an extra pointer per item.

## Practice

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

Solution:

`{[()()]}`: `{` → `{[` → `{[(` → `{[` → `{[(` → `{[` → `{` → 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.

**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: This page's `balanced()` function, almost unchanged.
- [Simplify Path](https://leetcode.com/problems/simplify-path/) (medium). Hint: Split by `/`. Push folder names, pop on `..`, ignore `.` and empty parts. Join what is left.
- [Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/) (medium). Hint: Push a 0 for each `(`. On `)`, pop v; add `max(2*v, 1)` to the new top.

## Mastery checklist

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