The next table shows the time complexity of basic operations for linked lists.

Search Operation

Searching in a linked list involves traversing the list from the beginning until the desired element is found. This operation has a time complexity of O(n) in both the worst and average cases. Unlike arrays, linked lists do not support direct access to elements based on their index, resulting in linear time complexity for searching.

def search_linked_list(head, target):
  
    current = head
    while current:
        if current.val == target:
            return True
        current = current.next
    return False

Insert Operation

Inserting an element into a linked list can be done efficiently by updating only a few pointers. Specifically, we need to update the pointer of the element after which we are inserting the new element, ensuring it points to the new element, and the pointer of the new element must point to the next element in the list. This operation has a time complexity of O(1).

def insert_node(head, val, position):
   
    if position == 0:
        new_node = ListNode(val)
        new_node.next = head
        return new_node
    
    current = head
    for _ in range(position - 1):
        if current is None:
            raise ValueError("Position out of range")
        current = current.next
    
    new_node = ListNode(val)
    new_node.next = current.next
    current.next = new_node
    
    return head

Delete Operation

Just like in inserting operation we need toupdate the pointers of the adjacent nodes to bypass the deleted node. As a result we have O(1) time complexity for deleting operation.

def delete_node(head, target):
    
    # If the list is empty, return None
    if not head:
        return None
    
    # If the target is at the head, move the head to the next node
    if head.val == target:
        return head.next
    
    # Search for the target value while keeping track of the previous node
    prev = head
    current = head.next
    while current:
        if current.val == target:
            prev.next = current.next
            return head
        prev = current
        current = current.next
    
    return head

Note

When inserting or deleting an element in a linked list, the process involves adjusting pointers accordingly. In contrast, when working with arrays, to achieve the same operation, a segment of the array must be rewritten.