However, they are very useful. By storying values and pointers next to each other in nodes, linked lists have characteristics similar to Python dictionaries.
This tutorial will teach you everything you need to know about linked lists in Python. We’ll cover the fundamentals of linked lists, how to visualize this unique data structure, and several examples of how to create linked lists using Python code.
Table of Contents
You can skip to a specific section of this Python linked lists tutorial using the table of contents below:
A linked list is a way of storing values or elements, which is also known as a data structure. Unlike in arrays or lists where elements are stored next to each other, linked lists hold the value and a pointer to the next node in its structure. In order to visualize this better, consider the following figure.
The above is a simple way to visualize a linked list. It is also called a singly linked list and can only be iterated in one direction. It has three nodes with the values 12, 99, and 37. Each node also has a pointer referring to each succeeding element. The first node is called the head and it is where iterations through the linked list have to be started. As the last node has no succeeding node, it points to null.
In practice, linked lists can be used as a foundation to implement other data structures such as lists/arrays, stacks, and queues. They also can be implemented without the foundation of linked lists but it is a common practice to do so.
Now let us look into the fundamentals of linked lists.
Fundamentals of Linked Lists
From a more technical standpoint, a linked list can be called a linear data structure that consists of a collection of nodes. In its most fundamental form, a node has its data element and a pointer to the subsequent node in the linear collection. The way linked lists are stored in the memory are not governed by their physical placement and therefore, elements can be inserted or deleted efficiently from anywhere in the sequence.
The above is how a node looks. A node always has its data and pointer values. In more advanced linked lists such as doubly linked lists, there could be another pointer referring to its preceding node. Therefore, they can be iterated in both ways. However, we will learn about singly linked lists first.
Let’s Practice in Python
Now we know that linked lists consist of nodes and each node has a data value and a pointer value to the next node. We also learned that the first element of a linked list is known as its head. Let us implement all that knowledge into Python code.
Creation of a Linked List
In the following, we have created a simple Node class and a Linked List class to implement a singly linked list in our code.
If we print the linked list, the output will be the same as before.
Inserting to the middle
Let us now consider the scenario where we have to insert a new element to the middle of the linked list. We will insert a new element with the data 2 in between node_2 and node_3. If we are to perform a successful insertion, we will have to perform the following two steps.
Set the pointer of the new element to node_3
Set the pointer of node_2 to the new element
We will add a new function to our MyLinkedList class to perform the above two steps.
We will now insert a node with the value 15 to the end of the linked list we have created.
If we print the linked list, it will output the following.
Deleting Items from a Linked List
Now that we have mastered creation, traversing, and insertion, we will now look at how to delete elements from the linked list.
Just like before, modifications done to the linked list is almost always about rearranging the pointers. We will consider the three scenarios deletion at the beginning, deletion in the middle, deletion at the end.
Deleting at the beginning
In this, we only have to set the head of our linked list to its second item.
In this scenario, let us imagine we are to delete node_2 element with the value 1 from our linked list. In order to successfully execute the deletion, we are to point node_1 to node_3. We will write a function for that.
There it is. That is how we create our own Linked List and Node classes. We will now look at the Python libraries that can be used to make the whole Linked List process much easier.
Linked Lists Python Libraries
Deque from the collections module of Python is a great place to start Linked Lists. Deque is essentially for doubly linked lists and we will look at a few use cases and get ourselves familiar with its functionalities.
Creation of a linked list
We can simply import the collections module and get started as follows.
There we have created a linked list called my_list.
If we print it, it will return,
It means space has been created for us to add new nodes to the linked list.
Insertion of elements
We can insert elements to the end by using the append command.
If we print it, it will output,
We can also insert elements into its head position by using appendleft().
If we print it,
deque([3, 1, 2])
We can insert elements to its middle by using the insert function.
Its syntax is as insert( index, value).
The index is the position we want to insert a value to and value is the value we are inserting. Let us insert value 4 to the position 2 governed by zero indexing convention.
Print the whole linked list,
deque([3, 1, 4, 2])
Deletion of elements
We remove elements by using the element value. It will remove the first occurrence of the specified value.
If we print it,
deque([3, 1, 2])
If we are to delete it by the index, we can use the Python wide del command.
Print the linked list,
We can also use the pop function to remove elements. It will delete the last element and will print the value.
If we print the linked list, it will output,
confirming that the last value has been removed.
We can also remove the head value by using the popleft() function.
Doubly Linked Lists
We know that singly linked lists have two components in each of its nodes.
A data value
A pointer to the next node
As there is only one pointer, we can only traverse through the linked list in one direction.
However, in doubly linked lists, there is one more addition of another pointer. This pointer refers to each node’s preceding node. The following is a node of a doubly linked list in its most basic form.
If we consider the above figure, we can see that there are two pointers in addition to the data.
We can modify our previously written MyNode class by adding another variable prev_node facilitating doubly linked lists.
This way, we can even create circular linked lists by pointing each linked list’s last node to its first node and vice versa.
The biggest advantage of circular linked lists is that traversing through the list can be initiated at any arbitrary node. They are extremely similar to singly linked lists and therefore, they are as easy to use and implement in code. However, one thing to keep in mind is that while traversing through the linked list, the arbitrary starting point has to be remembered, or else it will traverse through the linked list indefinitely.
Linked lists are an efficient way to store data. They are linear, dynamic, and can be resized during runtime. Tasks such as low-level memory management are usually implemented using linked lists. Each node usually represents blocks of memories of any size. Linked lists make it easier to free, reassign, and reorder them.
Data in linked lists do not have to be in contiguous memory blocks and therefore, enable easy removal and addition of data unlike with arrays. However, there are some inherent disadvantages such as accessing elements which happen to be slower than it is with arrays.