Linked Lists in Python

This article will delve into implementing a linked list in Python. We shall utilize classes within the Python programming language to execute the linked list in Python. As we comprehend, a linked list comprises nodes containing two elements: data and a reference to another node. Initially, we shall implement the node itself.

What is Linked List in Python?

A linked List is a linear data structure, meaning that data elements are arranged in sequence and that each member element is connected to its next element. It consists of data objects in the form of nodes connected by links or pointers. Each node of LinkedList has two field:

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

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

Unlike Lists in Python, LinkedList's elements are stored at random locations in the memory.

Creation of Linked list in Python

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

Algorithm

Example

Explanation of Example

We created a node class, which is the basic unit of LinkedList. Inside it, we created a function that takes the value for the 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 will create some more nodes for our LinkedList. Then we store each node's address in their previous nodes by using Node.next. For example, the next pointer of node1 will point to node2.

Creating a Node Class

Creating a Node class in Python is fundamental in implementing various data structures like linked lists, trees, and graphs. A Node class typically represents an individual element in these data structures and contains a value and a reference to the next (and sometimes previous) node. Below is an example of how to create a simple Node class in Python:

Let's break down the components of this Node class:

1. Class Definition:

   • class Node:: This line declares the Node class in Python.

2. Constructor Method (__init__):

   • def __init__(self, data):: This method initializes a new instance of the Node class.
   • self refers to the current instance of the class.
   • data is the value that the node will hold.

3. Data Attribute:

   • self.data: This attribute holds the value of the node.

4. Next Pointer:

   • self.next: This attribute is a reference to the next node in a linked list. By default, it is set to None, indicating that the node currently does not point to any other node.

With this Node class, you can create individual nodes and link them together to form data structures like linked lists. Here's an example of how you can create and use nodes:

In this example:

• Three nodes with values 10, 20, and 30 are created.
• The next attribute of each node is assigned to the next node, linking them together.
• Finally, the linked list is traversed starting from the first node (node1), printing the value of each node along the way.

Traversing a Linked List in Python

A singly LinkedList can only be traversed in one direction(forward direction). This means that we can't return to the previous element of LinkedList if we pass that element. We 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 & assigned that first node as the head of our LinkedList. After assigning the value, we store the address of every next node in the previous node. Lastly, we created a pointer variable that currently stores the head value and gets updated during every iteration of the loop.

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

Insertion in a LinkedList

Insertion in a LinkedList means adding elements/nodes to the existing LinkedList. The basic technique used in inserting the newly created node into a LinkedList is reallocating 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 at the beginning of the LinkedList, we have to point the next pointer of the newly created node to the head of the LinkedList. So, the 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 a node at the beginning of the LinkedList.

Algorithm

Example

2. Insertion at The End

Insertion at the end of LinkedList is almost the 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 the newly created node, and then our new node gets added to the LinkedList at the end.

Algorithm

Example

Output

3. Inserting in between two Data Nodes

Example

Output

Update the Node of a Linked List

In this implementation:

• head is the head node of the linked list.
• target is the value of the node that needs to be updated.
• new_val is the new value that will replace the old value of the target node.
• We traverse the linked list using a while loop and check each node's value.
• If we find a node with the target value, we update its val attribute with the new value.
• Finally, we return the head of the modified linked list. The original list is returned unchanged if the target value is not found.

Delete Node in a Linked List

• This operation deletes a node with a given value from the linked list.
• It traverses the list to find the node with the specified value and removes it by updating the pointers of the previous and next nodes.

1. Remove First Node from Linked List:
   • This operation removes the first node from the linked list.
   • It updates the head pointer to the next node in the list.

2. Remove Last Node from Linked List:
   • This operation removes the last node from the linked list.
   • It traverses the list to find the second-to-last node and updates its next pointer to None.

3. Delete a Linked List Node at a Given Position:
   • This operation deletes the node at a specified position (index) in the linked list.
   • It traverses the list to find the node at the specified position and removes it by updating the pointers of the previous and next nodes.

4. Delete a Linked List Node of a Given Data:
   • This operation deletes the node with a specified value from the linked list.
   • It traverses the list to find the node with the specified value and removes it by updating the pointers of the previous and next nodes.

Get the Length of a Linked List in Python

In order to get the length of a linked list in Python, you can traverse the list while counting the number of nodes until you reach the end. Here's how you can implement it:

In this implementation:

• head is the head node of the linked list.
• We initialize a variable length to 0 to store the length of the linked list.
• We traverse the linked list using a while loop.
• We increment the length variable for each node encountered by 1.
• Once we reach the end of the linked list (when curr becomes None), we return the length value, which represents the total number of nodes in the linked list.

Advantages and Disadvantages of Linked List

Advantages of Linked Lists:

1. Dynamic Size: Linked lists can dynamically grow or shrink in size during program execution, unlike arrays, which have a fixed size.

2. Insertion and Deletion: Insertion and deletion operations can be performed efficiently at any position within a linked list.

3. Memory Utilization: Linked lists utilize memory efficiently by allocating memory only when needed.

4. Ease of Implementation: Implementing certain operations, such as inserting or deleting elements, is often simpler with linked lists compared to arrays due to fewer constraints on memory allocation.

5. Versatility: Python Linked lists support various linked structures, including singly linked lists, doubly linked lists, and circular linked lists.

Disadvantages of Linked Lists:

1. Sequential Access: Unlike arrays, linked lists do not support random access to elements based on their indices.

2. Memory Overhead: Linked lists require extra memory for storing pointers/references to the next node, increasing memory overhead compared to arrays.

3. Cache Inefficiency: Traversing a linked list in python may lead to cache misses since elements are not stored contiguously in memory.

4. Extra Space for Pointers: Each node in a linked list requires additional memory for storing pointers or references to the next node, leading to higher space complexity than arrays.

5. Complexity in Reversal: Reversing a linked list in Python or performing certain operations, such as finding the middle node, may require more complex algorithms than similar operations on arrays.

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