Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Thad Smith
Date : Mon Oct 10 2005 09:45 pm

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

.