Stack Implementation Using Linked List: Algorithm, Code, and Examples

TL;DR: A stack implemented using linked list uses nodes, each with a data field and a pointer to the next node in the stack. The top of the stack is the linked list head. Both push and pop operations occur at the head of the list, resulting in O(1) operations. Unlike an array-based stack, a linked list implementation has no defined capacity.

A stack is a simple Last-In-First-Out (LIFO) data structure that can be implemented using arrays or linked lists. The array-based implementation is simple but has the disadvantage of a fixed size. In contrast, the linked list implementation allows dynamic resizing because it deallocates nodes as elements are removed from the stack. This article describes the linked list implementation of a stack data structure. The discussion covers the push, pop, and peek operations, including pseudocode, implementations in various programming languages, time and space complexity, and a comparison to the array-based implementation.

The article discusses implementing a stack using a linked list. A linked-list stack is efficient and has no predefined size limit. The stack can grow and shrink at runtime depending on the number of elements. The push and pop operations are done at the head of the linked list, which makes them O(1) operations. The article provides pseudocode for push, pop, and peek operations and compares the efficiency of the linked-list implementation with the array implementation. The article also provides implementations of the operations in C, C++, Java, and Python.

Want a Top Software Development Job? Start Here!AI-Powered Full Stack Developer ProgramExplore Program

What Is Stack Implementation Using Linked List?

In a linked-list-based stack, each element is stored in a node containing a data field and a pointer to the next node. Instead of maintaining a separate array index, the stack keeps a single pointer, usually called top, that always points to the most recently added node; the head of the linked list.

• Insertion (push) always happens at the head, so the new node becomes the new top.
• Deletion (pop) always happens at the head, so the top moves to the next node and frees the old head.
• The last node in the list has its next pointer set to NULL, marking the bottom of the stack.
• Overflow in a linked-list stack isn't a fixed-capacity limit like in an array; it occurs only when there isn't enough heap memory to allocate a new node.
• Underflow occurs when a pop or peek is attempted on an empty stack, that is, when top is NULL.

Because both push and pop operate on the head of the list, neither operation ever needs to shift or scan through other elements, which is why a linked-list stack keeps every operation at O(1).

Why Use a Linked List Instead of an Array for a Stack?

An array-based stack has to reserve its size in advance. Once it's full, pushing another element means allocating a larger array and copying every existing element into it, an O(n) operation. A linked-list-based stack avoids this entirely by allocating one node per push and freeing one node per pop, so it only ever uses exactly as much memory as it currently needs.

Because a linked-list stack allocates memory as it goes, it is inherently a dynamic stack implementation. There's no upper bound decided in advance, and no resize-and-copy step ever needed, unlike a dynamic array that still has to reallocate periodically behind the scenes.

Here's How to Land a Top Software Developer JobAI-Powered Full Stack Developer ProgramExplore Program

Stack Operations Using Linked List: Algorithm and Pseudocode

Push (insert at top):

push(value):
    create newNode
    newNode.data = value
    if top is NULL:
        newNode.next = NULL
    else:
        newNode.next = top
    top = newNode

Pop (remove from top):

pop():
    if top is NULL:
        report underflow
        return
    temp = top
    value = temp.data
    top = top.next
    free(temp)
    return value

Peek (view the top element without removing it):

peek():
    if top is NULL:
        report empty stack
        return
    return top.data

isEmpty (check whether the stack has any elements):

isEmpty():
    return top == NULL

Stack Implementation Using Linked List in C

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

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

struct Node* top = NULL;

int isEmpty() {
    return top == NULL;
}

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Stack Overflow: not enough heap memory.\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
    printf("%d pushed onto the stack.\n", value);
}

int pop() {
    if (isEmpty()) {
        printf("Stack Underflow: stack is empty.\n");
        return -1;
    }
    struct Node* temp = top;
    int poppedValue = temp->data;
    top = top->next;
    free(temp);
    return poppedValue;
}

int peek() {
    if (isEmpty()) {
        printf("Stack is empty.\n");
        return -1;
    }
    return top->data;
}

void display() {
    struct Node* temp = top;
    printf("Stack (top to bottom): ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    display();
    printf("Top element is %d\n", peek());
    printf("Popped element: %d\n", pop());
    display();
    return 0;
}

Sample output:

10 pushed onto the stack.
20 pushed onto the stack.
30 pushed onto the stack.
Stack (top to bottom): 30 20 10
Top element is 30
Popped element: 30
Stack (top to bottom): 20 10

Stack Implementation Using Linked List in C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = nullptr;
    }

    bool isEmpty() {
        return top == nullptr;
    }

    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
        cout << value << " pushed onto the stack." << endl;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow: stack is empty." << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty." << endl;
            return -1;
        }
        return top->data;
    }

    void display() {
        Node* temp = top;
        cout << "Stack (top to bottom): ";
        while (temp != nullptr) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.display();
    cout << "Top element is " << s.peek() << endl;
    cout << "Popped element: " << s.pop() << endl;
    s.display();
    return 0;
}

Learn 45+ in-demand full-stack development skills and tools, including Frontend Development, Backend Development, Version Control and Collaboration, Database Management, and AI-Assisted Development, with our Full Stack Developer Course.

Stack Implementation Using Linked List in Java

public class StackLinkedList {

    private Node top;

    private class Node {
        int data;
        Node next;

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

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

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
        System.out.println(value + " pushed onto the stack.");
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow: stack is empty.");
            return -1;
        }
        int poppedValue = top.data;
        top = top.next;
        return poppedValue;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return top.data;
    }

    public void display() {
        Node temp = top;
        System.out.print("Stack (top to bottom): ");
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        StackLinkedList stack = new StackLinkedList();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.display();
        System.out.println("Top element is " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        stack.display();
    }
}

Dive Deep Into Java Core ConceptsJava Certification TrainingENROLL NOW

Stack Implementation Using Linked List in Python

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


class Stack:
    def __init__(self):
        self.top = None

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

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        print(f"{value} pushed onto the stack.")

    def pop(self):
        if self.is_empty():
            print("Stack Underflow: stack is empty.")
            return None
        popped_value = self.top.data
        self.top = self.top.next
        return popped_value

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

    def display(self):
        temp = self.top
        elements = []
        while temp is not None:
            elements.append(temp.data)
            temp = temp.next
        print("Stack (top to bottom):", elements)


if __name__ == "__main__":
    stack = Stack()
    stack.push(10)
    stack.push(20)
    stack.push(30)
    stack.display()
    print("Top element is", stack.peek())
    print("Popped element:", stack.pop())
    stack.display()

All four implementations follow the same underlying algorithm shown in the pseudocode above; only the syntax for structs/classes, memory management, and printing changes between languages.

Deep Dive Into Core Python ConceptsWith the Python Certification CourseENROLL NOW

Time and Space Complexity of Stack Using Linked List

Space complexity is O(n) for n elements, since each element requires its own node plus one extra pointer (next) beyond the data itself. This pointer is the main memory overhead compared to an array-based stack, which stores only the raw data with no per-element pointer cost.

Advantages of Stack Using Linked List

• Grows and shrinks dynamically at runtime; no fixed size is decided in advance.
• Push and pop are O(1) worst-case on every call, with no occasional resize-and-copy cost like a dynamic array.
• No memory is wasted on unused, pre-allocated capacity, since each node is allocated only when needed and freed immediately after it is popped.
• Insertion and deletion never require shifting other elements, unlike an array-based stack.

Disadvantages of Stack Using Linked List

• Each node uses extra memory for its pointer, in addition to the actual data.
• No random access; reaching any element other than the top requires traversing from the top, which is O(n).
• Reverse traversal isn't possible with a singly linked list alone; it would require a doubly linked list and the extra memory it requires.
• Slightly worse cache performance than an array-based stack, since nodes are scattered across the heap instead of sitting in contiguous memory.

Get the Coding Skills You Need to SucceedAI-Powered Full Stack Developer ProgramExplore Program

Applications of Stack Using Linked List

• Expression evaluation and conversion: Parsing and evaluating infix, postfix, and prefix expressions, where the stack size needed isn't known ahead of time.
• Function call management: Modeling call stacks and recursion, where the depth of nested calls can vary and isn't fixed in advance.
• Undo/redo functionality: Where the number of undoable actions is unbounded and shouldn't be capped by a fixed array size.
• Backtracking algorithms: Such as maze solving or parsing, where the stack can grow arbitrarily deep depending on the input.
• Browser history and back-navigation: Where entries are added and removed dynamically without a predetermined limit.

The step-by-step Software Engineer Roadmap is designed for professionals seeking to understand the full scope of the profession. Explore the skills, tools, salary potential, and career roadmap needed to build a successful career as a software engineer.

Conclusion

A linked-list stack solves the one real limitation of an array-based stack: a fixed, pre-decided size. By allocating one node per push and freeing it on pop, the stack grows and shrinks exactly as needed, with every push, pop, and peek running in constant time. The trade-off is the extra pointer memory per node and the loss of random access and cache-friendly contiguous storage that arrays offer. Once you're comfortable with this implementation, the same head-insertion, head-deletion pattern extends naturally to a linked-list-based queue implementation.

Understanding data structures such as stacks and linked lists is an important step toward becoming a stronger developer. If you want to apply these programming concepts through hands-on projects, explore Simplilearn’s Full Stack Developer Course, which covers frontend, backend, databases, and other essential development skills. You can also explore Simplilearn’s Software Development courses to build broader programming and software engineering skills for real-world development

Key Takeaways

• A linked-list-based stack keeps a single top pointer at the head of the list; push and pop both act on the head.
• Push, pop, peek, and isEmpty are all O(1) worst-case; only traversal/display is O(n).
• Space complexity is O(n), with one extra pointer of overhead per node compared to an array-based stack.
• Unlike an array-based stack, a linked-list stack is inherently dynamic and never needs a resize-and-copy step.
• The trade-off for that flexibility is per-node pointer overhead, no random access, and weaker cache locality.

FAQ

1. Can a stack be implemented using a singly linked list?

Yes, and it's the standard approach. Since push and pop only ever touch the head of the list, a singly linked list (with just a next pointer) is enough; a doubly linked list is not needed unless you also need to traverse the stack in reverse.

2. What causes stack overflow in a linked-list implementation?

Unlike an array-based stack, there's no fixed capacity to exceed. Overflow only happens if the program's heap runs out of memory for a new node, which in practice means the stack has grown extremely large or the system is already low on available memory.

3. How is memory allocated in a stack using a linked list?

Each push allocates one new node on the heap (malloc in C, new in C++/Java, or Python's object allocator) when needed. Each pop frees that node immediately, so total memory use tracks the stack's current size rather than a size decided upfront.

4. Which is better, a stack using an array or a linked list?

Neither is universally better. An array-based stack is faster and more cache-friendly when you know the maximum size in advance. A linked-list-based stack is better when the size is unpredictable or can grow very large, since it avoids resizing and doesn't waste memory on unused capacity.