Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : DV
Date : Tue Oct 11 2005 08:27 pm


Thad Smith wrote:
> DV wrote:
>
> > Thad Smith wrote:
> >
>>>(SNIP)
> >>
> >>Merging will take at least O(n).
> >
> > Not if it's a (doubly) linked list; then merging takes constant time.
> > It's just pointer manipulation.
>
> Maybe I don't understand what you mean by merging.  I was thinking of
> two lists of length n, each ordered but with no ordering between list,
> which are then combined to make one ordered list, such as
> A = {5,12,13,20,27}
> B = {2,4,6,16,29}
> merge(A,B) = {2,4,5,6,12,13,16,20,27,29}
>
> Is that what you can do in constant time, given a variable input length?
>
> If you mean combining the two with no relative ordering, that wouldn't
> normally be called a merge.
>
> Thad

Who said anything about ordering?  We can have lists of things that
aren't even _comparable_.  By merging I basically mean concatenating:
in your example above, merge(A,B) would be
{5,12,13,20,27,2,4,5,6,12,13,16,20,27,29}.

When one talks of lists, does that really imply sorting?  I am curious
about this now.  If it does, please let me know, I've probably made an
ass of myself quite a few times if this is the case.  In half a decade
of programming it's been my experience that of all the times one uses
lists, the percent of time when you actually need to sort things is
very minute.  Of course by this I mean just everyday type programming -
I know in sophisticated algorithms people sort like they're crazed sort
addicts ;)

DV

.