Re: Destructively merging two LinkedLists
On Jan 10, 2:14 pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
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 usua=
lly
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 :).