Unraveling the Mysteries of Linked Lists with Python
Elshad Karimov
Founder of AppMillers | Oracle ERP Fusion Cloud Expert | Teaching more than 200k people How to Code.
Let’s dive into linked lists, a super handy tool in the data structure world. They’re flexible and dynamic, making them great for managing data. We’ll explore this by looking at some Python code, breaking down the LinkedList and Node classes to see how they work. It’s going to be straightforward and fun, perfect for anyone curious about how to store and organize data effectively.
Today, we’ll dive deep into understanding linked lists through a Python implementation, dissecting each part of our LinkedList and Node classes to illuminate their functionality and applications.
Ready to get a clear, simple look at linked lists? Let’s go!
Linked List Implementation Youtube Video
My Udemy Bootcamps
Understanding the Node
At the heart of every linked list is the node, a simple yet powerful structure holding data and a reference to the next node.
class Node:
def __init__(self, value):
self.value = value
self.next = None
The Node class is straightforward: it initializes with a value and sets next to None, preparing the node to link to another when the time comes.
The LinkedList Class
Our LinkedList class is where the magic happens. It orchestrates how nodes are connected, accessed, and managed.
Initialization — Constructor
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
When a LinkedList is created, it starts empty. head and tail are None, and length is 0, signifying an empty list.
Visual Representation — __str__ method (print)
def __str__(self):
temp_node = self.head
result = ''
while temp_node:
result += str(temp_node.value) + ' -> ' if temp_node.next else str(temp_node.value)
temp_node = temp_node.next
return result
The __str__ method allows us to print our list, showing each value linked to the next, providing a clear, visual representation of our list's current state.
Append Method
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.length += 1
Appending adds a new node to the end. If the list is empty, this new node becomes both the head and the tail. Otherwise, it’s linked to the current tail and then becomes the new tail.
Prepend Method
def prepend(self, value):
new_node = Node(value)
if not self.head:
self.head = self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
self.length += 1
Prepending inserts a new node at the beginning. It becomes the new head, linking to the previous head.
Insert Method
def insert(self, index, value):
if index < 0 or index > self.length:
print("Error: Index out of bounds.")
return
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
elif index == 0:
new_node.next = self.head
self.head = new_node
else:
temp_node = self.head
for _ in range(index - 1):
temp_node = temp_node.next
if temp_node.next is None: # If we're inserting at the end
self.tail = new_node
new_node.next = temp_node.next
temp_node.next = new_node
self.length += 1
The insert method adds a node at a specified index, handling various edge cases, ensuring the list maintains its integrity.
Traverse Method
def traverse(self):
current = self.head
while current:
print(current.value)
current = current.next
Traversing lets us visit each node, an essential operation for viewing or modifying our list.
领英推荐
Search Method
def search(self, target):
current = self.head
while current is not None:
if current.value == target:
return True
current = current.next
return False
Searching checks for the presence of a value, returning its position or indicating its absence.
Get Method
def get(self, index):
if index == -1:
return self.tail
elif index < -1 or index >= self.length:
return None
current = self.head
for _ in range(index):
current = current.next
return current
get retrieves the value at a specified index, providing direct access to any node in the list.
Set_value Method
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
set_value updates the value of a node at a given index, allowing for modification of the list's content.
Pop First Method
def pop_first(self):
if self.length == 0:
return None
popped_node = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
popped_node.next = None
self.length -= 1
return popped_node
pop_first removes the first node of the list, adjusting the head to the next node, and reducing the list's length.
Pop Method
def pop(self):
if self.length == 0:
return None
popped_node = self.tail
if self.length == 1:
self.head = self.tail = None
else:
temp = self.head
while temp.next is not self.tail:
temp = temp.next
temp.next = None
self.tail = temp
self.length -= 1
return popped_node
pop removes the last node of the list, meticulously adjusting the second-to-last node to become the new tail.
Remove Method
def remove(self, index):
if index < 0 or index >= self.length: # Check for out-of-range index
return None
if index == 0: # If removing the head node
return self.pop_first()
if index == self.length-1: # If removing the tail node
return self.pop()
# For removing a node in between
prev_node = self.get(index-1)
popped_node = prev_node.next
prev_node.next = popped_node.next
popped_node.next = None
self.length -= 1
return popped_node
Removing a node, whether it’s at the edges or in the middle, requires careful re-linking to maintain list integrity.
Delete All Method
def delete_all(self):
self.head = None
self.tail = None
self.length = 0
Finally, delete_all cleans our slate, setting us back to an empty list, ready for new operations.
Linked lists, with their sequential yet non-contiguous nature, offer a flexible alternative to arrays. Through the LinkedList class, we gain a hands-on understanding of how dynamic data structures operate, equipping us with the knowledge to tackle more complex problems in computer science.
By exploring each method and understanding its role in the larger structure, we appreciate the elegance and utility of linked lists, a testament to the beauty and power of data structures.
Full Code
# Created by Elshad Karimov
# Copyright ? 2024 AppMillers. All rights reserved.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0
def __str__(self):
temp_node = self.head
result = ''
while temp_node is not None:
result += str(temp_node.value)
if temp_node.next is not None:
result += ' -> '
temp_node = temp_node.next
return result
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
self.tail = new_node
self.length += 1
def prepend(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head = new_node
self.length += 1
def insert(self, index, value):
if index < 0 or index > self.length:
print("Error: Index out of bounds.")
return
new_node = Node(value)
if self.length == 0:
self.head = new_node
self.tail = new_node
elif index == 0:
new_node.next = self.head
self.head = new_node
else:
temp_node = self.head
for _ in range(index - 1):
temp_node = temp_node.next
if temp_node.next is None: # If we're inserting at the end
self.tail = new_node
new_node.next = temp_node.next
temp_node.next = new_node
self.length += 1
def traverse(self):
current = self.head
while current is not None:
print(current.value)
current = current.next
def search(self, target):
current = self.head
while current is not None:
if current.value == target:
return True
current = current.next
return False
def search1(self, target):
current = self.head
index = 0
while current is not None:
if current.value == target:
return index
current = current.next
index += 1
return -1
def get(self, index):
if index == -1:
return self.tail
elif index < -1 or index >= self.length:
return None
current = self.head
for _ in range(index):
current = current.next
return current
def set_value(self, index, value):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
def pop_first(self):
if self.length == 0:
return None
popped_node = self.head
if self.length == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
popped_node.next = None
self.length -= 1
return popped_node
def pop(self):
if self.length == 0:
return None
popped_node = self.tail
if self.length == 1:
self.head = self.tail = None
else:
temp = self.head
while temp.next is not self.tail:
temp = temp.next
temp.next = None
self.tail = temp
self.length -= 1
return popped_node
def remove(self, index):
if index < 0 or index >= self.length: # Check for out-of-range index
return None
if index == 0: # If removing the head node
return self.pop_first()
if index == self.length-1: # If removing the tail node
return self.pop()
# For removing a node in between
prev_node = self.get(index-1)
popped_node = prev_node.next
prev_node.next = popped_node.next
popped_node.next = None
self.length -= 1
return popped_node
def delete_all(self):
self.head = None
self.tail = None
self.length = 0
linked_list = LinkedList()
linked_list.get(0)
# linked_list.append(10)
# linked_list.append(20)
# print(linked_list)
# linked_list.pop()
# print(linked_list.tail.value)
# print(linked_list.head.value)
# print(linked_list)
If you found them helpful:
Discover more in my online courses at AppMillers ??
Connect on LinkedIn: Elshad Karimov
Follow on X (Twitter): Elshad Karimov
Subscribe our Newsletter for recent Technological advancements : Newsletter by Elshad Karimov
Integration Developer | DevOps Engineer | AWS Certified
7 个月Good one! Especially the search1 implementation. Thanks!