Table of Content

• Complexity Analysis of Insertion at the Beginning of Linked List
• Complexity Analysis of Insertion at the End of Linked List
• Complexity Analysis of Insertion at a Specific Position of Linked List
• Complexity Analysis of Deletion at the Beginning of Linked List
• Complexity Analysis of Deletion at the End of Linked List
• Complexity Analysis of Deletion at a Specific Position of Linked List
• Complexity Analysis of Search for a Value of Linked List

Operation	Time Complexity	Auxiliary Space	Explanation
Insertion at Beginning	O(1)	O(1)	Constant-time pointer updates.
Insertion at End	O(n)	O(1)	Traversal required to find the last node.
Insertion at Position	O(n)	O(1)	Traversal to the desired position, then constant-time pointer updates.
Deletion at Beginning	O(1)	O(1)	Constant-time pointer update.
Deletion at End	O(n)	O(1)	Traversal required to find the second last node.
Deletion at Position	O(n)	O(1)	Traversal to the desired position, then constant-time pointer updates.
Searching in Linked list	O(n)	O(1)	Traversal through the list to find the desired value.

Let’s look at time and auxiliary space complexity of each of these above operations in detail.

Complexity Analysis of Insertion at the Beginning of Linked List

• Time Complexity: O(1)
  • Reason: Inserting a node at the beginning involves the following steps:
    1. Create a new node.
    2. Set the next pointer of new node to the current head.
    3. Update the head to point to the new node.

  These operations involve only a few pointer manipulations, which take constant time regardless of the size of the list.

• Auxiliary Space: O(1)
  • Reason: The space required for the operation is constant because only one new node is created, and no additional data structures or memory proportional to the input size are needed.

Complexity Analysis of Insertion at the End of Linked List

• Time Complexity: O(n)
  • Reason: Inserting a node at the end requires:
    1. Traversing the entire list to find the last node (which takes O(n) time where n is the number of nodes).
    2. Setting the next pointer of the last node to the new node.
    3. Optionally, updating the last node to point to null if needed.

  The traversal dominates the time complexity, making it linear in relation to the number of nodes.

• Auxiliary Space: O(1)
  • Reason: Only one new node is created, and no extra space proportional to the input size is needed.

Complexity Analysis of Insertion at a Specific Position of Linked List

• Time Complexity: O(n)
  • Reason: Inserting at a specific position involves:
    1. Traversing the list to the node just before the desired position (which can take O(n) time in the worst case).
    2. Creating a new node.
    3. Setting the new node’s next pointer to the next node in the list.
    4. Updating the previous node’s next pointer to point to the new node.

  The traversal step dominates the time complexity.

• Auxiliary Space: O(1)
  • Reason: Only one new node is created, and no additional memory proportional to the list size is required.

Complexity Analysis of Deletion at the Beginning of Linked List

• Time Complexity: O(1)
  • Reason: Deleting the first node involves:
    1. Updating the head pointer to point to the next node.

  This is a constant-time operation as it only involves updating a single pointer.

• Auxiliary Space: O(1)
  • Reason: No additional memory is required for this operation.

Complexity Analysis of Deletion at the End of Linked List

• Time Complexity: O(n)
  • Reason: Deleting the last node requires:
    1. Traversing the entire list to find the second-to-last node (which takes O(n) time).
    2. Updating the second-to-last node’s next pointer to null.

  The traversal step dominates the time complexity.

• Auxiliary Space: O(1)
• Reason: No additional memory is required for this operation.

Complexity Analysis of Deletion at a Specific Position of Linked List

• Time Complexity: O(n)
  • Reason: Deleting a node at a specific position involves:
    1. Traversing the list to the node just before the one to be deleted (which can take O(n) time in the worst case).
    2. Updating the previous node’s next pointer to bypass the node to be deleted and point to the next node.

  The traversal step dominates the time complexity.

• Auxiliary Space: O(1)
• Reason: No additional memory is required for this operation.

Complexity Analysis of Search for a Value of Linked List

• Time Complexity: O(n)
  • Reason: Searching for a value involves:
    1. Traversing the list node by node until the desired value is found or the end of the list is reached.

  In the worst case, the entire list must be traversed, making the time complexity linear.

• Auxiliary Space: O(1)
  • Reason: No additional memory is required for this operation.