Consider an implementation of unsorted singly linked list. Suppose it has its…
2023
Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
- A.
I and II
- B.
I and III
- C.
I, II and III
- D.
I, II and IV
Attempted by 279 students.
Show answer & explanation
Correct answer: B
Answer: b
Explanation: We know the head node in the given linked list. Insertion and deletion of elements at the front of the linked list completes in O (1) time whereas for insertion and deletion at the last node requires to traverse through every node in the linked list.
Suppose there are n elements in a linked list, we need to traverse through each node. Hence time complexity becomes O(n).