Destructively merging two LinkedLists

[raphfrk]

Is there a method that will merge two linked lists (or other list data
structure that can be combined)?

This should be an O(1) operation. However, addAll() method takes
longer as the array sizes grow. I guess it is iterating through the
2nd list in order to perform the merge.

 

[Eric Sosman]

Is there a method that will merge two linked lists (or other list data
structure that can be combined)?

This should be an O(1) operation. However, addAll() method takes
longer as the array sizes grow. I guess it is iterating through the
2nd list in order to perform the merge.

Moving all the members of listA to listB could in principle be
O(1), but note that this would be a destructive operation, leaving
listA empty. After listB.addAll(listA), all the objects originally
in listA are now in *both* lists, and their "dual citizenship" must
be recorded somewhere. Hence, listB.addAll(listA) is at least an
O(listA.size()) operation.

I'm also a little concerned about the word "merge," which usually
suggests objects with ordered keys. "Merging" two such ordered lists
is at least O(min(listA.size(), listB.size()).

As far as I can see, there's no pre-packaged stealAll() method.
An O(1) version, if it existed, would probably have to be a method
of a particular List implementation and not of List itself, since
it would depend on both the "from" and "to" Lists sharing the same
implementation (so "to" could steal "from's" metadata). If you need
the functionality badly enough, I think you'll need to write your
own List implementation, perhaps with methods like

class RaphfrkList<T> extends AbstractSequentialList<T> {
boolean stealAll(RaphfrkList<? extends T> from) {
// O(1) magic here ...
}
boolean stealAll(Collection<? extends T> from) {
boolean result = addAll(from);
from.clear();
return result;
}
// ...
}

.... so you could steal efficiently from your own implementation, as
well as stealing "routinely" from arbitrary Collections.

 

[Joshua Cranmer]

class RaphfrkList<T> extends AbstractSequentialList<T> {
boolean stealAll(RaphfrkList<? extends T> from) {
// O(1) magic here ...
}
boolean stealAll(Collection<? extends T> from) {

if (from instanceof RaphfrkList)
return stealAll((RaphfrkList)from);

boolean result = addAll(from);
from.clear();
return result;
}
// ...
}

Java does not do dynamic dispatch based on real types of arguments.

 

[raphfrk]

     Moving all the members of listA to listB could in principle be
O(1), but note that this would be a destructive operation, leaving
listA empty.  After listB.addAll(listA), all the objects originally

Yeah, I included "Destructively" in the thread title.

     I'm also a little concerned about the word "merge," which usually
suggests objects with ordered keys.  "Merging" two such ordered lists
is at least O(min(listA.size(), listB.size()).

Fair enough, concatenate might have been a better word to use.

     As far as I can see, there's no pre-packaged stealAll() method..
An O(1) version, if it existed, would probably have to be a method
of a particular List implementation and not of List itself

Right, it would only be useful for certain implementation of the List
type.

If you need
the functionality badly enough, I think you'll need to write your
own List implementation, perhaps with methods like

It should be possible to do it another way.

It just meant that I could use a recursive algorithm to do it, and it
would be easier to code.

Thinking about the problem more, I might even be able to pre-compute
the number of elements.

        class RaphfrkList<T> extends AbstractSequentialList<T> {
            boolean stealAll(RaphfrkList<? extends T> from) {
                // O(1) magic here ...
            }
            boolean stealAll(Collection<? extends T> from) {
                boolean result = addAll(from);
                from.clear();
                return result;
            }
            // ...
        }

More complex than I was looking for .

 

[raphfrk]

     Moving all the members of listA to listB could in principle be
O(1),

Also, thanks for the info.

 

[Eric Sosman]

if (from instanceof RaphfrkList)
return stealAll((RaphfrkList)from);

Java does not do dynamic dispatch based on real types of arguments.

True, if he uses a List (or Queue or Collection or ...) reference
to point to a RaphfrkList object, he'll get the vanilla stealAll().
but if he uses a RaphfrkList reference

RaphfrkList listA = new RaphfrkList();
RaphfrkList listB = new RaphfrkList();
// ...
listA.stealAll(listB);

.... then he'll get the specialized version. (The usual advice to use
interface references in preference to implementation references can
be disregarded, I think, in cases where an implementation-specific
functionality is desired.)

Alternatively, he could decorate the vanilla method:

boolean stealAll(Collection<? extends T> from) {
if (from instanceof RaphfrkList)
return stealAll( (RaphfrkList<? extends T>)from );
//...
}

(Double-check the cast; I'm not at all sure I wrote it correctly.)

 

[Eric Sosman]

Yeah, I included "Destructively" in the thread title.

I noticed the Subject a little late ...

It should be possible to do it another way.

It just meant that I could use a recursive algorithm to do it, and it
would be easier to code.

Perhaps I don't understand your situation, but I don't see how
you'll get an O(1) solution from a recursive algorithm. (I also
don't see how recursion would be helpful -- but, as I say, perhaps
I don't understand your situation.)

Thinking about the problem more, I might even be able to pre-compute
the number of elements.

Now I'm *sure* I don't understand your situation! The concatenated
List will have listA.size() + listB.size() elements, guaranteed, so I
don't see where "might" arises. Are you trying to ensure element
uniqueness? If so, why a List and not a Set? What is the wider
context, the larger problem you're trying to solve?

 

[Tom Anderson]

Perhaps I don't understand your situation, but I don't see how
you'll get an O(1) solution from a recursive algorithm.

Maybe it doesn't recurse very much?

tom

 

[Eric Sosman]

Maybe it doesn't recurse very much?

Damn you! Damn y-- oh, sorry, that's a double re-cursion.