A Deeper Dive Into Linked Lists: Just The Python This Time

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!