Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : alfps
Date : Tue Oct 11 2005 03:21 am

* DV:
> 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.

For ordinary linked lists the answer is, as far as I know, no.

However, you don't state whether you mean linked lists or list-like
functionality.

If you just mean the functionality, then it's possible that the answer depends
on what subset of list-like functionality you need.


> 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 :/

One such is the cursor gap structure.  It's an array with random read/write
access but insert/delete access only via a logical cursor that can only be
moved sequentially.  The cursor is implemented as an area of unused array
locations, and moving the cursor one step corresponds to copying an element
from one side of that area to the other, hence the name "cursor gap".

However, I don't see how a cursor gap structure could help with your earlier
requirements.

What it does help with is constant time random read/write access combined with
constant time insert/delete, and the cost is that the cursor for insert/delete
can only be moved sequentially, and that memory needs to be allocated for the
maximum size, not just for the current size.

-- 
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

.