Complexity Analysis

Operations

vs Array Implementation

Traversal Patterns

Applications

Implementation

class Node:
    def __init__(self, value):
        self.value = value      # Data stored in the node
        self.next = None        # Reference to next node

class LinkedList:
    def __init__(self):
        self.head = None        # Reference to first node
        self.size = 0          # Track number of elements
    
    def insert(self, index, value):
        # Validate index
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        
        # Create new node
        new_node = Node(value)
        
        if index == 0:
            # Insert at head
            new_node.next = self.head
            self.head = new_node
        else:
            # Traverse to position before insertion
            current = self.head
            for i in range(index - 1):
                current = current.next
            
            # Insert the node
            new_node.next = current.next
            current.next = new_node
        
        self.size += 1
    
    def delete(self, index):
        # Validate index
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        
        if index == 0:
            # Delete head
            value = self.head.value
            self.head = self.head.next
        else:
            # Traverse to position before deletion
            current = self.head
            for i in range(index - 1):
                current = current.next
            
            # Get value and update pointer
            value = current.next.value
            current.next = current.next.next
        
        self.size -= 1
        return value
    
    def search(self, value):
        # Linear search through the list
        current = self.head
        index = 0
        
        while current:
            if current.value == value:
                return index
            current = current.next
            index += 1
        
        return -1  # Not found
    
    def access(self, index):
        # Validate index
        if index < 0 or index >= self.size:
            raise IndexError("Index out of bounds")
        
        # Traverse to the index
        current = self.head
        for i in range(index):
            current = current.next
        
        return current.value
    
    def append(self, value):
        # Insert at the end
        self.insert(self.size, value)
    
    def prepend(self, value):
        # Insert at the beginning
        self.insert(0, value)
    
    def get_size(self):
        return self.size
    
    def display(self):
        # Return list of all elements
        elements = []
        current = self.head
        while current:
            elements.append(current.value)
            current = current.next
        return elements