An empty linked list consists of

Photo by Patrick Tomasso on Unsplash

Hi everyone, in this article, we will talk about simple linked lists, one of the most commonly used data structures. Firstly, we will see what a linked list is, how the data is stored, the advantages and drawbacks of using it. After that, we will see the main operations in a linked list and we will implement them in Python. So, lets start.

Why use a Linked List

The most common way to store a bunch of data in a single variable is using an array. However, arrays in most programming languages and in theory generally have a drawback, they are static data structures. That means the programmer must pre-define their size in advance and that size cannot be changed after the declaration. As a result, in most cases, we spend a lot of space in memory we actually dont use. Moreover, in some cases, we want a sorted array with data, so the insertion or the deletion of an element will be expensive in time to keep the array sorted. If we want for example to add a new element that must be placed in the first position of the array, all the other elements on the array must be moved one position further to the right. Similarly, if we want to delete the first element of an array, all the other elements must be moved one position further to the left. These operations may not be visible in a small amount of data, but in cases, we have an array with thousands or millions of elements the time complexity of the algorithm will be increased dramatically.

What is a Linked List

To solve the problems above, we use a linked list instead of an array. A linked list is a dynamic data structure, meaning that we dont need to pre-define its size (maximum number of elements). Also, operations like the insertion or the deletion of a node have better time complexity. A linked list consists of a number of nodes. In the general case, every node consists of two parts, the data part and the link to the next node of the list. A linked list is represented as a pointer to the first node of the list called head. If the linked list has no nodes, the head pointer has a null (None for the Python) value. The last node of the linked list has a pointer with a null value meaning that has no connection with a node. The node and the linked list have the following structure.

A simple Linked List representation

Create a Linked List in Python

To create a linked list in Python we define a class called Node that represents each of the nodes of the linked list and a class called LinkedList that represents the linked list itself. Lets see the code below:

As we can see in the code above, each node has a value and the next attribute is initialized in None. On the other hand, the LinkedList class has only the head attribute that is also initialized in None, so we have an empty linked list.

Operations in Linked List

We have a branch of operations in linked lists that helps us to add, delete, update or find elements in a list. The most important of them are the following:

• Check if a Linked List is empty
• Traversal of a Linked List
• Add node to a Linked List
• Return a node of a Linked List
• Check if a node exists in a Linked List
• Remove a node from a Linked List

Check if a Linked List is empty

To check if a linked list is empty or not, we just check the value of the head of the linked list to see if it has a None value (empty list) or a connection with a node. In Python, the None value has a Boolean value of False. See the code below:

Check if a Linked List is empty in Python

Traversal of a Linked List

Traversing is one of the most commonly used operations in linked lists. Traversing in linked lists means visiting every node of it. As we will see in the next lines, we use this method for various reasons like to print the nodes of a list, to find a particular node, etc. To do that, we use a while loop. In the following example, we traverse the linked list in __str__(self) under method to print all the nodes of a linked list.

Traverse a simple Linked List

Add node to a Linked List

We have a couple of ways to add a new node in a linked list. We can add it in the front of the linked list as the first node, to the back as the last node, or even to the middle of the linked list before or after a particular node.

• Add to front

Suppose we want to add a new node at the beginning of the linked list. First, we must check if the linked list is empty (head is None) or not, so we execute the following steps.

Add a new node to the front of the Linked List

Now lets see the code in Python

• Add to back

Suppose we want to add a new node at the end of the Linked List. Lets see the steps below:

Add a new node to the end of the Linked List

Now, lets implement it in Python.

• Add before a particular node

Suppose now we have a linked list with some nodes and we want to add a new node before a particular node (target node). Lets see the steps below:

Add a new node before a particular node in a Liked List

Feel free to try to implement the add_after_node() function which adds a new node after a particular node. I have an implementation in my Github account to check my solution.

Return a node of the Linked List

• Return the first node of the linked list

Suppose now we have a linked list and we want to get the value of the first node. To do that, we must check if the linked list is empty or not. After that, if there is at least one node, we return the first node of that list.

• Return the last node of the Linked List

Similarly, we can have access to the last element of a linked list. To do that, we need to traverse all the nodes of our linked list until the final node. Then we can return the value of that node. In this case, simple linked lists are not so good as far as time complexity, as we have to loop through all the nodes from start to end. However, we can solve this problem using a tail node. A tail node is a pointer, like the head, which is linked with the last node of the linked list, so we have a pointer for the last node and we can get its data in one step.

Structure of a Linked List with tail

Let's see the implementation of them in the code below:

Check if a node exists in the Linked List

One of the most common operations in linked lists is to check if a particular value (node) exists in the linked list. To do that, we need to traverse the list from start until to find the node with the desired value. As you can guess, the time complexity depends on the size of the linked list and the position of the desired node. Lets see an example below:

Remove a node from the Linked List

• Remove the first node

Lets assume that we have a non-empty linked list and we want to remove the first element. To do that, we need to change the head so that to be linked with the node with which the first node is connected (second node). Lets see the image below:

As we can see, we dont really delete the first node but, we lose its reference. After that point, there is no way to have access to that node anymore thus Python garbage collector will delete that node from the memory.

• Remove the last node

In the previous example, we deleted the first node of a linked list. Similarly, we can delete the data structure until the second to last node. After that, we simply change the connection of that node (which has the reference for the last node) to None, so we lose that reference, and the node will be deleted. As we mentioned earlier, this operation would be much more efficient if we use and a tail pointer.

• Remove a node based on a key

Another very commonly used operation in linked lists is the removal of a node based on a key. In this case, we loop through the nodes of the linked list to find the node with the desired key. Simultaneously, we keep track of the previous of the desired node. After that, link the previous node with the node with which desired node is connected.

Lets see an example below:

The Deque object in Python

In Python, there is the deque object (double ended queue) to easily implement a linked list. With deque, we can easily insert, delete or access nodes from the beginning or from the end of our list in constant time O(1).

Create a list with deque

To create a linked list with deque, first, we need to import it from module collections. After that, to create a linked list we use the deque() constructor with an iterable like list, tuple, dictionary, etc as a parameter.

Add / remove elements with deque

After the creation of the linked list, we can add or remove elements (nodes) using the methods append(element) and pop(). These methods are used to add and remove nodes from the end of the linked list. Also, we can add or remove elements from the beginning of the linked list using the methods appendleft(element) and popleft().

Conclusion

In this article, we discussed simple linked lists data structure. Linked lists are very useful not only for the reasons we talked about earlier in this article but also because we can implement other data structures like queues and stacks. In the future, we will have the opportunity to analyze in more detail other types of linked lists like circular linked lists, doubly linked lists, etc. Until then, keep learning and keep coding. Thanks for reading.