Welcome to our deep dive into Linked Lists in Python! This tutorial is designed to guide both beginners and intermediates in understanding and implementing Linked Lists, a fundamental data structure in computer science.
A Linked List is a collection of data elements, called nodes, linked using pointers. Unlike arrays, where elements are stored continuously in memory, Linked Lists allow for dynamic memory allocation and insertion/deletion of elements on the fly.
Each node in a Linked List contains:
class Node:
def __init__(self, data=None):
self.data = data
self.next = NoneTo create a Linked List, we'll first create an empty head node and then add nodes one by one.
def create_linked_list(data_list):
head = Node() # Create an empty head node
current = head # current node points to head
for data in data_list:
new_node = Node(data) # Create a new node with the given data
current.data = data # Store the data in the current node
current.next = new_node # Move the current node to the new node
return head # The linked list is now stored in the head nodeTo traverse a Linked List, we start from the head node and follow the next pointers until we reach the end of the list.
def traverse_linked_list(head):
current = head
while current is not None:
print(current.data)
current = current.nextWhat is a Linked List in Python?
To add a node at the beginning of the Linked List, we create a new node, update the next pointer of the current head, and move the head pointer to the new node.
def add_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
head = new_nodeTo delete a node, we need to find the previous node and update the next pointer of the previous node to point to the next node after the one to be deleted.
def delete_node(head, key):
if head is None:
return head
if head.data == key:
head = head.next
return head
current = head
while current.next is not None and current.next.data != key:
current = current.next
if current.next is None:
print(f"{key} not found in the list.")
return head
current.next = current.next.next
return headWhat is the time complexity of adding a node at the beginning of a Linked List in Python?
Finding the middle of a Linked List involves traversing half the length of the list. We can do this by counting the number of nodes as we traverse the list and then moving the second pointer two steps at a time.
def find_middle(head):
slow = head
fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slowWhat is the time complexity of finding the middle of a Linked List in Python?
Reversing a Linked List can be done by storing the previous node, current node, and next node in temporary variables, and then updating the pointers accordingly.
def reverse_linked_list(head):
prev = None
current = head
while current is not None:
next = current.next
current.next = prev
prev = current
current = next
return prevWhat is the time complexity of reversing a Linked List in Python?
Congratulations on learning about Linked Lists in Python! You now have a solid understanding of their structure, creation, traversal, addition, deletion, and manipulation.
Linked Lists are a versatile data structure used in various real-world applications, including database systems, operating systems, and web applications. Keep practicing, and soon you'll be able to create your own Linked List-based projects! 📝 ✅