Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : DV
Date : Mon Oct 10 2005 08:10 pm


Thad Smith wrote:
> DV wrote:
> > Is there a data structure for lists such that a list can be split in
> > half in constant time or its middle element found in constant time
> > (such as an array pointer + size variable) but also such that two lists
> > can be merged in constant time (such as a linked list)?  This isn't a
> > homework problem.
>
> Merging will take at least O(n).
>
> Thad

Not if it's a (doubly) linked list; then merging takes constant time.
It's just pointer manipulation.  But with a linked list it would
strictly require linear time to find the middle element (and thus to
split in half as well).

I thought about my original request some more and I agree with the
reply that it's impossible:  if you gave me such a data structure, I
believe I could give you a (rather complicated!) O(n) sort algorithm.
Which is impossible, right?

Thanks for the feedback, you guys are great
DV

.