Re: Destructively merging two LinkedLists
On 1/10/2011 8:05 AM, raphfrk@gmail.com wrote:
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.
--
Eric Sosman
esosman@ieee-dot-org.invalid