Over the last three posts, we created a tailless linked list, extended it into a tailed list, and finally we implemented a double linked list that solved the O(n) complexity hurdles. Each step added speed, but with that came some tradeoffs along with complexity.

For Day 4, I have decided that the next logical step is to implement a Stack data structure, but instead of starting from raw memory and building everything from scratch, we’re going to focus on behavior and benchmarks first (this will all make sense at the end of the blog post so hang with me).

---

What Is a Stack?

A stack is one of the simplest and most fundamental data structures in computer science.

It follows a single rule:

Last In, First Out (LIFO)

If you push items onto a stack:

Push A
Push B
Push C

Then popping removes them in reverse order:

Pop → C
Pop → B
Pop → A

---

Core Stack Operations

A stack usually exposes a very small API, and we will keep the operations to just these to make our lives easy:

push()      // Add item to top
pop()       // Remove item from top
peek()      // Read top without removing
is_empty()  // Check if stack is empty

Notice something important here:

A stack only ever interacts with one end of the structure — the top.

This turns out to matter a lot when choosing how to implement one. For the astute among you, you can probably see where we are going with this given our last few posts.

---

Why Stacks Matter in Real Systems

Stacks show up everywhere:

• Function call stacks
• Undo/redo systems
• Expression parsing
• DFS graph traversal
• Embedded buffering patterns
• Temporary working memory in algorithms

---

Performance First — Benchmarking the Implementation

Before we talk about how this stack is implemented, let’s look at real performance numbers.

These benchmarks are:

• push
• peek
• pop

Each push allocates memory.
Each pop frees memory.

This is the “honest” cost of dynamic allocation, and this performance readout follows the same general structure as the ones in our last posts:

=== Stack (L****d L**t) Benchmark ===
Real implementation timing (includes malloc/free)

=============================
BENCH N=1000
=============================
push         O(1)/op total O(N)   |      0.031 ms |       30.9 ns/op
peek         O(1)/op              |      0.987 ms |        0.5 ns/op (REPS=2000000)
pop          O(1)/op (+free)      |      0.008 ms |        8.3 ns/op

=============================
BENCH N=3000
=============================
push         O(1)/op total O(N)   |      0.089 ms |       29.6 ns/op
peek         O(1)/op              |      1.112 ms |        0.6 ns/op (REPS=2000000)
pop          O(1)/op (+free)      |      0.026 ms |        8.7 ns/op

=============================
BENCH N=10000
=============================
push         O(1)/op total O(N)   |      0.272 ms |       27.2 ns/op
peek         O(1)/op              |      1.023 ms |        0.5 ns/op (REPS=2000000)
pop          O(1)/op (+free)      |      0.087 ms |        8.7 ns/op

=============================
BENCH N=30000
=============================
push         O(1)/op total O(N)   |      0.699 ms |       23.3 ns/op
peek         O(1)/op              |      0.939 ms |        0.5 ns/op (REPS=2000000)
pop          O(1)/op (+free)      |      0.235 ms |        7.8 ns/op

=============================
BENCH N=100000
=============================
push         O(1)/op total O(N)   |      2.360 ms |       23.6 ns/op
peek         O(1)/op              |      0.935 ms |        0.5 ns/op (REPS=2000000)
pop          O(1)/op (+free)      |      0.786 ms |        7.9 ns/op

Ignore the censored part of the metrics 🙂

The key takeaways:

Operation	Complexity
push	O(1)
pop	O(1)
peek	O(1)

This is exactly what we want from a stack, and it is also identical to the previous charts for our tailless, tailed, and doubly linked list implementations.

---

The Important Engineering Idea

Here’s the key concept for this post:

A data structure is defined by its behavior and guarantees — not by how it is stored internally.

If another structure already provides the complexity guarantees we need…

We can reuse it.

---

Surprise! — The Stack Is Just Our Linked List!

This entire stack implementation is built on top of our tailless singly linked list.

No new node structures.
No new memory management.
No new traversal logic.

Just restricted access.

---

Mapping Stack Operations → Linked List Operations

Stack	Linked List
push	push_front
pop	pop_front
peek	front

That’s it.

A stack is literally:

A linked list where you are only allowed to touch the head.

Because of this, our tailless linked list fits the bill perfectly. Here is ALL the code for your reference:

---

stack.h

#ifndef STACK_H
#define STACK_H

#include "linked_list.h"

// our stack is literally just wrapping our tailless linked list
struct Stack {
        struct Node* head;
        size_t size;
};

void stack_init(struct Stack* s);
void stack_destroy(struct Stack* s);

int stack_push(struct Stack* s, struct Node* n);
int stack_pop(struct Stack* s);
struct Node* stack_peek(const struct Stack* s);

int stack_is_empty(const struct Stack* s);
size_t stack_size(const struct Stack* s);

#endif

stack.c

#include "stack.h"

void stack_init(struct Stack* s) {
        if (!s) return;
        s->head = NULL;
        s->size = 0;
}

void stack_destroy(struct Stack* s) {
        if (!s) return;
        list_destroy(&s->head); // uses linked_list.c
        s->size = 0;
}

int stack_push(struct Stack* s, struct Node* n) {
        if (!s || !n) return -1;
        push_front(n, &s->head); // uses linked_list.c
        s->size++;
        return 0;
}

int stack_pop(struct Stack* s) {
        if (!s || !s->head) return -1;
        pop_front(&s->head); // uses linked_list.c (and frees node)
        s->size--;
        return 0;
}

struct Node* stack_peek(const struct Stack* s) {
        if (!s) return NULL;
        return front(s->head); // uses linked_list.c
}

int stack_is_empty(const struct Stack* s) {
        return (!s || s->head == NULL);
}

size_t stack_size(const struct Stack* s) {
        return s ? s->size : 0;
}

And for the code we reference in the above files, you can simply visit my post on tailless linked lists.

So, did I cheat for today by using a bunch of code I already wrote? Kind of. However, later on, I promise it will all make sense when we eventually revisit some of these data structures in the future, but that is far, far away.