Linked list ADT Python

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.

In the previous tutorial I discussed how to code a Stack Abstract Data Type using a linked list as the underlying data structure. In this tutorial I will create a Queue Abstract Data Type using a linked list. The queue will implement the two most common operations of enqueue and dequeue to add and remove an item from the queue. Although a linked list will maintain the state of the queue, the software developer will not interact with the linked list directly. The details of the algorithm and data structures used to perform dequeue and enqueue are encapsulated by the custom Python Queue Class.

Node Class for Linked List

The Node Class used in the previous linked list tutorials is the same. Each Node holds an integer value and a pointer to the next Node in the linked list.

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]

Queue Class

A queue is a First-In, First-Out [FIFO] abstract data type. The first value added to the queue will be the first value removed from the queue. My queue is implemented by a Queue Class and offers three common operations.

• enqueue - Adds new value to the Queue.
• dequeue - Retrieves and removes value from Queue.
• is_empty - Returns True if the Queue is empty, othewise False.

All these operations are performed in constant time, O[1].

Here is one solution to implementing a Queue abstract data type using Python.

class Queue[object]: def __init__[self]: self.head = None self.tail = None def enqueue[self, value: int] -> None: new_node = Node[value] if self.head is None: self.head = new_node self.tail = self.head return self.tail.next = new_node self.tail = new_node def dequeue[self] -> int: if self.head is None: raise EmptyQueueException["Dequeue from empty queue."] value = self.head.value self.head = self.head.next if self.head is None: self.tail = None return value def is_empty[self]: return self.head is None

Unlike the Stack Abstract Data Type implmentation in Python which only uses a head pointer to the linked list, the Queue implementation contains both a head and tail pointer of the linked list. By maintaining a head and tail pointer in the linked list, we are able to guarantee that enqueue and dequeue are constant time O[1] operations. The head pointer is used during the dequeue operation, and the tail pointer is used during the enqueue operation.

Custom Python Exception

I created a custom Exception Class, called EmptyQueueException, that gets raised if you attempt to dequeue from an empty queue.

class EmptyQueueException[Exception]: pass

Black Box Automated Tests

I added a Python script to test the functionality of the Queue Class. These are black box tests, since they test the interface and not the internals of the Queue Class.

if __name__ == '__main__': q = Queue[] try: q.dequeue[] except EmptyQueueException: pass max_range = 100 for i in range[max_range]: q.enqueue[i] i = 0 while not q.is_empty[]: assert q.dequeue[] == i i += 1 try: q.dequeue[] except EmptyQueueException: pass

Conclusion

As you can see, the linked list is a very handy data structure and can be used internally by both Stack and Queue Abstract Data Types. The linked list is often encapsulated by a custom class. The internal algorithm and data structures are hidden from the software developer, making it easier to refactor and completely change the internals without breaking the interface / API.

One of the hardest parts about becoming a web developer without a CS degree [aside from the obvious bits] is learning data structures and algorithms on your own.

A lot of self-taught programmers don’t realize the importance of these concepts until they already have an interview lined up, and by then it’s already too late! I was fortunate enough to attend the Code Fellows Python Development Accelerator, where a section of the curriculum was dedicated to basic data structures and algorithms. But eight whirlwind weeks were not enough to solidify these concepts, so I thought it’d be beneficial, both for my own edification and for other budding Pythonistas, to write a series on basic data structures, starting with the linked list.

In its most basic form, a linked list is a string of nodes, sort of like a string of pearls, with each node containing both data and a reference to the next node in the list [Note: This is a singly linked list. The nodes in a doubly linked list will contain references to both the next node and the previous node]. The main advantage of using a linked list over a similar data structure, like the static array, is the linked list’s dynamic memory allocation: if you don’t know the amount of data you want to store before hand, the linked list can adjust on the fly.* Of course this advantage comes at a price: dynamic memory allocation requires more space and commands slower look up times.

*In practice this means certain insertions are more expensive. For example, if the list initially allocates enough space for eight nodes, on the ninth insertion the list will have to double its allocated space to 16 and copy over the original 8 nodes, a more expensive operation than a normal insertion.

The Node

The node is where data is stored in the linked list [they remind me of those plastic Easter eggs that hold treats]. Along with the data each node also holds a pointer, which is a reference to the next node in the list. Below is a simple implementation.

class Node[object]: def __init__[self, data=None, next_node=None]: self.data = data self.next_node = next_node def get_data[self]: return self.data def get_next[self]: return self.next_node def set_next[self, new_next]: self.next_node = new_next

The node initializes with a single datum and its pointer is set to None by default [this is because the first node inserted into the list will have nothing to point at!]. We also add a few convenience methods: one that returns the stored data, another that returns the next node [the node to which the object node points], and finally a method to reset the pointer to a new node. These will come in handy when we implement the Linked List.

The Linked List

My simple implementation of a linked list includes the following methods:

• Insert: inserts a new node into the list

• Size: returns size of list

• Search: searches list for a node containing the requested data and returns that node if found, otherwise raises an error

• Delete: searches list for a node containing the requested data and removes it from list if found, otherwise raises an error

The Head of the List

The first architectural piece of the linked list is the ‘head node’, which is simply the top node in the list. When the list is first initialized it has no nodes, so the head is set to None. [Note: the linked list doesn’t necessarily require a node to initialize. The head argument will default to None if a node is not provided.]

class LinkedList[object]: def __init__[self, head=None]: self.head = head

Insert

This insert method takes data, initializes a new node with the given data, and adds it to the list. Technically you can insert a node anywhere in the list, but the simplest way to do it is to place it at the head of the list and point the new node at the old head [sort of pushing the other nodes down the line].

As for time complexity, this implementation of insert is constant O[1] [efficient!]. This is because the insert method, no matter what, will always take the same amount of time: it can only take one data point, it can only ever create one node, and the new node doesn’t need to interact with all the other nodes in the list, the inserted node will only ever interact with the head.

def insert[self, data]: new_node = Node[data] new_node.set_next[self.head] self.head = new_node

Size

The size method is very simple, it basically counts nodes until it can’t find any more, and returns how many nodes it found. The method starts at the head node, travels down the line of nodes until it reaches the end [the current will be None when it reaches the end] while keeping track of how many nodes it has seen.

The time complexity of size is O[n] because each time the method is called it will always visit every node in the list but only interact with them once, so n * 1 operations.

def size[self]: current = self.head count = 0 while current: count += 1 current = current.get_next[] return count

Search

Search is actually very similar to size, but instead of traversing the whole list of nodes it checks at each stop to see whether the current node has the requested data and if so, returns the node holding that data. If the method goes through the entire list but still hasn’t found the data, it raises a value error and notifies the user that the data is not in the list.

The time complexity of search is O[n] in the worst case [you often hear about best case / average case / worst case for Big O analysis. For this purpose of this blog post, we’ll assume worst case is the one we care about it, because it often is!]

def search[self, data]: current = self.head found = False while current and found is False: if current.get_data[] == data: found = True else: current = current.get_next[] if current is None: raise ValueError["Data not in list"] return current

Delete

You’ll be happy to know that delete is very similar to search! The delete method traverses the list in the same way that search does, but in addition to keeping track of the current node, the delete method also remembers the last node it visited. When delete finally arrives at the node it wants to delete, it simply removes that node from the chain by “leap frogging” it. By this I mean that when the delete method reaches the node it wants to delete, it looks at the last node it visited [the ‘previous’ node], and resets that previous node’s pointer so that, rather than pointing to the soon-to-be-deleted node, it will point to the next node in line. Since no nodes are pointing to the poor node that is being deleted, it is effectively removed from the list!

The time complexity for delete is also O[n], because in the worst case it will visit every node, interacting with each node a fixed number of times.

def delete[self, data]: current = self.head previous = None found = False while current and found is False: if current.get_data[] == data: found = True else: previous = current current = current.get_next[] if current is None: raise ValueError["Data not in list"] if previous is None: self.head = current.get_next[] else: previous.set_next[current.get_next[]]

That wraps up the linked list implementation! If I made a mistake please shoot me an email. At the bottom I’ve provided a link to the source code and have also added a test suite that tests all the functionality described in this blog post. Happy coding!

Ready to become a professional Python programmer? Learn more about our advanced training in Python »

Resources & Credits LinkedList Source + LinkedList Tests

Problem Solving with Algorithms and Data Structures Using Python — In addition to Code Fellows, I learned a lot about linked lists from this book. It’s very good and the above code was heavily inspired by their implementations.

This article is reposted with permission from the author. See the original post and find more resources on John’s blog.