Linked List - Dynamic Implementation

Problem

Implement basic linked list operations: insert, delete, and reverse.

Solution

Linked List Implementation

Basic linked list with insert, delete, and reverse operations

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_end(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
    
    def delete_node(self, val):
        if not self.head:
            return False
        
        if self.head.val == val:
            self.head = self.head.next
            return True
        
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                return True
            current = current.next
        return False
    
    def reverse(self):
        prev = None
        current = self.head
        
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        
        self.head = prev
    
    def print_list(self):
        current = self.head
        while current:
            print(current.val, end=" -> ")
            current = current.next
        print("None")

# Example usage
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.print_list()  # 1 -> 2 -> 3 -> None

ll.reverse()
ll.print_list()  # 3 -> 2 -> 1 -> None

Read the full article

Detailed explanation on Medium

Read

Time Complexity

Insert at end: O(n) - Need to traverse to the end
Delete: O(n) - Need to find the node to delete
Reverse: O(n) - Need to visit each node once

Key Points

Null pointer checks - Always check for null before accessing next
Head pointer updates - Update head when inserting/deleting first element
Memory management - In C++, remember to delete nodes to prevent memory leaks
Temporary variables - Use temp variables to avoid losing references during operations

Common Operations

Insert at beginning (O(1))
Insert at end (O(n))
Delete by value (O(n))
Reverse (O(n))
Detect cycle (O(n) time, O(1) space with Floyd's algorithm)