Watch Now This tutorial has a related video course created by the Real Python team. Watch it together with the written tutorial to deepen your understanding: Working With Linked Lists in Python
Linked lists are like a lesser-known cousin of lists. They’re not as popular or as cool, and you might not even remember them from your algorithms class. But in the right context, they can really shine.
In this article, you’ll learn:
- What linked lists are and when you should use them
- How to use
collections.dequefor all of your linked list needs - How to implement your own linked lists
- What the other types of linked lists are and what they can be used for
If you’re looking to brush up on your coding skills for a job interview, or if you want to learn more about Python data structures besides the usual dictionaries and lists, then you’ve come to the right place!
You can follow along with the examples in this tutorial by downloading the source code available at the link below:
Get the Source Code: Click here to get the source code you’ll use to learn about linked lists in this tutorial.
Understanding Linked Lists
Linked lists are an ordered collection of objects. So what makes them different from normal lists? Linked lists differ from lists in the way that they store elements in memory. While lists use a contiguous memory block to store references to their data, linked lists store references as part of their own elements.
Main Concepts
Before going more in depth on what linked lists are and how you can use them, you should first learn how they are structured. Each element of a linked list is called a node, and every node has two different fields:
- Data contains the value to be stored in the node.
- Next contains a reference to the next node on the list.
Here’s what a typical node looks like:
A linked list is a collection of nodes. The first node is called the head, and it’s used as the starting point for any iteration through the list. The last node must have its next reference pointing to None to determine the end of the list. Here’s how it looks:
Now that you know how a linked list is structured, you’re ready to look at some practical use cases for it.
Practical Applications
Linked lists serve a variety of purposes in the real world. They can be used to implement (spoiler alert!) queues or stacks as well as graphs. They’re also useful for much more complex tasks, such as lifecycle management for an operating system application.
Queues or Stacks
Queues and stacks differ only in the way elements are retrieved. For a queue, you use a First-In/First-Out (FIFO) approach. That means that the first element inserted in the list is the first one to be retrieved:
In the diagram above, you can see the front and rear elements of the queue. When you append new elements to the queue, they’ll go to the rear end. When you retrieve elements, they’ll be taken from the front of the queue.
For a stack, you use a Last-In/Fist-Out (LIFO) approach, meaning that the last element inserted in the list is the first to be retrieved:
In the above diagram you can see that the first element inserted on the stack (index 0) is at the bottom, and the last element inserted is at the top. Since stacks use the LIFO approach, the last element inserted (at the top) will be the first to be retrieved.
Because of the way you insert and retrieve elements from the edges of queues and stacks, linked lists are one of the most convenient ways to implement these data structures. You’ll see examples of these implementations later in the article.
Graphs
Graphs can be used to show relationships between objects or to represent different types of networks. For example, a visual representation of a graph—say a directed acyclic graph (DAG)—might look like this:
There are different ways to implement graphs like the above, but one of the most common is to use an adjacency list. An adjacency list is, in essence, a list of linked lists where each vertex of the graph is stored alongside a collection of connected vertices:
| Vertex | Linked List of Vertices |
|---|---|
| 1 | 2 → 3 → None |
| 2 | 4 → None |
| 3 | None |
| 4 | 5 → 6 → None |
| 5 | 6 → None |
| 6 | None |
In the table above, each vertex of your graph is listed in the left column. The right column contains a series of linked lists storing the other vertices connected with the corresponding vertex in the left column. This adjacency list could also be represented in code using a dict:
>>> graph = {
... 1: [2, 3, None],
... 2: [4, None],
... 3: [None],
... 4: [5, 6, None],
... 5: [6, None],
... 6: [None]
... }
The keys of this dictionary are the source vertices, and the value for each key is a list. This list is usually implemented as a linked list.
Note: In the above example you could avoid storing the None values, but we’ve retained them here for clarity and consistency with later examples.
In terms of both speed and memory, implementing graphs using adjacency lists is very efficient in comparison with, for example, an adjacency matrix. That’s why linked lists are so useful for graph implementation.
Performance Comparison: Lists vs Linked Lists
In most programming languages, there are clear differences in the way linked lists and arrays are stored in memory. In Python, however, lists are dynamic arrays. That means that the memory usage of both lists and linked lists is very similar.
Further reading: Python’s implementation of dynamic arrays is quite interesting and definitely worth reading about. Make sure to have a look and use that knowledge to stand out at your next company party!
Since the difference in memory usage between lists and linked lists is so insignificant, it’s better if you focus on their performance differences when it comes to time complexity.
Insertion and Deletion of Elements
In Python, you can insert elements into a list using .insert() or .append(). For removing elements from a list, you can use their counterparts: .remove() and .pop().
The main difference between these methods is that you use .insert() and .remove() to insert or remove elements at a specific position in a list, but you use .append() and .pop() only to insert or remove elements at the end of a list.
Now, something you need to know about Python lists is that inserting or removing elements that are not at the end of the list requires some element shifting in the background, making the operation more complex in terms of time spent. You can read the article mentioned above on how lists are implemented in Python to better understand how the implementation of .insert(), .remove(), .append() and .pop() affects their performance.
With all this in mind, even though inserting elements at the end of a list using .append() or .insert() will have constant time, O(1), when you try inserting an element closer to or at the beginning of the list, the average time complexity will grow along with the size of the list: O(n).
Linked lists, on the other hand, are much more straightforward when it comes to insertion and deletion of elements at the beginning or end of a list, where their time complexity is always constant: O(1).
For this reason, linked lists have a performance advantage over normal lists when implementing a queue (FIFO), in which elements are continuously inserted and removed at the beginning of the list. But they perform similarly to a list when implementing a stack (LIFO), in which elements are inserted and removed at the end of the list.
Retrieval of Elements
When it comes to element lookup, lists perform much better than linked lists. When you know which element you want to access, lists can perform this operation in O(1) time. Trying to do the same with a linked list would take O(n) because you need to traverse the whole list to find the element.
When searching for a specific element, however, both lists and linked lists perform very similarly, with a time complexity of O(n). In both cases, you need to iterate through the entire list to find the element you’re looking for.
Introducing collections.deque
In Python, there’s a specific object in the collections module that you can use for linked lists called deque (pronounced “deck”), which stands for double-ended queue.
collections.deque uses an implementation of a linked list in which you can access, insert, or remove elements from the beginning or end of a list with constant O(1) performance.
How to Use collections.deque
There are quite a few methods that come, by default, with a deque object. However, in this article you’ll only touch on a few of them, mostly for adding or removing elements.
First, you need to create a linked list. You can use the following piece of code to do that with deque:
>>> from collections import deque
>>> deque()
deque([])
The code above will create an empty linked list. If you want to populate it at creation, then you can give it an iterable as input:
>>> deque(['a','b','c'])
deque(['a', 'b', 'c'])
>>> deque('abc')
deque(['a', 'b', 'c'])
>>> deque([{'data': 'a'}, {'data': 'b'}])
deque([{'data': 'a'}, {'data': 'b'}])
When initializing a deque object, you can pass any iterable as an input, such as a string (also an iterable) or a list of objects.
Now that you know how to create a deque object, you can interact with it by adding or removing elements. You can create an abcde linked list and add a new element f like this:
>>> llist = deque("abcde")
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
>>> llist.append("f")
>>> llist
deque(['a', 'b', 'c', 'd', 'e', 'f'])
>>> llist.pop()
'f'
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
Both append() and pop() add or remove elements from the right side of the linked list. However, you can also use deque to quickly add or remove elements from the left side, or head, of the list:
>>> llist.appendleft("z")
>>> llist
deque(['z', 'a', 'b', 'c', 'd', 'e'])
>>> llist.popleft()
'z'
>>> llist
deque(['a', 'b', 'c', 'd', 'e'])
Adding or removing elements from both ends of the list is pretty straightforward using the deque object. Now you’re ready to learn how to use collections.deque to implement a queue or a stack.
How to Implement Queues and Stacks
As you learned above, the main difference between a queue and a stack is the way you retrieve elements from each. Next, you’ll find out how to use collections.deque to implement both data structures.
Queues
With queues, you want to add values to a list (enqueue), and when the timing is right, you want to remove the element that has been on the list the longest (dequeue). For example, imagine a queue at a trendy and fully booked restaurant. If you were trying to implement a fair system for seating guests, then you’d start by creating a queue and adding people as they arrive:
>>> from collections import deque
>>> queue = deque()
>>> queue
deque([])
>>> queue.append("Mary")
>>> queue.append("John")
>>> queue.append("Susan")
>>> queue
deque(['Mary', 'John', 'Susan'])
Now you have Mary, John, and Susan in the queue. Remember that since queues are FIFO, the first person who got into the queue should be the first to get out.
Now imagine some time goes by and a few tables become available. At this stage, you want to remove people from the queue in the correct order. This is how you would do that:
>>> queue.popleft()
'Mary'
>>> queue
deque(['John', 'Susan'])
>>> queue.popleft()
'John'
>>> queue
deque(['Susan'])
Every time you call popleft(), you remove the head element from the linked list, mimicking a real-life queue.
Stacks
What if you wanted to create a stack instead? Well, the idea is more or less the same as with the queue. The only difference is that the stack uses the LIFO approach, meaning that the last element to be inserted in the stack should be the first to be removed.
Imagine you’re creating a web browser’s history functionality in which store every page a user visits so they can go back in time easily. Assume these are the actions a random user takes on their browser:
- Visits Real Python’s website
- Navigates to Pandas: How to Read and Write Files
- Clicks on a link for Reading and Writing CSV Files in Python
If you’d like to map this behavior into a stack, then you could do something like this:
>>> from collections import deque
>>> history = deque()
>>> history.appendleft("https://realpython.com/")
>>> history