Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Michael Jørgensen
Date : Wed Oct 12 2005 10:20 am


"DV" <dreamvigile@hotmail.com> wrote in message
news:1128968328.414511.150270@g49g2000cwa.googlegroups.com...
> 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.
>
> It seems like if you take the arraylike properties, you are forced to
> forfeit the linkedlistlike properties...  it would be extremely nice to
> have some data structure that has both :/

How about an ordinary doubly linked list, where you keep *three* pointers
and a length. The third pointer will simply point to the middle of the list.
It should be possible to update this pointer in constant time, given that
you know the length of the list, PROVIDED you additionally know whether the
element you're add/deleting is to the left or the right of the middle
element. All this could be achieved using iterators.

-Michael.

.