2
$\begingroup$

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$.

The answer is given as $O(1)$ and $O(n)$.
What I learnt till now is that searching operation in linked lists takes linear time since it doesn't have indexes like arrays. Then why does searching the $8th$ element would take constant time?
Further explanation for the answer is as follows :

Finding 8th element from beginning requires 8 nodes to be traversed which takes constant time. Finding 8th from end requires the complete list to be traversed.

Can someone explain me the concept behind this?

$\endgroup$

4 Answers 4

1
$\begingroup$

The concept has been explained above by Anders for the 8th element from the beginning.

For the 8th element from the end of the list we can use two pointers. Both of them start from the beginning of the list and then we move one of the two by following 7 nodes so that the two pointers have a difference of 8 nodes (including the nodes where they are pointing to).

From that point and on you iterate so that in every step we move each pointer by one position; first we are moving the pointer that is further ahead of the two. When we can not move that pointer further (say because the next pointer is null), then we stop. At that point, the other pointer is pointing to the 8th element of the list counting from the end.

So, total complexity is the number of assignments that we have performed to the pointers by following the `next' links of the list which is $n + (n-8) = 2n - 8$, which is $O(n)$.

Side note: It is assumed that you have a proper linked list; i.e. not a cycle, but I guess you consider this as a given.

Also note that if you had a doubly-linked list and you also had a pointer for the last node of the list, then you could start from there and start counting backwards. In that case, finding the 8th element from the end of the list, the complexity would be $O(1)$.

$\endgroup$
1
$\begingroup$

If you start from the beginning, it does not matter how big the list is, you have to go through the links a constant number of times no matter what.

n = 100, n = 1000, does not matter, you just have to follow exactly 7 links (independent of n).

$\endgroup$
1
  • $\begingroup$ Yes, that is what puzzled me too, but this is exactly the question that was asked. $\endgroup$ Jan 29, 2015 at 22:35
0
$\begingroup$

It’s a trick question. Finding the k-th number takes O(k). Finding the 8-th item can be done in a constant number of steps so it takes O(1).

But with this kind of question, you are unlikely to do this just once. As an example, if you want the k-th item for each 1 <= k <= n, that only takes O(n) steps. If you want item $k_i$ for each 1 <= k <= n, you sort the $k_i$ in O(n log n), then find all items in O(K) where K is the largest of the $k_i$.

$\endgroup$
-2
$\begingroup$

lets talk of each case one by one: (finding from the start) since question has asked us to find the element from the start and has to reach particulary to a place that is 8 th from the start . actually many of us becomes that we have to traverse the link list a long but actually we dont have to because since it has asked for the only to traverse the count of uptill the 8 th element so whatever be the length of the list we have to end our searchtill the 8 th element only during traverse so no matter how many nodes are given to us but it wont affect our time complexities hence it will take constant time o(1)

(finding the 8 th element from the end) this we can find either we use the formula to get the count of nodes in the linklist and n-l+1 from the beginning is the position of the element from the beginning ,since here we have found that it is linearly dependent on the length *of the list hence it answers with the o(n) or another approach is that we can reverse the list and again traverse to the 8 th element from the beginning in reversing the cost is o(n) and finding the lement from the beginning is o(1)=o(n)o(1)=o(n)

$\endgroup$
3
  • $\begingroup$ very nice explanation $\endgroup$ Oct 1 at 2:25
  • $\begingroup$ What's with the all-caps-rage? Why do You give props to Your own answer? $\endgroup$
    – DirkT
    Oct 3 at 20:42
  • $\begingroup$ please see again my explanation and thank you for your feedback $\endgroup$ Oct 10 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.