← 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 annotationsfrom collections.abc import Iteratorfrom typing import Generic, TypeVarT = 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 = Noneif __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->a5Falseed->c->b->adNone

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