Linked List

 A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation, allowing for efficient insertion and deletion operations.

In Python, we can implement a basic linked list by creating a Node class and a LinkedList class that manages the nodes. 


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, value):
        # Create a new node with the given value
        new_node = Node(value)
        
        # If the linked list is empty, set the new node as the head
        if self.head is None:
            self.head = new_node
        else:
            # Traverse to the end of the list and append the new node
            curr = self.head
            while curr.next is not None:
                curr = curr.next
            curr.next = new_node

    def delete(self, value):
        if self.head is None:
            return
        
        # If the head node has the value, update the head to the next node
        if self.head.value == value:
            self.head = self.head.next
            return

        # Traverse the linked list to find the node with the given value
        curr = self.head
        prev = None
        while curr is not None:
            if curr.value == value:
                # Remove the node by updating the previous node's next reference
                prev.next = curr.next
                return
            prev = curr
            curr = curr.next

    def search(self, value):
        # Traverse the linked list to find the node with the given value
        curr = self.head
        while curr is not None:
            if curr.value == value:
                return True
            curr = curr.next
        return False


Now let's solve a question from LeetCode using the Linked List. Consider the problem "Remove Nth Node From End of List" (LeetCode #19), where we need to remove the nth node from the end of a linked list.


def remove_nth_from_end(head, n):
    # Create a dummy node as the new head
    dummy = Node(0)
    dummy.next = head
    
    # Find the length of the linked list
    length = 0
    curr = head
    while curr is not None:
        length += 1
        curr = curr.next
    
    # Find the node before the nth node from the end
    target = length - n
    curr = dummy
    for _ in range(target):
        curr = curr.next
    
    # Remove the nth node by updating the next reference
    curr.next = curr.next.next
    
    return dummy.next


In this example, we create a dummy node as the new head to handle the case where the first node needs to be removed. We then calculate the length of the linked list by traversing it once. Next, we find the node before the nth node from the end by traversing from the dummy node. Finally, we remove the nth node by updating the next reference of the previous node. We return the modified linked list.

The time complexity of the remove_nth_from_end function is O(N), where N is the number of nodes in the linked list. We need to traverse the linked list twice - once to calculate the length and once to find the target node. The space complexity is O(1) as we only use a constant amount of additional space.

 

Next Post Previous Post