Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Wed Oct 12 2005 01:11 am


On Tue, 11 Oct 2005, DV wrote:
> Thad Smith wrote:
>> DV wrote:
>>> Thad Smith wrote:
>>>>
>>>> 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.
>
> 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.

   You can have lists of things that aren't comparable, but you can't 
"merge" two lists unless their elements are all comparable. Think of 
the sorting algorithm known as "mergesort" --- one of its steps is to 
"merge" two halves of the sorted list.
   What you're describing is known as "concatenating" the lists, or 
"appending" the second list onto the first.

HTH,
-Arthur

.