Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Jon Harrop
Date : Tue Oct 11 2005 12:04 am

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.

A balanced binary tree should let you do all of those in O(log n) time.

-- 
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

.