Data Structures with Python — Linked Lists (Theory)

A quick overview of the operations with the linked lists

In this article, we will continue with our series on Computer Science and discuss the first data structure. To make things easier, we will separate theory and practical implementation into two parts. So, let’s start by understanding the basics of linked lists — one of the most important data structures.

I strongly recommend that you pay attention to the first article in the series, which explains the concept of Big O. This concept will be useful for better understanding throughout the series as it helps with data structures and algorithms. You can find the first part by following the link below.

Computer Science with Python — Time Complexity and Big O

What is a linked list and what is the difference to Python lists?

If you work with Python, it’s essential to know about the built-in list data structure. In other programming languages, a similar thing appears in the form of an array. Let me briefly explain some details about lists in Python.

You can use indexes to access elements in the list. For example, to get the first element in the list, you can use the [0] index. Lists are mutable, which means that you can add items, remove them, and perform other similar operations. There are many methods, which are used specifically for lists, like append(), remove(), sort(), and many others.

• You can use indexes to access elements in the list. So, if you want to get the first element in the list, you can use my_list[0] format.
• Lists are changeable, which means that you can add items, remove them, and perform other similar operations.
• There are many methods, which are used specifically for lists, like append, sort, pop, and many others.

So, it seems that lists are a good way to store multiple variables in the same place. However, the fundamental principle in computer science is that no data structure is suitable for every task. In other words, there might be situations, when performance with an array will be unsuitable for the task.

And here comes another data structure with similar characteristics — linked list. What is the difference for the linked list?

• First of all, we don’t have any indexes in the linked lists, so accessing data from it might be more difficult.
• The second difference is the place in memory reserved for each element. For the list, we have a continuous appearance in memory, while linked lists are spread all over the memory.
• But what is more important, the elements are connected with pointers. So, you can access the next element when the current element is in use.

The difference between a Python list (in this picture array) and a linked list. Source.

The linked list data structure consists of a head node, which is the first node in the structure, a tail node, which is the last one, and other data nodes in between. Every node points to the next one until the tail is reached.

What is the node?

In linked lists, each element is referred to as a node. The node carries a value and a pointer to the next node. All nodes, except the last one, have this pointer (which is None). This approach is crucial for this data structure. Below is a simple way to create a linked list in Python.

head = {
    "value": 12,
    "next": {
        "value": 16,
        "next": {
            "value": 21,
            next: None
        }
    }
}

print(head["next"]["value"])
# 16

Basic operations with the linked lists

Big O

In this particular data structure, we will be utilizing some methods that are widely used for such objects. It is important to understand the performance of each of these data structures. For this purpose, we will be using the Big O notation which we are already familiar with. Also, I will cover all these operations below.

• Append node to the tail — O(1)
• Remove the last node — O(n)
• Prepend, or change the head of the linked list — O(1)
• Remove the first node, or change the head to the second element — O(1)
• Insert, or add a node in the middle of the list — O(n)
• Delete, or removing a node from the middle of the list — O(n)

Operations with the tail

Appending a new node to the tail of a linked list is the easiest operation and takes the minimum amount of time, which is O(1). To do this, we create a new node in memory and a pointer from the tail node to the new node.

However, removing the last node in the linked list is a more difficult operation. We need to change the pointer of the previous node to None as it cannot point to a deleted node. Since we can’t simply access the previous node, we must iterate through each element in the linked list from the head to this particular node. This interaction always takes the same amount of time, which is O(n).

Appending to the end of the linked list. Source.

Operations with the head

To add a new node to the start of a linked list, all you have to do is change the head of the list. This is a simple operation that always requires minimal steps and is O(1) in computation.

Similarly, removing the first node in the list is also a straightforward process. To achieve this, we simply change the head of the list to the second node and remove the first element. This operation is also O(1) in computation and can be used to delete multiple nodes at once.

Change the head of the list. Source.

Operations in the middle of the list

To add a node in the middle of a linked list, follow these steps:

1. Create a new node with the data and point it to the following node (E->C).
2. Iterate to the previous node, which now has two points to it (B).
3. Change the pointer for this node to the newly created node (B->E).

As you can see, this process involves iteration, which means that the time complexity will be O(n).

To remove a node from the middle of the linked list, follow the same steps in the opposite direction. This means that you need to iterate to the required nodes and change the pointer to the following node (B->C). Once you have done this, you can safely remove the old data (E).

Adding node in the middle. Source

Lookup operations

When working with a linked list data structure, we often need to access specific points within it. This can be done either by searching for a node by its value or by its index. However, since linked lists do not have indices, we must iterate through the list until we find the desired data. As a result, the time complexity for this operation will always be O(n).

Lookup for a node by value. Source

Below is the final comparison between linked lists and built-in Python lists. As per the analysis, certain operations, particularly those involving the beginning of the list, are faster when executed with linked lists. However, when it comes to accessing specific elements, arrays are much faster since they have indexes.

There are some use cases when we come to the linked lists, let’s just take a look at some examples.

• Pages in your web browser — when using the Next and the Previous buttons. It’s pretty intuitive, that the system works similarly to the linked lists.
• Music player — the same pattern when you want to skip to the next track or come back to the previous one.
• Essentially, file systems have a part of functionality from the linked lists, as folders and files have some hierarchy.

Conclusions

This section provided you with the theoretical information you need to understand how linked lists work. In the upcoming article, I will concentrate on the practical implementation of linked lists in Python. Before then, I suggest that you become familiar with all the operations associated with linked lists.

Linked lists are just one of many data structures that you can use to organize your data. In subsequent articles, we will explore other ways to organize data.

I can be found on LinkedIn and I am looking forward to connecting with you. Let’s engage in discussions about the intricate world of data science and data engineering.