Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Thad Smith
Date : Tue Oct 11 2005 09:38 am

DV wrote:

> 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).
> 
> Not if it's a (doubly) linked list; then merging takes constant time.
> It's just pointer manipulation.  

Maybe I don't understand what you mean by merging.  I was thinking of 
two lists of length n, each ordered but with no ordering between list, 
which are then combined to make one ordered list, such as
A = {5,12,13,20,27}
B = {2,4,6,16,29}
merge(A,B) = {2,4,5,6,12,13,16,20,27,29}

Is that what you can do in constant time, given a variable input length?

If you mean combining the two with no relative ordering, that wouldn't 
normally be called a merge.

Thad

.