← Back to Data Structures and Algorithms in Python

In this source code example, we will write a code to implement the Stack data structure using the Linked List data structure in Python.

The singly linked list is a linear data structure in which each element of the list contains a pointer that points to the next element in the list. Each element in the singly linked list is called a node. Each node has two components: data and a pointer next which points to the next node in the list.

Stack Implementation Using Linked List in Python

""" A Stack using a linked list like structure """
from __future__ import annotations

from collections.abc import Iterator
from typing import Generic, TypeVar

T = TypeVar("T")

class Node(Generic[T]):
    def __init__(self, data: T):
        self.data = data
        self.next: Node[T] | None = None

    def __str__(self) -> str:
        return f"{self.data}"


class LinkedStack(Generic[T]):

    def __init__(self) -> None:
        self.top: Node[T] | None = None

    def __iter__(self) -> Iterator[T]:
        node = self.top
        while node:
            yield node.data
            node = node.next

    def __str__(self) -> str:
        return "->".join([str(item) for item in self])

    def __len__(self) -> int:
        return len(tuple(iter(self)))

    def is_empty(self) -> bool:
        return self.top is None

    def push(self, item: T) -> None:
        node = Node(item)
        if not self.is_empty():
            node.next = self.top
        self.top = node

    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        assert isinstance(self.top, Node)
        pop_node = self.top
        self.top = self.top.next
        return pop_node.data

    def peek(self) -> T:
        if self.is_empty():
            raise IndexError("peek from empty stack")

        assert self.top is not None
        return self.top.data

    def clear(self) -> None:
        self.top = None


if __name__ == "__main__":
        
        stack = LinkedStack()
        stack.push("a")
        stack.push("b")
        stack.push("c")
        stack.push("d")
        stack.push("e")
        print(str(stack))
        print(len(stack))
        print(stack.is_empty())
        print(stack.pop())
        print(str(stack))
        print(stack.peek())
        print(stack.clear())

Output:

e->d->c->b->a
5
False
e
d->c->b->a
d
None

Push Operation

In a push operation, we add an element/node to the top of the stack.

    def push(self, item: T) -> None:
        node = Node(item)
        if not self.is_empty():
            node.next = self.top
        self.top = node

Pop Operation

Remove the top element/node from the stack

    def pop(self) -> T:
        if self.is_empty():
            raise IndexError("pop from empty stack")
        assert isinstance(self.top, Node)
        pop_node = self.top
        self.top = self.top.next
        return pop_node.data