In recent tutorials I have been discussing linked lists. Linked lists are a fundamental data structure in computer science and a popular topic in technical interviews and programming challenges. In the first tutorial I discussed using linear search to find a value in a linked list, and in the second tutorial I discussed inserting a new node in a linked list.
In this tutorial I will create a Stack
class and use a linked list as the underlying data structure for maintaining state. This is a bit different than the other tutorials in that I am encapculating the linked list and hiding the underlying implementation from the user of the Stack
Class. The Stack
Class will implement common Stack operations (e.g. push, pop, and peek) using a singly linked list, but the developer using the class will not interact with the linked list directly.
Linked List Node Class
I will continue to use the Node
Class mentioned in the previous tutorials. Each Node
instance will contain a value and a pointer to the next Node
instance in the linked list. To simplify things, I am storing integers in each Node
, but a linked list can store any type of data.
class Node(object): def __init__(self, value: int, next_node: "Node" = None): self.value = value self.next = next_node def __repr__(self): return "Node <{}>".format(self.value)
Stack Class
A stack is a Last-In, First-Out (LIFO) abstract data type. The last value added to the stack will be the first value removed from the stack. My stack is implemented by a Stack
Class and offers four common operations.
- push - Adds new value to the Stack.
- pop - Retrieves and removes value from Stack.
- peek - Retrieves, but does not remove, value from Stack.
- is_empty - Returns True if Stack empty, othewise False.
All these operations are performed in constant time, O(1), by pushing and popping values from the head of the linked list.
Here is one solution to implementing a Stack abstract data type using Python.
class Stack(object): def __init__(self): self.head = None def push(self, value: int) -> None: self.head = Node(value, self.head) def pop(self) -> int: if self.head is None: raise EmptyStackException("Pop from empty stack.") value = self.head.value self.head = self.head.next return value def peek(self) -> int: if self.head is None: raise EmptyStackException("Peek from empty stack.") return self.head.value def is_empty(self) -> bool: return self.head is None
Custom Python Exception Class
I created a custom Exception
Class, called EmptyStackException
, that gets raised if you attempt to peek or pop from an empty stack.
class EmptyStackException(Exception): pass
Automated Tests
I added some code to test the Stack
Class to make sure it works. In production, one should use doctest or unittest as a more formal way to write the tests.
if __name__ == '__main__': s = Stack() try: s.peek() except EmptyStackException: pass max_range = 100 for i in range(max_range): s.push(i) i = max_range while not s.is_empty(): i -= 1 print(s.peek()) assert s.pop() == i try: s.pop() except EmptyStackException: pass
Conclusion
I hope you're enjoying this series on linked lists and the topics of computer science, algorithms, and data structures in my tutorials. Since we just coded a Stack abstract data structure in Python using a linked list, we should probably look at coding a Queue abstract data structure using a linked list in Python next.
Posted by David Hayden
David Hayden is a freelance web developer. In his spare time he tutors students on a wide variety of computer science topics and programming languages. You can find him on twitter as @koderdojo.