Question

What is the time complexity of deleting an element from the beginning of a linked list?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Hint:

Linked lists excel at insertions and deletions at the beginning (O(1)). Arrays, on the other hand, are slow for these operations (O(n)) because all other elements need to be shifted. However, arrays provide fast random access (O(1)), while linked lists require traversal (O(n)).

Answer 1

The Correct Option is A

In a singly linked list, a pointer (usually calledhead` orstart`) points to the first node of the list.
To delete the first element, the following steps are performed:
1. Check if the list is empty. If it is, there is nothing to delete. 2. Create a temporary pointer to the current head node. 3. Update thehead` pointer to point to the second node in the list (which ishead->next`). 4. Free the memory occupied by the original first node (using the temporary pointer).
Each of these steps (checking, pointer assignment, memory deallocation) takes a constant amount of time, regardless of the total number of elements ('n') in the linked list.
Therefore, the time complexity of deleting an element from the beginning of a linked list is constant time, or O(1).