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.

Related Posts: