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?

|cite|improve this question|||||
$\endgroup$
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)$.

|cite|improve this answer|||||
$\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).

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ Yes, that is what puzzled me too, but this is exactly the question that was asked. $\endgroup$ – Siddharth Thevaril Jan 29 '15 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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