CODEWITHSUNDEEP
algorithmdata-structureslinked-listtime-complexity
Genadi
Genadi

Reputation: 249

Efficiently searching a doubly-linked list for a value with a pointer constraint?

I have been given this problem to solve:

Suppose you're given a doubly-linked list and a pointer to some element of that list. Let's suppose that you want to search the list for some value v, which you know exists somewhere. Using no pointers except p, design an Θ(m)-time algorithm for finding v, where m is the distance between p and the node containing v. Do not modify the input list.

Does anyone have any ideas how to solve this? The only way I can think of doing this destructively modifies the list.

Upvotes: 4

Views: 540

Answers (2)

Bernhard Barker
Bernhard Barker

Reputation: 55619

I think templatetypedef has the correct answer, but the below solution came to mind, based on the original phrasing of the question, which states that the list can't be "destroyed or shuffled", which might imply that modifying it is okay if you can change it back again - even if this is not true, I still think this is an interesting approach.

It can easily be solved with 2 pointers, right? One to go forward and one to go back, moving both at the same time until you the value you're looking for.

Now this is all well and good, except that we're only allowed to have 1 pointer.

If you think about a double linked-list, we know that the previous node's next pointer is just a pointer to the current element, so, if we were to lose it, we could just set it up again.

So we could use p.prev.next as free storage (and p.prev.prev.next, given a similar argument).

So, we could only use one pointer going forward, and store the one going back in p.prev.next, moving it appropriately as we go along.

Some Java-esque pseudo-code ignoring end-of-list checks and not finding it for simplicity (I think it's already complicated enough):

if p.data == v
  return v

p = p.next
p.prev.next = p.prev.prev

while not found
  if p == v || p.prev.next == v
    p.prev.next = p                   // restore p.prev.next
    return v
  p = p.next
  p.prev.next = p.prev.prev.next.prev // set up p.prev.next from p.prev.prev.next
  p.prev.prev.next = p.prev           // restore p.prev.prev.next

Upvotes: 4

templatetypedef
templatetypedef

Reputation: 372992

As a hint: What happens if you take one step forward, two steps back, four steps forward, eight steps back, etc.? How many total steps will it take to find the element?

When doing the analysis, you might find it useful to sum up a geometric series. If it helps, 1 + r + r2 + r3 + ... + rn-1 = (rn - 1) / (r - 1).

Hope this helps!

Upvotes: 5

Related Questions