DS-linked_list

Question

With regard to linked list, which of the following statement is false ?

(A) An algorithm to search for an element in a singly linked list requires 0(n)
operations in the worst case.
(B) An algorithm for deleting the first element in a singly linked list requires 0(n)
operations in the worst case.
(C) An algorithm for finding the maximum value in a circular linked list requires 0(n)
operations.
(D) An algorithm for deleting the middle node of a circular linked list requires 0(n)
operations.

Answer 1

Option b:

We know that inorder to search for an element we have to compare each element until not found and in worst case it would be last so o(n)is true (we cannot apply binary search on linked list /unsorted list so complexity cannot be reduced).

Now in order to delete first element we have to modify head(start) and it will only take some constant time so o(1).

Again for option c we have to search for maximum element and that will take o(n).

Again for going to middle we will have go one after to other node to reach middle and for large value of n we assume complexity o(n).

So option b is false

Answer 2

Option (b). An algorithm for deleting the first element in a singly linked list requires O(1) operations. The start pointer needs to point to the second element in the list. The first element is to be freed afterwards.