The Gateway to Computer Science Excellence
0 votes
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.
in Programming by (59 points) | 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 !

1 Answer

0 votes
Best answer

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 :)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,390 answers
198,589 comments
105,443 users