Chapter 4: Linked Lists

Question 1

What will be the time complexity when inserting a data element after an element that is being pointed to by a pointer in a linked list?

Solution

It will be O(1), since there is no need to traverse the list to reach the desired location where a new element is to be added. A pointer is pointing to the current location, and a new element can be directly added by linking it.

Question 2

What will be the time complexity when ascertaining the length of the given linked list?

Solution

O(n).

In order to find out the length, each node of the list has to be traversed, which will take O(n).

Question 3

What will be the worst-case time complexity for searching a given element in a singly linked list of length n?

Solution

O(n).

In the worst case, the data element to be searched will be at the end of the list, or will not be present in the list. In that case, there will be a total n number of comparisons, thus...