Linkedlist in Python

Introduction to Linked List in Python

Ever wondered how incoming requests to a shared resource like a printer are handled on a network. The solution for this complicated thought is LinkedList which is thoroughly described in this article. Read along to know more.

Like Arrays, LinkedList is the linear data structure(i.e data elements are arranged in sequential manner and each member element is connected to its next element). It consists of data objects in form of nodes which are connected by links or pointers. Each node of LinkedList has 2 field:

• Data: Stores the value of node in this field.
• Next: Stores the address of the next linked node.

In LinkedList, the first most nodes is considered as the Head of the LinkedList which stores the address of the LinkedList and the last node is considered by using the NONE value into the next field of the node.

Unlike Lists in python, LinkedList's elements are stored at the random location of the memory.

Why LinkedList?

The main benefit of a linked list over the array is that the linkedlist elements can be easily inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while restructuring an array at run-time is a much more expensive operation.

Linked lists allow insertion and removal of nodes at any point in the list, and allow doing so with a constant number of operations by keeping the link previous to the link being added or removed in memory during list traversal.

1. LinkedLists are Dynamic In Nature:

As we cann't increase/allocate extra space for arrays during the compilation of the code, so we get bounded to that limited space. But LinkedList is benifical here for allocating new memory during the run time. Not only limited to the increase/extra allocation of space we can remove the extra space from the LinkedList during the run time.

2. Insertion is easier in LinkedList :

During the insertion process we have to shift some elements to some extra space due to which it is complicated to insert elements in array.

3. Deletion is easier in LinkedList:

During the deletion process, when we delete some element from the array then we have to shift all the elements right of it to left position to fill up the vacant space while we just have to update the address of the node which is ahead of the deleted node.

Node

The nodes are created by implementing a class which will hold the pointers along with the data element. In the below example we create a class named chocolates to hold the name of the chocolates. The nextval pointer is initialized to null and three nodes and initialized with values as shown.

Example

Creation Of Linked List in Python

LinkedList is created by using the node class. In Node class we create a function which is used for setting the value and the next pointer for the node. We pass the values through the node object to point the next data elements. In this static example, we adding 5 nodes in the linkedlist manually by adding each node one by one.

Algorithm

Example

Explanation of Example

We created a Node class which is the basic unit for LinkedList. Inside it, we created a function which takes value for node as a parameter. Then, we assign the value to the node. And, we place None for the next pointer for that node. Now, we create first node and give it a value elem1. We stored the address of node1 to the head variable. After that, we create some more nodes fot our LinkedList. Then we store each node's address to their previous Nodes by using Node.next. For example, next pointer of node1 will points to node2.

How to Traversing a Linked List in Python?

A singly LinkedList can only be traversed in one direction(forward direction). It means that we cann't come back to the previous element of the LinkedList if we passed that element. We just have to traverse the elements of the LinkedList with the help of the pointer assigned to the next node.

Algorithm

Example

Output

Explanation

First of all, we created a node class so that we can create our basic unit of the LinkedList. After that we created the first node & assign that first node as the head of our LinkedList. After assigning the value, we store the address of every next node into the previous node. Lastly, we created a pointer variable which currently stores the value of head and it get updated during every iteration of loop.

Then, we start writing the code for traversal of LinkedList. We implement a while loop till Node.Next not equals to None. As loop is running, we are printing the value of each node. After printing the value of node, we update the pointer so that it can point to next node.

Insertion in a LinkedList

Insertion in a LinkedList means adding elements/nodes to the already existing LinkedList. The basic technique used in insertion of newly created node into a LinkedList is the reallocation of the next pointer of an already existing node of the LinkedList.

Orignal LinkedList Before Insertion

We can insert a node to 3 different positions of LinkedList. Let's understand each of these one by one:

1. Insertion at Beginning

While Inserting a node in the beginning of the LinkedList we have to point the next pointer of the newly created node to the head of the LinkedList. So that, current head changes to the second node of the LinkedList and the newly created node changes to the head of the LinkedList.

Let's understand the algorithm and the example for the insertion of node in the beginning of the LinkedList.

Algorithm

Insertion Process in Beginning

Example

Inserted node in Beginning

Output

Explanation

First of all, we created a node class so that we can create our basic unit of the LinkedList. After that we created the first node & assign that first node as the head of our LinkedList. After assigning the value, we store the address of every next node into the previous node.

After creating the new node we store the value of next into the next pointer of the new node so that the new node can points to the current head of the LinkedList.

Finally, we update the head of the LinkedList by assigning the address of the new node created to it. Now during the traversal of the LinkedList head points to the newly created node and then goes to its remaining previous nodes.

After that we will traverse the linkedlist to get all the nodes value one by one.

2. Insertion at any position of LinkedList

For inserting a node at any position of the LinkedList we require the node after which the newly created node has to be inserted. While inserting the new node, we will traverse to the existing node after which we have to insert the new node. Update the next pointer of the new node with the next pointer of the existing node to which we have traveresed and the update the next pointer of the existing node with the new node.

Let's understand the algorithm and the example for the insertion of node in the middle of the LinkedList.

Algorithm

Insertion Process in between 2 nodes

Example

Output

Inserted Node in between 2 nodes

Explanation

We created some nodes and value to them. After assigning the value, we store the address of every next node into the previous node. We then create a after variable which stores the node value after which we have to add a new node. Then, we create a new node which is to be inserted in the middle of the LinkedList. We then, use loop to iterate over the nodes value and check its value.

If the value of that node is equals the after then we assign the value of next pointer of existing node to the next pointer of the new node. After update the next field of new node, update the next pointer of the existing node with the new node so that it can point to the new node.

After assigning all the values to the next pointer we use break statement to get out of the loop and continue the traversal process otherwise we update the pointer and traverse to the next node and repeat the step till the loop is running. Lastly, we update the which helps us to traverse and print the LinkedList.

Then we write code for traversal of linkedlist where we can see that new node gets added at the specified position of the linkedlist.

3. Insertion at The End of LinkedList

Insertion at the end of LinkedList is almost same as that in the middle of the LinkedList. In this case, we don't have to update the next pointer of the new node but we just update the next pointer of the last node with the address of newly created node and then our new node gets added to the LinkedList at the end.

Algorithm

Insertion process at end

Example

Output

Inserted Node at end

Explanation

We created some nodes and then assign values to them. After assigning the value, we store the address of every next node into the previous node. Then, we create a new node which is to be inserted in the end of the LinkedList.

We then, use loop to iterate over the nodes next pointer till they are not None. We update the pointer and traverse to the next node and repeat the step till the loop is running. Finally, we update the next pointer of the last node with the newly created node. Lastly, we update the which helps us to traverse and print the LinkedList.

Then we write code for traversal of linkedlist and we can see that a new node gets added at the end of the linkedlist.

Deletion Of Node from LinkedList

Here, we remove the node by using the value of nodes of the LinkedList. We just have to locate the previous node after which the node to be deleted is present.

Deletion in LinkedList can be done in the following two different ways:

1. Deletion from Beginning of LinkedList

For deletion of the node from the beginning of the LinkedList we have to update the address of node present in the head of LinkedList with the node after the first node.

Let's understand this better with the help of Algorithm and the Example.

Algorithm

Deletion Process from Beginning

Example

Output

Deletion of Node from Beginning of LinkedList

Explanation

We created some nodes and assign values to them. After assigning the value, we store the address of every next node into the previous node. We have to update the head of the LinkedList with the next node to the first node. Lastly, we update the which helps us to traverse and print the LinkedList.

After that we write code for traversal of linkedlist and we can checkout that the initial node get deleted from the linkedlist.

Deletion from Mid & End of LinkedList

For deletion of a node from middle or end of the LinkedList, the basic technique used is to break the link to the node to be deleted and join together the nodes previous and ahead of the node to be deleted. For this we reach to the node previous to the node to be deleted and update the next pointer with the node after the node to be deleted.

This technique of deletion of node works for both the case deleting a node from mid or end of linkedlist. We don't need to handle individual cases differently.

This is explained by the following algorithm

Algorithm

Deletion Process from Middle

Example

Output

Deletion of Node from Middle of LinkedList

Explanation

We created some nodes and assign value to them. After assigning the value, we store the address of every next node into the previous node. We created a variable contains the value for the node to be deleted. Then we start loop till we got don't get None. We checked the pointer's next pointer value. if the value is same as that of the node which we have to delete them we have to assign the pointer ahead of the nodetobedeleted to the node behind of nodetobedeleted otherwise, we update the pointer to it's next one so that we can traverse the whole LinkedList.

Then we write code for traversal of linkedlist and when we got output we can crealy see that the node gets deleted.

Using Advanced LinkedList

Doubly LinkedList

A type of LinkedList in which a node has 2 pointer fields for storing the address of the previous and the next node of the sequence. This type of LinkedList is termed as Doubly LinkedList.

So a doubly LinkedList has 3 parts:

• Pointer to the previous node (previous pointer)
• Node Data/Value
• Pointer to the next node (next pointer)

In a normal/single LinkedList, we can traverse only in one direction, because each node has address of it's next node and it we cann't go to the previous nodes. But in case of doubly LinkedList, each node of the list contains the address of its previous node, thus we can find all the details about the previous node as well by using the previous address stored inside the previous part of each node. So, in doubly LinkedList we can traverse in both the directions(forward & backward).

For more detailed understanding of Doubly LinkedList please refer to this article.

Circular LinkedList

A type of LinkedList in which the last node of the LinkedList contains the address of the head of the LinkedList. This type of LinkedList is termed as Circular LinkedList.

We can traverse the circular LinkedList until we reach to the same node from where we started the traversal. The circular LinkedList has no beginning and no ending because there is no null value present in the next part of any of the nodes.

For more detailed understanding of Doubly LinkedList please refer to this article.

Advantage Of LinkedList over Arrays

• Insertion & Deletion process is faster in LinkedList as compared to Arrays.
• As LinkedList are not limited to specific size, they are dynamic in nature so we can't have to allocate memory during compile time as we do in Arrays.
• As the size of a linked list can grow or shrink at runtime, so there is no memory wastage. Only the required memory is allocated

Disadvantage Of LinkedList over Arrays

• The memory required by a linked list is more than the memory required by an array.
• To access node an at index x in a linked list, we have to traverse through all the nodes before it. But in the case of an array, we can directly access an element at index x, using arr[x].
• Search time is slower in LinkedList as compared to Arrays because random access is not avaiable in linkedlist.

Read More:

1. Singly Linked List
2. Linked List in C
3. LinkedList in Java
4. init function in python
5. insert() function in Python