The boring section
A linked list is a type of data structure that stores a sequence of data elements, but unlike an array or a list, the elements are not stored in a contiguous block of memory. Instead, each element has a pointer or a link to the next element in the sequence, forming a chain of nodes. A linked list looks as follows:
Head -> Node1 -> Node2 -> Node3 -> None
In this representation,
Head points to the first node in the linked list, and each node points to the next node in the sequence until the last node (
Node3) that points to
None, indicating the end of the linked list.
You might have heard a lot about linked lists in data structure classes or online courses. However, to be honest, you don’t have to know about them, and you might never use them in real-world projects nowadays.
Linked lists are NOT built-in in Python. You have to implement them yourself using classes or use a module like
collections.deque that provides a linked list-like data structure (this work will be complicated and quite laborious). One possible reason why Python does not have a built-in linked list data structure is that it already provides a lot of flexibility and functionality with its list type, which can be used as a stack, a queue, or a general-purpose collection. Another possible reason is that Python is designed to be a high-level and expressive language, which abstracts away the low-level details of memory management and data structures.
That being said, learning linked lists still has certain benefits, such as giving you more control and efficiency over your data manipulation, especially when you need to insert or remove elements from both ends of the list.
Linked lists vs normal lists in Python
A linked list has some advantages and disadvantages compared to a regular list.
- You can easily add or remove data from anywhere in the list without shifting the other elements.
- You don’t need to specify the size of the list in advance, as it can grow or shrink dynamically.
- You can use linked lists to implement other data structures, such as queues, stacks, or graphs.
- You need more memory to store the links between the nodes, as well as the nodes themselves.
- You cannot access a specific element in the list by its index, as you have to traverse the list from the beginning until you find it.
- You have to be careful not to lose or break the links between the nodes, as this can cause errors or data loss.
The boring part with text and concepts should end here. It’s time to practice.
Working with linked lists requires writing a lot of code (way more than normal lists). That’s why I guess you don’t like them much. Anyway, it’s good to see some code examples.
In this example, we’ll create a simple linked list by defining a custom
Node class and a
LinkedList class to manage the nodes:
# SlingAcademy.com # This code uses Python 3.11.4 # Define a node class class Node: def __init__(self, data): self.data = data self.next = None # Define a linked list class class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return last_node = self.head while last_node.next: last_node = last_node.next last_node.next = new_node def print_list(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") # Create a linked list and append some data linked_list = LinkedList() linked_list.append(1) linked_list.append(2) linked_list.append(3) # Print the linked list linked_list.print_list()
1 -> 2 -> 3 -> None
A doubly linked list is a type of linked list in which each node consists of three attributes:
data attribute is used to store the data in the node. The
next attribute is used to refer to the next node in the linked list. And, the
previous attribute is used to refer to the previous node in the linked list.
To implement a doubly linked list in Python, we can define a
Node class and a
DoublyLinkedList class. The
Node class will have three attributes:
DoublyLinkedList class will have a head attribute that points to the first node of the list. It will also have methods to insert, delete, and traverse the nodes of the list.
# SlingAcademy.com # This code uses Python 3.11.4 # Define a Node class class Node: def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as None self.prev = None # Initialize prev as None # Define a DoublyLinkedList class class DoublyLinkedList: def __init__(self): self.head = None # Initialize head as None # Method to insert a new node at the beginning of the list def push(self, new_data): # Create a new node with the given data new_node = Node(new_data) # Make the new node's next point to the current head new_node.next = self.head # Make the current head's prev point to the new node if self.head is not None: self.head.prev = new_node # Make the new node's prev point to None new_node.prev = None # Make the new node as the new head self.head = new_node # Method to delete a node from the list def delete(self, key): # Find the node with the given key curr = self.head while curr is not None and curr.data != key: curr = curr.next # If the node is not found, return if curr is None: return # If the node is the head, make the next node as the new head if curr == self.head: self.head = curr.next # If the node is not the last node, make its next node's prev point to its prev node if curr.next is not None: curr.next.prev = curr.prev # If the node is not the first node, make its prev node's next point to its next node if curr.prev is not None: curr.prev.next = curr.next # Method to print the nodes of the list from head to tail def print_list(self): temp = self.head # Start from the head while temp: # Loop until temp is None print(temp.data) # Print the data of the current node temp = temp.next # Move to the next node # Create an empty doubly linked list dllist = DoublyLinkedList() # Insert some nodes at the beginning of the list dllist.push(15) dllist.push(10) dllist.push(5) # Print the list dllist.print_list() # Output: 5 10 15 # Delete a node from the list dllist.delete(10) # Print the list again dllist.print_list() # Output: 5 15
Sorting a linked list means rearranging the nodes in the list so that their data values are in ascending or descending order. There are different ways to sort a linked list, but we’ll only focus on merge sort in the example to come.
Merge sort is a divide-and-conquer algorithm that recursively splits the list into smaller sublists until each sublist contains only one node, and then merges the sublists in sorted order until the original list is sorted. The main steps of merge sort are:
- Split the list into two halves by finding the middle node and breaking the links between the two halves.
- Recursively sort the left and right halves using merge sort.
- Merge the sorted left and right halves by creating a new head node and comparing the data values of the left and right nodes, and appending the smaller one to the new head node until one of the halves is empty. Then append the remaining nodes of the other half to the new head node.
- Return the new head node to the sorted list.
This is an example of how to implement merge sort on a linked list in Python:
# SlingAcademy.com # This code uses Python 3.11.4 # Define a Node class class Node: def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as None # Define a LinkedList class class LinkedList: def __init__(self): self.head = None # Initialize head as None # Method to insert a new node at the end of the list def append(self, new_data): # Create a new node with the given data new_node = Node(new_data) # If the list is empty, make the new node as the head if self.head is None: self.head = new_node return # Otherwise, traverse to the last node last = self.head while last.next: last = last.next # Make the last node's next point to the new node last.next = new_node # Method to print the nodes of the list def print_list(self): temp = self.head # Start from the head while temp: # Loop until temp is None print(temp.data, end=" ") # Print the data of the current node temp = temp.next # Move to the next node print() # Print a newline # Method to split a list into two halves by finding the middle node def split_list(self, head): # If the list is empty or has only one node, return it as it is if head is None or head.next is None: return head, None # Otherwise, use two pointers: slow and fast slow = head # Move one step at a time fast = head.next # Move two steps at a time while ( fast and fast.next ): # Loop until fast reaches the end or one before the end slow = slow.next # Move slow one step forward fast = fast.next.next # Move fast two steps forward # Now slow is at the middle node, so break the link between slow and slow.next mid = slow.next slow.next = None # Return the two halves: head to slow, and mid to fast return head, mid # Method to merge two sorted lists by creating a new head node def merge_lists(self, left, right): # If either of the lists is empty, return the other one as it is if left is None: return right if right is None: return left # Otherwise, create a new head node with a dummy value head = Node(0) # Use a pointer to keep track of the current node of the new list curr = head while left and right: # Loop until either of the lists is empty if ( left.data <= right.data ): # If left's data is smaller or equal to right's data curr.next = left # Append left to curr's next left = left.next # Move left one step forward else: # If right's data is smaller than left's data curr.next = right # Append right to curr's next right = right.next # Move right one step forward curr = curr.next # Move curr one step forward # If there are any remaining nodes in left or right, append them to curr's next if left: curr.next = left if right: curr.next = right # Return the next of the head node, which is the actual head of the merged list return head.next # Method to sort a list using merge sort def merge_sort(self, head): # If the list is empty or has only one node, return it as it is if head is None or head.next is None: return head # Otherwise, split the list into two halves left, right = self.split_list(head) # Recursively sort the left and right halves using merge sort left = self.merge_sort(left) right = self.merge_sort(right) # Merge the sorted left and right halves head = self.merge_lists(left, right) # Return the sorted head node return head # Create an unsorted linked list llist = LinkedList() llist.append(15) llist.append(10) llist.append(5) llist.append(20) llist.append(3) llist.append(2) # Print the unsorted list print("Unsorted list:") llist.print_list() # Sort the list using merge sort llist.head = llist.merge_sort(llist.head) # Print the sorted list print("Sorted list:") llist.print_list()
Unsorted list: 15 10 5 20 3 2 Sorted list: 2 3 5 10 15 20
You’ve learned the fundamentals and walked through some practical examples of using linked lists in Python. What are your thoughts on linked lists? Tedious and overcomplicated or interesting and worth knowing about? Please let me know by leaving a comment.