4

We have a linked list of size L, and we want to retrieve the nth to the last element.

Solution 1: naive solution

  • make a first pass from the beginning to the end to compute L
  • make a second pass from the beginning to the expected position

Solution 2: use 2 pointers p1, p2

  • p1 starts iterating from the beginning, p2 does not move.
  • when there are n elements between p1 and p2, p2 starts iterating as well
  • when p1 arrives at the end of the list, p2 is at the expected position

Both solutions seem to have the same time complexity (i.e, 2L - n iterations over list elements) Which one is better?

4
  • Since you didn't define "better," there isn't even a question here. Sep 16, 2013 at 0:59
  • One needs to understand that "big O" complexity is only loosely related to actual performance in many cases, since it ignores additive factors and constant multipliers.
    – Hot Licks
    Sep 16, 2013 at 1:05
  • Solution one is O(2n) => O(n) while Solution two is O(n). Both are linear. But solution two does sound cheaper but in reality is probably the same number of operations. Sep 16, 2013 at 1:13
  • Check this one stackoverflow.com/questions/2598348/…
    – Shafqat
    Aug 22, 2016 at 0:11

4 Answers 4

3

Both those algorithms are two-pass. The second may have better performance for reasonably small n because the second pass accesses memory that is already cached by the first pass. (The passes are interleaved.)

A one-pass solution would store the pointers in a circular buffer or queue, and return the "head" of the queue once the end of the list is reached.

3
  • In your one pass solution, is the queue of size n? If so, there would be n list iterations + L enqueue operations + L-n dequeue operations. Why is it better than the first 2 solutions?
    – usual me
    Sep 16, 2013 at 1:44
  • You never defined "better." Some applications require a one-pass algo. Also, the circular buffer is a discrete object so this would work on a machine with no cache but with random-access memory of different speeds. By the way, comparing number of iterations to number of queue operations is apples to oranges. Sep 16, 2013 at 4:56
  • Check this out: stackoverflow.com/questions/2598348/…
    – Shafqat
    Aug 22, 2016 at 0:12
2

How about using 3 pointers p, q, r and a counter.

Iterate through the list with p updating the counter. Every n nodes assign r to q and q to p

When you hit the end of the list you can figure out how far r is from the end of the list.

You can get the answer in no more than O(L + n)

1

If n << L, solution 2 is typically faster, because of caching, i.e. the memory blocks containing p1 and p2 are copied to the CPU cache once and the pointers moved for a bunch of iterations before RAM needs to be accessed again.

0

Would it not be much cheaper to simply store the length of the linked list in O(1) memory? The only reason you have to do a "first pass" at all is because you don't know the length of your linked list. If you store the length, you could iterate over (|L|-n) elements every time and get retrieve the element easily. For higher values of n in comparison to L, this way would save you substantial amounts of time. For example if n was equal to |L|, you could simply return the head of the list with no iteration at all.

This method uses slightly more memory than your first algorithm since it stores the length in memory, but your second algorithm uses two pointers, whereas this method only uses 1 pointer. If you have the memory for a second pointer, you probably have the memory to store the length of your linked list.

Granted O(|L|-n) is equivalent to O(n) in pure theory, but there are "fast" linear algorithms and then there are "slow" ones. Two-pass algorithms for this kind of problem are slow.

As @HotLicks pointed out in the comments, "One needs to understand that "big O" complexity is only loosely related to actual performance in many cases, since it ignores additive factors and constant multipliers." IMO just go for the laziest method in this case and don't overthink it.

Your Answer

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

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