Linked List Stack Implementation: Dynamic and Flexible

How a Linked List Stack Works

A linked list stack uses a singly linked list where the head of the list is the top of the stack. Each element is stored in a separate node that contains the data and a pointer (or reference) to the next node.

Push always adds a new node at the head (the front of the list). Pop always removes the head node. Because we only ever touch the head, both operations are O(1) with no need to traverse the list.

Linked List Stack: head = C

C →

B →

A NULL

head points to node C (the top). Popping removes C, making B the new head.

Node Structure

Each node in the linked list contains two fields:

data: The value stored in this node. This can be any type (int, string, object, etc.).
next: A pointer to the next node in the list. The last node's next pointer is NULL (or None in Python).

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

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Push onto a Linked List Stack

Push prepends a new node to the head of the list. This is the simplest insertion operation in a linked list.

1

Create a new node with the given data.

2

Set the new node's next pointer to the current head.

3

Update the head pointer to point to the new node.

4

Increment the size counter if you track one.

void push(Node **head, int val) {
    Node *newNode = malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = *head;
    *head = newNode;
}

Pop from a Linked List Stack

Pop removes the head node and returns its data. The second node (if any) becomes the new head.

1

Check if the head is NULL. If it is, the stack is empty (underflow).

2

Store the current head's data in a temporary variable.

3

Store the current head in a temporary pointer.

4

Move the head to head->next.

5

Free the old head node and return the stored data.

int pop(Node **head) {
    if (*head == NULL) return -1;
    Node *temp = *head;
    int val = temp->data;
    *head = (*head)->next;
    free(temp);
    return val;
}

Advantages Over Arrays

No Fixed Size

A linked list stack grows and shrinks one node at a time. There is no capacity to set in advance and no overflow caused by a full array. The stack can grow as large as available memory allows.

No Resizing

Array stacks occasionally need to resize (allocate a bigger array and copy everything). Linked list stacks never resize. Every push is exactly O(1) with no amortized overhead.

Memory Efficiency for Sparse Usage

If your stack usage fluctuates wildly (sometimes empty, sometimes full), a linked list stack uses only the memory it needs. An array stack reserves its full capacity even when mostly empty.

No Copying on Growth

When a dynamic array doubles, it copies every element to the new array. For stacks holding large objects, this copying can be expensive. Linked list stacks avoid this entirely by allocating one node at a time.

Disadvantages

Extra memory for pointers. Each node stores a pointer (or reference) in addition to the data. On a 64-bit system, this adds 8 bytes per element. For a stack of integers (4 bytes each), the pointer more than doubles the per-element memory cost.

Cache misses. Nodes are allocated on the heap and may not be contiguous in memory. When you pop many elements in sequence, the CPU cannot prefetch the next node because it does not know where it is. Array stacks access contiguous memory, which is much more cache-friendly.

Allocation overhead. Each push requires a heap allocation (malloc, new, or equivalent). Heap allocation is slower than simply writing to the next array slot. In performance-critical code, this overhead matters.

Memory Layout Comparison

Understanding the memory layout helps you choose between an array stack and a linked list stack.

Array Stack

Elements are stored in a single contiguous block of memory. The OS allocates this block in one call. All elements sit next to each other, so the CPU cache can hold multiple elements at once.

Memory:
[50][30][70][_][_]
 ^top = 2
 contiguous

Linked List Stack

Each node is a separate allocation. Nodes can be anywhere on the heap. The only connection is the next pointer in each node.

Memory:
head -> [70|*] -> [30|*] -> [50|NULL]
         addr:0x100  addr:0x300  addr:0x50
         scattered on heap

Code in 5 Languages

C

#include <stdlib.h>

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

typedef struct {
    Node *top;
    int size;
} LLStack;

void init(LLStack *s) { s->top = NULL; s->size = 0; }

void push(LLStack *s, int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val;
    n->next = s->top;
    s->top = n;
    s->size++;
}

int pop(LLStack *s) {
    if (s->top == NULL) return -1;
    Node *temp = s->top;
    int val = temp->data;
    s->top = temp->next;
    free(temp);
    s->size--;
    return val;
}

C++

#include <iostream>

template <typename T>
class LLStack {
    struct Node {
        T data;
        Node *next;
        Node(T d, Node *n = nullptr) : data(d), next(n) {}
    };
    Node *head = nullptr;
    int sz = 0;
public:
    void push(T val) {
        head = new Node(val, head);
        sz++;
    }
    T pop() {
        if (!head) throw std::runtime_error("Underflow");
        Node *temp = head;
        T val = temp->data;
        head = head->next;
        delete temp;
        sz--;
        return val;
    }
    bool isEmpty() const { return head == nullptr; }
    int size() const { return sz; }
};

Java

public class LLStack<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }

    private Node top = null;
    private int size = 0;

    public void push(T val) {
        top = new Node(val);
        top.next = top;
        size++;
    }

    public T pop() {
        if (top == null) throw new RuntimeException("Underflow");
        T val = top.data;
        top = top.next;
        size--;
        return val;
    }

    public T peek() {
        if (top == null) throw new RuntimeException("Empty");
        return top.data;
    }

    public boolean isEmpty() { return top == null; }
    public int size() { return size; }
}

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedStack:
    def __init__(self):
        self.top = None
        self._size = 0

    def push(self, val):
        node = Node(val)
        node.next = self.top
        self.top = node
        self._size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("Stack underflow")
        val = self.top.data
        self.top = self.top.next
        self._size -= 1
        return val

    def peek(self):
        if self.top is None:
            raise IndexError("Stack is empty")
        return self.top.data

    def is_empty(self):
        return self.top is None

    def size(self):
        return self._size

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedStack {
    constructor() {
        this.top = null;
        this._size = 0;
    }

    push(val) {
        const node = new Node(val);
        node.next = this.top;
        this.top = node;
        this._size++;
    }

    pop() {
        if (!this.top) throw new Error("Stack underflow");
        const val = this.top.data;
        this.top = this.top.next;
        this._size--;
        return val;
    }

    peek() {
        if (!this.top) throw new Error("Stack is empty");
        return this.top.data;
    }

    isEmpty() { return this.top === null; }
    size() { return this._size; }
}

When to Choose Linked List Over Array

Use a linked list stack when the decision factors favor flexibility over raw speed.

Factor	Array Stack	Linked List Stack
Max size known?	Yes - use fixed-size	No - linked list grows freely
Cache performance	Excellent (contiguous memory)	Poor (scattered nodes)
Memory overhead	Low (data only)	Higher (data + pointer per node)
Push guarantees	Amortized O(1) if dynamic	Strictly O(1) always
Resize pauses	Yes, O(n) copy on resize	Never
Allocation per push	None (unless resizing)	One heap allocation

Rule of thumb: Default to an array stack (dynamic array). Switch to a linked list stack only if you have a specific reason, such as guaranteed O(1) push without amortization, or unpredictable growth patterns that make array resizing expensive.

Frequently Asked Questions

Can a linked list stack overflow?

Technically yes, if the system runs out of heap memory. But practically, a linked list stack will not overflow due to capacity limits the way a fixed-size array stack does. It grows as long as memory is available.

Why is push on a linked list stack O(1)?

Push prepends a new node to the head of the linked list. This requires only creating a node and updating two pointers (new node's next and the head pointer). No traversal is needed, so it is constant time.

What is the memory overhead of a linked list stack?

Each node stores the data plus a pointer to the next node. On a 64-bit system, the pointer takes 8 bytes. So for an int stack, each element uses 12 bytes (4 for int + 8 for pointer) instead of 4 bytes in an array stack. This is the trade-off for dynamic sizing.

When should I use a linked list stack over an array stack?

Use a linked list stack when you cannot predict the maximum number of elements and want to avoid resizing pauses. It is also useful when you need to frequently push and pop large batches and want guaranteed O(1) without amortized overhead.

Do high-level languages use linked list stacks internally?

Most high-level languages use dynamic arrays for their built-in stack types. Python lists, Java ArrayList-based stacks, and JavaScript arrays are all array-based. Linked list stacks are more common in systems programming and educational contexts.