Python - Linked Lists

By: Rajesh P.S.

A linked list is a data structure used to store a collection of elements. It consists of a sequence of nodes, each of which contains an element and a reference (or pointer) to the next node in the sequence. The first node in the sequence is called the head of the list, and the last node is called the tail.

What is Linked List

Unlike arrays, linked lists do not use a contiguous block of memory to store the elements. Instead, each node in the list is allocated separately and connected to the next node through the reference in the previous node. This allows for efficient insertion and deletion operations, as the nodes do not need to be shifted to make space for a new element. However, accessing a specific element in the list can be slower than in an array, as the list must be traversed from the beginning until the desired element is found.

Implementation of Linked List

Linked lists can be implemented in different ways, such as singly linked lists, doubly linked lists, and circular linked lists. In a singly linked list, each node has a reference to the next node in the sequence, but not to the previous node. In a doubly linked list, each node has references to both the next and previous nodes, allowing for efficient traversal in both directions. In a circular linked list, the last node is connected to the first node, forming a loop.

Continue Reading...

How do you create a linked list in Python?

Following an example of how to create a linked list in Python using the Node and LinkedList classes:

In the above implementation, the Node class represents a node in the linked list. Each node has two attributes: value, which stores the value at that node, and next, which is a reference to the next node in the list.

The LinkedList class represents the entire linked list. It has two attributes: head, which is a reference to the first node in the list, and tail, which is a reference to the last node in the list.

The add_node method is used to add a new node to the end of the list. If the list is empty (head is None), the new node becomes the head of the list. Otherwise, the next attribute of the current tail node is set to the new node, and the tail attribute is updated to the new node.

Next, create a LinkedList object called my_list and add three nodes to it with values 100, 200, and 300, respectively, using the add_node method.

Traversing a Linked List

Traversing a linked list means visiting each node in the list exactly once. Following an example of how to traverse a linked list in Python:

#Output: 100 200 300

In the above example, the traverse method of the LinkedList class is used to print the value of each node in the list. The method starts by initializing current_node to be the head of the list. It then enters a loop that continues until current_node is None (i.e., the end of the list has been reached). During each iteration of the loop, the method prints the value of the current node and updates current_node to be the next node in the list (i.e., the node referenced by the next attribute of the current node).

Next, create a LinkedList object called my_list and add three nodes to it with values 100, 200, and 300, respectively, using the add_node method. Then call the traverse method to print the values of all three nodes in the list.

Insert an element at the beginning of a linked list

To insert an element at the beginning of a linked list in Python, you need to create a new node with the desired value, and make it the new head of the list by updating the next attribute of the new node to point to the old head node.

#Output: 100 200 300

Insert_at_beginning method of the LinkedList class is used to insert a new node with the specified value at the beginning of the list. The insert_at_beginning() method creates a new node with the desired value and updates its next attribute to point to the old head node (i.e., the node currently referenced by self.head). It then sets the head attribute of the list to the new node, making it the new first node in the list.

Insert an element at the end of a linked list

To insert an element at the end of a linked list in Python, you need to create a new node with the desired value, and make it the new tail of the list by updating the next attribute of the current tail node to point to the new node.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: self.tail.next = new_node self.tail = new_node def insert_at_end(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: self.tail.next = new_node self.tail = new_node def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next my_list = LinkedList() my_list.add_node(100) my_list.add_node(200) my_list.insert_at_end(300) my_list.traverse()

#Output: 100 200 300

The insert_at_end method of the LinkedList class is used to insert a new node with the specified value at the end of the list. The method creates a new node with the desired value and updates the next attribute of the current tail node (i.e., the node currently referenced by self.tail) to point to the new node. It then sets the tail attribute of the list to the new node, making it the new last node in the list.

Insert an element in between two Data Nodes of a linked list

To insert an element in between two data nodes of a linked list in Python, you need to create a new node with the desired value, and update the next attribute of the new node to point to the node that comes after the node you want to insert the new node after, and update the next attribute of the node you want to insert the new node after to point to the new node.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: self.tail.next = new_node self.tail = new_node def insert_between_nodes(self, prev_node_value, new_node_value): new_node = Node(new_node_value) current_node = self.head while current_node is not None: if current_node.value == prev_node_value: new_node.next = current_node.next current_node.next = new_node if current_node == self.tail: self.tail = new_node return current_node = current_node.next print(f"Error: {prev_node_value} not found in linked list") def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next my_list = LinkedList() my_list.add_node(100) my_list.add_node(300) my_list.insert_between_nodes(100, 200) my_list.traverse()

#Output: 100 200 300

The insert_between_nodes method of the LinkedList class is used to insert a new node with the specified value in between two existing nodes in the list. The method searches for the node with the value equal to the specified prev_node_value using a while loop. Once the node is found, the new node is created and its next attribute is set to the next attribute of the found node. The next attribute of the found node is then updated to point to the new node.

Delete an element from a linked list

To delete an element from a linked list in Python, you need to update the next attribute of the node that comes before the node you want to delete to point to the node that comes after the node you want to delete. You also need to handle the case where the node you want to delete is the head of the linked list, in which case you need to update the head attribute of the linked list to point to the node that comes after the head.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: self.tail.next = new_node self.tail = new_node def delete_node(self, value): current_node = self.head if current_node is not None and current_node.value == value: self.head = current_node.next current_node = None return while current_node is not None: if current_node.value == value: break prev_node = current_node current_node = current_node.next if current_node == None: return prev_node.next = current_node.next current_node = None def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next my_list = LinkedList() my_list.add_node(100) my_list.add_node(200) my_list.add_node(300) my_list.delete_node(200) my_list.traverse()

#Output: 100 300

The delete_node method of the LinkedList class is used to delete the node with the specified value from the list. The method searches for the node with the value equal to the specified value using a while loop. If the node to be deleted is the head node, then we update the head attribute of the list to point to the node after the head, and delete the head node. If the node to be deleted is not the head node, then we traverse the list to find the node to be deleted and update the next attribute of the node that comes before it to point to the node that comes after it.

Search for an element in a linked list

To search for an element in a linked list in Python, you can iterate through each node in the list and compare the value of each node with the value you are searching for.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None self.tail = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: self.tail.next = new_node self.tail = new_node def search(self, value): current_node = self.head while current_node is not None: if current_node.value == value: return True current_node = current_node.next return False def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next my_list = LinkedList() my_list.add_node(100) my_list.add_node(200) my_list.add_node(300) print(my_list.search(200)) print(my_list.search(400))

#Output: True False

The search method of the LinkedList class is used to search for a node with a specific value. The method iterates through the linked list by starting from the head node and checking each node's value. If the value is found, the method returns True, otherwise, it continues to the next node. If the end of the list is reached and the value has not been found, the method returns False.

Reverse a linked list in Python

To reverse a linked list, you need to change the pointers of each node to point to the previous node instead of the next node.

#Output: Original list: 100 200 300 Reversed list: 300 200 100

The reverse method of the LinkedList class is used to reverse the linked list. The method uses three pointers: current_node, previous_node, and next_node. Initially, previous_node is set to None and current_node is set to the head of the list. The method iterates through the list and for each node, it sets next_node to the next node in the list, sets the next pointer of current_node to previous_node, and then updates previous_node to current_node and current_node to next_node. Finally, the head of the list is set to previous_node.

Find the middle element of a linked list

To find the middle element of a linked list in Python, you can use the slow-fast pointer technique. In this technique, you use two pointers, one that moves one step at a time (slow pointer) and another that moves two steps at a time (fast pointer). When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element of the list.

#Output: Original list: 100 200 300 400 500 Middle element: 300

The find_middle_element method of the LinkedList class is used to find the middle element of the linked list. The method uses the slow-fast pointer technique, where slow_pointer and fast_pointer are initially set to the head of the list. The while loop continues until fast_pointer reaches the end of the list or the second-to-last node. In each iteration of the loop, slow_pointer moves one step forward and fast_pointer moves two steps forward. When the loop ends, slow_pointer will be pointing to the middle element of the list.

Merge two linked lists in Python

To merge two linked lists, you can create a new linked list and iterate through both lists, comparing the values of the nodes and adding the smaller value to the new list. Once one list is exhausted, the remaining nodes of the other list can be appended to the new list.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: current_node = self.head while current_node.next is not None: current_node = current_node.next current_node.next = new_node def merge(self, other_list): new_list = LinkedList() current_node1 = self.head current_node2 = other_list.head while current_node1 is not None and current_node2 is not None: if current_node1.value < current_node2.value: new_list.add_node(current_node1.value) current_node1 = current_node1.next else: new_list.add_node(current_node2.value) current_node2 = current_node2.next while current_node1 is not None: new_list.add_node(current_node1.value) current_node1 = current_node1.next while current_node2 is not None: new_list.add_node(current_node2.value) current_node2 = current_node2.next return new_list def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next # create first linked list list1 = LinkedList() list1.add_node(100) list1.add_node(300) list1.add_node(500) # create second linked list list2 = LinkedList() list2.add_node(200) list2.add_node(400) list2.add_node(600) # merge the two lists and print the result merged_list = list1.merge(list2) print("Merged list:") merged_list.traverse()

#Output: Merged list: 100 200 300 400 500 600

Create two linked lists list1 and list2 with values 100, 300, and 500 and 200, 400, and 600, respectively, using the add_node method of the LinkedList class. Then call the merge method of list1 and pass list2 as an argument to merge the two lists. The method creates a new LinkedList object called new_list and iterates through both lists, comparing the values of the nodes and adding the smaller value to new_list. Once one list is exhausted, the remaining nodes of the other list are appended to new_list. Finally, the method returns new_list.

Remove duplicates from a linked list

To remove duplicates from a linked list, you can use a hash table to keep track of the values you have seen. You can iterate through the linked list and check if the value of each node is in the hash table. If it is, you can remove the node from the linked list. If it is not, add the value to the hash table.

#Output: Linked list without duplicates: 100 200 300 400

Create a linked list linked_list with values 100, 200, 300, 200, 400, and 100 using the add_node method of the LinkedList class. Then call the remove_duplicates method of linked_list to remove the duplicates. The method initializes a hash table called values_seen with the value of the first node of the linked list and iterates through the linked list, checking if the value of each node is in values_seen. If it is, the node is removed from the linked list. If it is not, the value is added to values_seen. Finally, the method returns the modified linked list.

Sort a linked list in Python

To sort a linked list in Python, use any sorting algorithm such as insertion sort, bubble sort, or merge sort. Merge sort is generally preferred as it has a time complexity of O(n log n) and is a stable sorting algorithm.

class Node: def __init__(self, value): self.value = value self.next = None class LinkedList: def __init__(self): self.head = None def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: current_node = self.head while current_node.next is not None: current_node = current_node.next current_node.next = new_node def merge_sort(self, head): if head is None or head.next is None: return head # split the linked list into two halves middle_node = self.get_middle(head) second_half = middle_node.next middle_node.next = None # recursively sort the two halves left_half = self.merge_sort(head) right_half = self.merge_sort(second_half) # merge the sorted halves sorted_list = self.merge(left_half, right_half) return sorted_list def get_middle(self, head): slow_pointer = head fast_pointer = head while fast_pointer.next is not None and fast_pointer.next.next is not None: slow_pointer = slow_pointer.next fast_pointer = fast_pointer.next.next return slow_pointer def merge(self, list1, list2): dummy_node = Node(0) current_node = dummy_node while list1 is not None and list2 is not None: if list1.value <= list2.value: current_node.next = list1 list1 = list1.next else: current_node.next = list2 list2 = list2.next current_node = current_node.next if list1 is not None: current_node.next = list1 else: current_node.next = list2 return dummy_node.next def traverse(self): current_node = self.head while current_node is not None: print(current_node.value) current_node = current_node.next # create linked list linked_list = LinkedList() linked_list.add_node(300) linked_list.add_node(100) linked_list.add_node(400) linked_list.add_node(200) # sort and print the result sorted_list = linked_list.merge_sort(linked_list.head) print("Sorted linked list:") while sorted_list is not None: print(sorted_list.value) sorted_list = sorted_list.next

#Output: Sorted linked list: 100 200 300 400

Create a linked list linked_list with values 300, 100, 400, and 200 using the add_node method of the LinkedList class. Then call the merge_sort method of linked_list to sort the linked list using merge sort. The method first checks if the linked list is empty or has only one node. If it does, it returns the linked list as is. Otherwise, it recursively splits the linked list into two halves, sorts the two halves separately, and then merges the sorted halves using the merge method.

When Should You Use a Linked List

Linked lists are useful in situations where you need to frequently insert or delete elements in a data structure. They are also useful when you do not know the size of the data beforehand and need a dynamic data structure that can be resized as needed. Here are some situations where linked lists can be particularly useful:

When the size of the data is unknown: Linked lists can be used when you do not know the size of the data that will be stored beforehand. Because linked lists can be resized easily by changing the links between nodes, you can add or remove nodes as needed to accommodate the data.
When frequent insertions or deletions are required: Linked lists are a good choice when you need to frequently insert or delete elements from a data structure. Because only the links between nodes need to be updated when elements are inserted or deleted, the performance impact of these operations is usually small.
When memory is a concern: Linked lists can be more memory-efficient than arrays when you have a lot of small elements. This is because arrays require a contiguous block of memory to store their elements, whereas linked lists only require the memory needed for the individual nodes.
When elements need to be stored in a specific order: Linked lists can be used to maintain a specific order of elements. For example, you can use a linked list to maintain a sorted list of elements, where new elements are inserted in the correct order as they are added to the list.
When you need to implement a stack or a queue: Stacks and queues are often implemented using linked lists because they require efficient insertions and deletions at one end of the list.

Applications of Linked Lists

Linked lists are a fundamental data structure that has a wide range of applications in computer science and software engineering. Here are some common applications of linked lists:

Implementing data structures: Linked lists are often used as the underlying data structure for other data structures such as stacks, queues, and hash tables. For example, a stack can be implemented using a linked list where the top of the stack is represented by the first node of the list.
Managing memory: Linked lists can be used to manage memory in operating systems and programming languages. For example, a linked list can be used to keep track of free memory blocks, where each block represents a node in the list.
Music and media players: Linked lists can be used to create playlists in music and media players. Each song or media file can be represented by a node in the linked list, and the links between the nodes can be used to define the order of the playlist.
Image processing: Linked lists can be used in image processing applications to represent and manipulate pixels in an image. Each pixel can be represented by a node in the list, and the links between the nodes can be used to define the spatial relationship between pixels.
Web applications: Linked lists can be used to represent web pages and their links in web applications. Each web page can be represented by a node in the list, and the links between the nodes can be used to define the hyperlinks between web pages.
Games: Linked lists can be used to represent the game board in some board games such as chess or checkers. Each game piece can be represented by a node in the list, and the links between the nodes can be used to define the allowable moves for each piece.

Conclusion:

Linked lists are an important data structure in Python and other programming languages. They consist of nodes that hold data and pointers to the next node in the sequence, allowing for efficient traversal and manipulation of the list. Linked lists have various applications in computer science, including as a fundamental building block for more complex data structures, such as trees and graphs. They are particularly useful when dealing with large datasets that need to be stored dynamically and are frequently updated. However, their main disadvantage is that they require more memory than other data structures, such as arrays, because of the need to store pointers to the next node.

Next > Switch Case in Python | Match-Case Statement

Related Topics

More Related Topics.....