Stack Using Linked List

Table of Contents +

When you build a stack with an array, you have to pick a size up front. Pick too small and the stack fills up and you get an overflow. Pick too big and the empty space wastes memory. So how do you get a stack that grows only as much as you need, with no fixed limit? You build it with a linked list. That is what we will do here.

📚 What We Are Building

A stack is a list where you add and remove from the same end only. The last thing you put in is the first thing you take out. We call that LIFO, which means Last In, First Out. Think of a pile of plates. You put a plate on top, and you take a plate from the top. You never pull one from the middle.

A linked list is a chain of small boxes. Each box is called a node. A node holds two things:

  • the data, which is the value you want to store
  • a next pointer, which points to the box right after it

The list does not sit in one solid block of memory. Each node sits wherever there is free space, and the next pointer is the thread that links them in order.

So a linked-list stack is just a chain of nodes where we always work at one end. That end is the top of the stack.

🎯 Why the Head Is the Top

The head is the very first node in the list. We keep a pointer called top that always points to the head.

Now here is the key idea. In a linked list, adding or removing at the head is fast. You only fix one pointer and you are done. You do not walk through the whole chain. So we make the head the top of the stack. Then both push and pop touch only the head, and both stay O(1).

Why not use the tail, the last node? To reach the tail you have to walk from the head all the way to the end every single time. That walk is O(n). The head has no such cost. So we use the head, and that head is the top of the stack.

Tip

Always do stack work at the head of the linked list. The head is reachable in one step, so push and pop never need to walk the chain.

Here is how push adds a new node at the head:

top

new node 30

20

10

null

The new node 30 becomes the head, its next points to the old head 20, and top now points to 30. The old chain is untouched.

🧱 Push: Add at the Head

Push means put a new value on top of the stack. With a linked list we make a fresh node and place it at the head.

Steps to push a value:

  1. Make a new node and put your value in its data.
  2. Point the new node’s next to the current top (the old head).
  3. Move top to the new node, so the new node is now the head.

That is the whole push. Just three pointer moves with no shifting or walking, so push is O(1).

🧹 Pop: Remove from the Head

Pop means take the top value off and return it. The top is the head, so we remove the head.

Steps to pop a value:

  1. First check if the stack is empty. If top is null, there is nothing to pop, so report underflow and stop.
  2. Read the data from the head node so you can return it.
  3. Move top to the second node (top.next), which makes it the new head.
  4. Free the old head if your language needs it (C and C++ do).

Again, only the head is touched. So pop is O(1) too.

Caution

Always check for an empty stack before you pop. If you skip that check and top is null, reading top.data crashes the program. An empty pop is called underflow.

💻 The Full Code

Below we build the linked-list stack. We define a node with data and next. We write push, pop, peek (look at the top without removing it), and isEmpty. Then a small demo pushes a few values, peeks, and pops everything so you can see the LIFO order.

stack_linked_list.py
# A node holds the data and a pointer to the next node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        # top always points to the head, which is the top of the stack
        self.top = None


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


    # Push: make a new node and place it at the head
    def push(self, value):
        node = Node(value)
        node.next = self.top   # new node points to the old head
        self.top = node        # top now points to the new node
        print(f"Pushed {value}")


    # Pop: remove the head and return its data
    def pop(self):
        if self.is_empty():
            print("Stack is empty (underflow)")
            return -1
        value = self.top.data
        self.top = self.top.next   # move top to the second node
        return value


    # Peek: look at the top without removing it
    def peek(self):
        if self.is_empty():
            print("Stack is empty")
            return -1
        return self.top.data


stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print(f"Top is {stack.peek()}")
print(f"Popped {stack.pop()}")
print(f"Popped {stack.pop()}")
print(f"Popped {stack.pop()}")
print(f"Popped {stack.pop()}")

The output of the above code will be:

Output
Pushed 10
Pushed 20
Pushed 30
Top is 30
Popped 30
Popped 20
Popped 10
Stack is empty (underflow)
Popped -1

See the order? We pushed 10, then 20, then 30. The pops came out 30, 20, 10. That is the last one in coming out first. That is LIFO working exactly as it should.

Output

Push, pop, peek, and isEmpty are all O(1). Every one of them touches only the head, so none of them ever walks the chain. The amount of work does not grow when the stack gets bigger.

⚖️ Linked List vs Array Stack

Both build a stack. The difference is in how they handle size and memory. Here is the quick comparison.

Point Linked List Stack Array Stack
Size limit No fixed limit, grows as needed Fixed size, can overflow
Memory per item Extra, each node stores a next pointer Just the value, no pointer
Push and pop O(1) at the head O(1) at the end
Memory layout Scattered nodes One solid block

So the trade is simple. The linked list never overflows because it grows with you. But each node pays a small cost in extra memory for the next pointer. The array has no pointer cost, but it has a fixed size that can fill up. Pick the linked list when you do not know how big the stack will get.

⏱️ Time and Space Complexity

Here is every operation in one place.

Operation Time Space
Push O(1) O(1)
Pop O(1) O(1)
Peek O(1) O(1)
isEmpty O(1) O(1)

The whole stack takes O(n) space to hold n items. That makes sense, since each item needs its own node.

🧩 What You’ve Learned

  • ✅ A stack follows LIFO, so the last value pushed is the first one popped.
  • ✅ A linked-list stack is a chain of nodes, where each node holds data and a next pointer.
  • ✅ The head is the top, because adding and removing at the head is O(1) and never walks the chain.
  • ✅ Push makes a new node, points it at the old head, and moves top to it.
  • ✅ Pop reads the head, moves top to the next node, and returns the old value.
  • ✅ Always check for an empty stack before popping, or you get underflow.
  • ✅ The linked-list stack has no fixed size limit, but pays a little extra memory per node for the next pointer.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In a linked-list stack, why do we keep the top at the head instead of the tail?

    Why: The head is reachable in one step, so push and pop stay O(1); reaching the tail would mean walking the whole chain.

  2. 2

    What are the steps of a push in a linked-list stack?

    Why: Push creates a node, links it to the current head, and updates top to the new node, all in O(1).

  3. 3

    What happens if you call pop on an empty linked-list stack without checking first?

    Why: With top null there is no head to read, so reading top.data crashes; this empty-pop case is called underflow.

  4. 4

    Compared to an array stack, what is the main trade-off of a linked-list stack?

    Why: The linked list grows as needed so it never overflows, but each node spends extra memory on its next pointer.

Score: 0 / 4

🚀 What’s Next?

Previous Stack Using Array Next Introduction to Queue

Share & Connect

Share on LinkedIn