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.

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):

def push(self, value: int) -> None:

def pop(self) -> int:
raise EmptyStackException("Pop from empty stack.")

return value

def peek(self) -> int:
raise EmptyStackException("Peek from empty stack.")

def is_empty(self) -> bool:

## 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.