Stack Using Linked List

A linked-list stack stores each element in a node on the heap. The top of the stack is the head of a singly linked list: push prepends a new node (O(1)), and pop removes the head (O(1)). There is no separate “full” state unless memory is exhausted—growth is per push. This page uses the usual C pattern: a struct for a node with data and next.

On this page

Representation — Node, head pointer, logical top at head
Operations — prepend on push, remove head on pop, peek at head
Example in C — malloc/free, file-scope API, stack_last
Trade-offs — vs array-based stacks

1) Representation

The stack is a chain of nodes. The first node (head) is the top; walking next pointers goes toward the bottom. An empty stack is represented by head == NULL.

Typical pieces for a singly linked stack in C
Component	Role	Notes
`struct Node`	Holds one value (e.g. `int data`) and a `next` pointer to the rest of the list.	Each push allocates one node with `malloc`.
`head`	Points to the top node; `NULL` when the stack is empty.	Only pointer you must keep for this minimal design.
Heap	Nodes live on the heap until `pop` or `destroy` calls `free`.	Pop frees the old head; destroying the stack walks and frees every node.

2) Mapping operations to the list

Push allocates a node, sets its data, points its next at the current head, then moves head to the new node. Pop reads the head’s data, advances head, and frees the old node. Peek reads head->data without unlinking.

Stack operations with a singly linked list (top at `head`)
Operation	Steps	Failure case
`push(x)`	`malloc` a node, set `data = x`, `next = head`, `head = new`.	Out of memory if `malloc` returns `NULL`.
`pop`	If `head` not `NULL`: save value, `head = head->next`, `free` old node.	Underflow if empty.
`peek`	If `head` not `NULL`: read `head->data`.	Underflow if empty.
`destroy`	Repeatedly pop or walk and `free` every node; set `head = NULL`.	—

3) Example in C

Below, one stack uses a file-scope head pointer and a small Node type. Functions return 1 on success and 0 on underflow or allocation failure; after a successful peek or pop, read stack_last. main does not pass pointers into the stack API.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Top of stack = head of list; NULL means empty. */
static Node *head;

/* After stack_peek or stack_pop returns 1, read the value here. */
static int stack_last;

void stack_init(void) {
    head = NULL;
}

/* Free every node (safe to call multiple times after init). */
void stack_destroy(void) {
    Node *p = head;
    while (p != NULL) {
        Node *next = p->next;
        free(p);
        p = next;
    }
    head = NULL;
}

int stack_is_empty(void) {
    return head == NULL;
}

/* Returns 1 on success, 0 if malloc fails. */
int stack_push(int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return 0;
    n->data = value;
    n->next = head;
    head = n;
    return 1;
}

/* Returns 1 on success, 0 if underflow. */
int stack_pop(void) {
    if (stack_is_empty())
        return 0;
    Node *old = head;
    stack_last = old->data;
    head = old->next;
    free(old);
    return 1;
}

/* Returns 1 on success, 0 if underflow. */
int stack_peek(void) {
    if (stack_is_empty())
        return 0;
    stack_last = head->data;
    return 1;
}

int main(void) {
    stack_init();

    stack_push(10);
    stack_push(20);

    if (stack_peek())
        printf("peek: %d\n", stack_last);

    if (stack_pop())
        printf("pop: %d\n", stack_last);

    stack_destroy();
    return 0;
}

You can store other types by changing data or using a void * payload; multiple stacks would use separate head pointers (often wrapped in a struct Stack).

Explanation of the program output

Here’s the explanation of the program’s output in table format. List diagrams read head → … (top of stack first).

Program execution trace
Step	Operation	Stack state (top → bottom)	Return value	`stack_last` value	Output
1	`stack_init()`	empty (`head == NULL`)	(void)	unchanged	(none)
2	`stack_push(10)`	`head` → `10` → `NULL`	`1` (success)	unchanged	(none)
3	`stack_push(20)`	`head` → `20` → `10` → `NULL`	`1` (success)	unchanged	(none)
4	`stack_peek()`	unchanged (`20` still at head)	`1` (success)	`20`	`peek: 20`
5	`stack_pop()`	`head` → `10` → `NULL` (node `20` freed)	`1` (success)	`20`	`pop: 20`
6	`stack_destroy()`	empty (remaining node freed)	(void)	—	(none)
7	Program ends	—	—	—	—

Final output
Line	Output
1	`peek: 20`
2	`pop: 20`

Key points

Behavior	Explanation
Peek shows `20`	LIFO: the last pushed value (`20`) sits at `head`.
Pop shows `20`	Pop removes and frees the head node, which held `20`.
No output for pushes	`stack_push()` only returns a status code.
`10` not popped in `main`	`stack_destroy()` frees the remaining node (`10`) without printing.
Each push allocates	Unlike a contiguous array, every successful push calls `malloc` for a new node.

4) Trade-offs

Pros — No fixed capacity and no realloc of a whole block; push/pop stay O(1) time; size is limited only by memory.
Cons — Extra memory per node for next; pointer chasing hurts cache locality vs an array; many small allocations can fragment the heap.

Compare with a fixed array stack or a dynamic array stack when you prefer contiguous storage. Operation definitions are on Stack operations.

Key takeaway

Implement the stack at the head: push is prepend, pop is delete head. Keep every malloc paired with a free on pop or when tearing down the whole stack.