How to Implement Stack Using Linked List: Simple Guide

To implement a stack using a linked list, create a linked list where the head node represents the top of the stack. Use push to add nodes at the head and pop to remove nodes from the head, following Last-In-First-Out (LIFO) order.

Syntax

A stack using a linked list typically has these parts:

• Node structure: Holds data and a pointer to the next node.
• Stack class: Maintains a reference to the top node.
• Push method: Adds a new node at the top.
• Pop method: Removes the top node and returns its data.
• Peek method: Returns the top node's data without removing it.
• IsEmpty method: Checks if the stack is empty.

python

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

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            return None
        popped = self.top.data
        self.top = self.top.next
        return popped

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

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

Example

This example shows how to create a stack, push items, pop an item, and peek at the top item.

python

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

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.top is None:
            return None
        popped = self.top.data
        self.top = self.top.next
        return popped

    def peek(self):
        if self.top is None:
            return None
        return self.top.data

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

# Using the stack
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Top item after pushes:", stack.peek())  # Should print 30
print("Popped item:", stack.pop())             # Should print 30
print("Top item after pop:", stack.peek())    # Should print 20

Output

Top item after pushes: 30
Popped item: 30
Top item after pop: 20

Common Pitfalls

Common mistakes when implementing a stack with a linked list include:

• Not updating the top pointer correctly after pop, which can cause errors or memory leaks.
• Trying to pop or peek when the stack is empty without checking, leading to errors.
• Confusing the order by adding or removing nodes from the tail instead of the head, breaking the LIFO principle.

Always add and remove nodes at the head to maintain correct stack behavior.

python

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

    # Wrong: popping from tail (inefficient and incorrect for stack)
    def pop_wrong(self):
        if self.top is None:
            return None
        current = self.top
        if current.next is None:
            popped = current.data
            self.top = None
            return popped
        while current.next.next:
            current = current.next
        popped = current.next.data
        current.next = None
        return popped

    # Correct: popping from head
    def pop_correct(self):
        if self.top is None:
            return None
        popped = self.top.data
        self.top = self.top.next
        return popped

Quick Reference

Stack using linked list quick tips:

• Push: Insert new node at the head.
• Pop: Remove node from the head.
• Peek: Return data from the head node.
• IsEmpty: Check if head is None.
• Always handle empty stack cases to avoid errors.

Key Takeaways

Implement stack with linked list by adding/removing nodes at the head for LIFO behavior.

Always check if the stack is empty before popping or peeking to avoid errors.

Push operation creates a new node and sets it as the new top.

Pop operation removes the top node and returns its data.

Avoid manipulating the tail node to maintain correct stack order and efficiency.