In this installment of our exploration into data structures, we take an even deeper dive into the concept of Linked Lists, a versatile and dynamic way to handle sequential data. I wanted to demonstrate my Java code as well but that would have made this post way too long so I'll leave that for tomorrow.
Here, we expand our Python implementation of Linked Lists, enhancing its functionality, and moving beyond the basics. Let's get started!
class Node:
def __init__(self, value):
self.value = value # Stores the value of the node
self.next = None # Pointer to the next node in the list
Our Node class remains unchanged from our previous discussions.
class LinkedList:
def __init__(self, value):
new_node = Node(value) # Create a new node with the given value
self.head = new_node # Head points to our newly created node
self.tail = new_node # Tail also points to the new node
self.length = 1 # Initialize length to 1 as we have one node
Our LinkedList class's initialization remains unchanged. It creates a new list with a single node.
def pop_first(self):
temp = self.head # Save the current head
if self.length == 0:
return None
self.head = self.head.next # Move the head pointer to the next node
temp.next = None # Detach the original head node from the list
self.length -= 1
if self.length == 0:
self.tail = None # If the list is now empty, reset the tail as well
return temp # Return the removed node
The pop_first method removes the first node from the list and adjusts the head accordingly.
def get(self, index):
if index < 0 or index >= self.length:
return None
temp = self.head
for _ in range(index):
temp = temp.next
return temp
The get method retrieves a node at a specific index in the list.
def set(self, index, value):
temp = self.get(index) # Get the node at the given index
if temp is not None:
temp.value = value # Update the node's value if it exists
return True
return False # If the node doesn't exist, return False
The set method updates the value of a node at a specific index.
def insert(self, index, value):
if index < 0 or index > self.length:
return False
if index == 0:
return self.prepend(value)
if index == self.length:
return self.append(value)
temp = self.get(index - 1) # Get the node preceding the insertion point
new_node = Node(value) # Create a new node with the given value
new_node.next = temp.next # Set new node's next to temp's next
temp.next = new_node # Set temp's next to new node
self.length += 1 # Increase length
return True
The insert method adds a node with a specific value at a certain index.
def remove(self, index):
if index < 0 or index >= self.length:
return None
if index == 0:
return self.pop_first()
if index == (self.length - 1):
return self.pop()
pre = self.get(index - 1) # Get the node preceding the node to be removed
temp = pre.next # Temporarily store the node to be removed
pre.next = temp.next # Set preceding node's next to removed node's next
temp.next = None # Detach the removed node from the list
self.length -= 1 # Decrease length
return temp # Return the removed node
The remove method removes a node at a specific index in the list.
def reverse(self):
temp = self.head # Save the current head
self.head = self.tail # Swap head and tail
self.tail = temp
before = None # To store the previous node
after = temp.next # To store the next node
for _ in range(self.length):
after = temp.next # Save next node
temp.next = before # Reverse the link
before = temp # Move previous node one step ahead
temp = after # Move temp one step ahead
The reverse method inverts the list, making the head the tail, and vice versa.
def make_empty(self):
self.head = None # Remove reference to head
self.tail = None # Remove reference to tail
self.length = 0 # Set length to 0
The make_empty method empties the list, effectively deleting all nodes and resetting the list's length.
With these enhanced operations, our Linked List implementation now offers advanced data manipulation capabilities. Linked Lists form the foundation of many more complex data structures and algorithms, demonstrating the immense potential and diversity of computer science applications. Our coding prowess continues to grow with each new concept learned and implemented. Happy coding!