86 views
What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.? Please mention the reason of the answer also.
| 86 views
0
From the beginning :- $O(1)$

From the end :- $O(n)$

Is it?
0

@Somdatta Sen

for answering this type of questions, you have to follow GeeksforGeeks site !

If you want to find the 8$^{th}$ element from the beginning of the linked list then

=>you have to move 8 steps from the starting of the link list

=> this requires constant time

=> T.C. = O(1).

------------------------------------------------------------------------------------------------------------------------------

If you want to find the 8$^{th}$ element from the end of the linked list then

=> you have to move till the end of the linked list.......O(n)

=> calculate the position of the 8$^{th}$ element from the end of the linked list .....O(1)

=> then you have to start again from starting of the linked list (since you cannot move backwards in a linked list) and move the pointer till you reach the 8$^{th}$ element from the end of the linked list .....O(n)

=> T.C. = O(n) + O(1) +O(n) = O(n).

OR

=> reverse the linked list .........O(n)

=> find the  8$^{th}$ element from the starting of the reversed linked list.....O(1)

=> T.C. = O(n) + O(1)  = O(n).

OR

keep two pointers, named as first and second,

move the second pointer 8 steps, and stop it !

now until you find second->next = NULL, for each iteration forward first and second pointers simultaneously.

when you reached the end of the list, the first pointer points to the 8$^{th}$ element from the end due to the difference between them is 8 steps.

traversing of linked list takes O(n) time.

by Boss (24.2k points)
edited by
0

you have to move till the end of the linked list.......O(n)

calculate the address of the 8th element from the end of the linked list .....O(1)

how this is possible ?

0
we will know what is value of n when we reach the end. i.e. how many nodes are there in linked list..then in next iteration we can move n-8+1 steps.
0

then this line

calculate the address of the 8th element from the end of the linked list .....O(1)

should be as

calculate the position of the 8th element from the end of the linked list .....O(1)

+1
corrected :)