0
$\begingroup$

Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)

|cite|improve this question
$\endgroup$
2
$\begingroup$

Infinite/unbounded in both directions? Zig-zag.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Would that work something like this? - steps in powers of 2 in alternating directions (2 steps left, 4 steps right,.....until we find the element)? $\endgroup$ – Sridhar Sep 10 '17 at 8:32
  • $\begingroup$ @Sridhar No, just keep two pointers, left and right and decrement left and increment right. $\endgroup$ – Pål GD Sep 10 '17 at 14:13
  • $\begingroup$ @PålGD that would work of course, but the question suggested "an element and pointer" in singular. $\endgroup$ – Hendrik Jan Sep 10 '17 at 15:16
  • $\begingroup$ @Sridhar indeed! $\endgroup$ – Hendrik Jan Sep 10 '17 at 15:16
  • $\begingroup$ Thanks for the idea. The complexity would be exponential right? $\endgroup$ – Sridhar Sep 11 '17 at 2:45

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.