Why does linked list delete and insert operation have complexity of O(1) ?

The complexity of delete and insert operations in a linked list can be $$O(1)$$ under specific conditions. Here’s a detailed explanation:

Insertion in a Linked List

1. Insertion at the Head:

   • When inserting a new node at the beginning of the list, the operation is straightforward. You simply adjust the pointers:
     java Copy

     newNode.next = head;
     head = newNode;

   • This operation does not require any traversal of the list, making it $$O(1)$$ [6].

2. Insertion at the Tail:

   • If you maintain a reference to the tail node, inserting at the end of the list is also $$O(1)$$. You just need to update the next pointer of the current tail and then update the tail reference:
     java Copy

     tail.next = newNode;
     tail = newNode;

   • This avoids the need to traverse the list to find the last node, ensuring constant time complexity [5].

3. Insertion at a Given Position:

   • If you already have a reference to the node after which you want to insert the new node, the insertion is $$O(1)$$. You only need to adjust a couple of pointers:
     java Copy

     newNode.next = currentNode.next;
     currentNode.next = newNode;

   • This operation does not involve any traversal, making it constant time [3].

Deletion in a Linked List

1. Deletion of the Head Node:

   • Deleting the first node is a simple operation where you just update the head pointer to the next node:
     java Copy

     head = head.next;

   • This operation is $$O(1)$$ because it does not require any traversal [6].

2. Deletion of a Given Node:

   • If you have a reference to the node to be deleted (and it is not the tail), you can perform the deletion in $$O(1)$$ by copying the data from the next node to the current node and then bypassing the next node:
     java Copy

     nodeToDelete.data = nodeToDelete.next.data;
     nodeToDelete.next = nodeToDelete.next.next;

   • This effectively ...