← 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