1
$\begingroup$

I have a linked list in which I have kept the elements in order (increasing/decreasing). I want to be able to perform a binary search on this linked list. For this I am keeping pointers to the middle element of list of length n, n/2, n/4 so on. I am not able to figure out what would be the order of storage in this case. Any ideas?

$\endgroup$
1
$\begingroup$

Let $T(n)$ be the number of middle-of-list pointers you need to store for a list of length $n$. For a list of length $n$, you need to store one pointer to the middle, plus however many middle-of-list pointers you need for the first half, plus however many you need for the second half. This gives $$T(n) = 1 + 2T(n/2)\,,$$ and we can take $T(1) = 0$, since a list of length $1$ probably doesn't need a middle-of-list pointer.

We have a reference question on formally solving recurrences like this but, for a rough-and-ready approach, we see that $T(2)=1$, $T(4)=3$, $T(8)=7$ so it's pretty clear that $T(n)=O(n)$ and, more to the point, $T(n)$ is about equal to $n$.

Well, now we wonder if a linked list was really the right data structure to be using. First off, programming a linked list with middle-of-list pointers seems to be quite difficult. Appending an item to the list sounds like it'll be awkward because you have all those pointers to update. Actually, I'm not sure what the data structure would even look like. But, anyway, maintaining the middle-of-list pointers costs us time so we'd better hope get something back for our investment of time, such as a saving in space. Nope. Storing the linked list needs about $n$ "next" pointers and about $n$ middle of list pointers, for a total of about $2n$. But just storing your data in a binary tree would require $n$ nodes, each with a pointer to the left child and one to the right child, again giving a total of $2n$ pointers.

$\endgroup$
0
$\begingroup$

You have just described the order. First you include the middle of the list. Then the middles of the two halves. And so on. That's the same storage convention as a heap: the children of node number $x$ are $2x$ and $2x+1$, assuming the first element is $1$. Let's see what this means for $n = 7$. The middle of the list is element 4, in binary 100. The middle of the first half is 2, in binary 010, and of the second half 6, in binary 110. Finally we have 001,011,101,111. The order in binary is $$ 100,010,110,001,011,101,111. $$ See if you can figure out a pattern.

$\endgroup$

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.