Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : pete
Date : Tue Oct 11 2005 08:44 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).
> >
> > Thad
> 
> Not if it's a (doubly) linked list; then merging takes constant time.
> It's just pointer manipulation. 

Pretty much everything you do with a linked list,
is just pointer manipulation.
I don't see how a doubley linked list is any different 
from a singley linked list in that regard.

-- 
pete

.