The boring section
What are linked lists?
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 -> NoneIn 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.
It’s okay if you don’t want to learn about linked lists
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.
Advantages:
- 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.
Disadvantages:
- 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.
Examples
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.
Creating a linked list and appending some data
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()Output:
1 -> 2 -> 3 -> NoneDoubly linked list
A doubly linked list is a type of linked list in which each node consists of three attributes: data, next, and previous. The 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: data, next, and prev. The 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.
Example:
# 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 15Sorting a linked list with merge sort
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()Output:
Unsorted list:
15 10 5 20 3 2
Sorted list:
2 3 5 10 15 20 Afterword
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.
