Putting two linkedlists together without copying - Java, Using standard API [duplicate]

Question

I have two LinkedList in my code and I need to make one that have both. I will not need this Lists anymore, just the new one, which have all data I need.

I could use .addAll(), but performance is I huge issue and I cant wait to copy,adding references, everything every time..

I am looking for something like we normally do if we create our own linkedlist, just connect the last node from one to the fist from the second.. Is there a way to do that using the LinkedList class from the java api?

---

Merging collections is a different case, although the operation means almost the same, my issue is just regarding performance and just for linkedlists, which normally can do what I need. Also "merging" is kind of an ambiguous term, what I want is just to put then together no matter what order they are, with performance in mind.I am not looking if is possible to merge...

Another thing, my question is just regarding the API, I am not looking for building my own code (boss requirement) and that is why is different from this one: Merge two lists in constant time in Java - not useful answers there either..

Answer 1

If you are using LinkedList then you are most likely not interested in indexed access (since indexed access is slow... but keep in mind that a list only stores references, so for very large lists with few insert/removes you are going to be more memory efficient with an ArrayList as it doesn't need to allocate each node on the heap)

So what you actually want is something that gives you most of the List contract... or maybe not even that.

It could well be that all you want is something that gives you Iterable<String>... if that is the case then you have a very easy life:

public class UberIterable<T> implements Iterable<T> {
  private final List<List<T>> lists;
  public UberIterable(List<T>... lists) {
    this.lists = Arrays.asList(lists); 
  }
  public Iterator<T> iterator() {
    return new Iterator<T>() {
      Iterator<List<T>> metaNext = lists.iterator();
      Iterator<T> next;
      public boolean hasNext() {
        while (true) {
          if (next != null && next.hasNext()) return true;
          if (metaNext.hasNext()) next = metaNext.next(); else return false; 
        }
      }
      public T next() {
        if (!hasNext()) throw new NoSuchElementException();
        return next.next();
      }
      public void remove() {
        throw new UnsupportedOperation();
      }
    }
  }
}

That is a basic implementation that will give you a merged view of many lists. If you want to get more of the contract of List you could repeat the same tricks only with a better implementation of ListIterator which will get a lot of what you are probably after, or finally by extending AbstractList and overriding the appropriate methods with your new ListIterator implementation

Answer 2

If you only want to iterate over the new list and you can replace List with Iterable you can use Guava's Iterable.concat as described here:

Combine multiple Collections into a single logical Collection?

Answer 3

I'm afraid the answer is no. The internal Entry class used by LinkedList is private, and all the public methods exposed by LinkedList work with general collections.

Your use case seems reasonable to me, but this implementation doesn't support it.

Answer 4

I'm afraid that the only way to do this is by using reflections... When you take a look at the source code of LinkedList, you can see that the subclass Entry<E> is private, which is a problem if you want to connect the first and last entries to other entries, in order to merge the list.

Update: Even reflections are not safe (unless you add checks), because Oracle changed the name of the subclass Entry to Node and changed the order of arguments of the constructor! in JDK 7, which is stupid IMHO.

Dirty solution: Do a whole copy paste of the source code and change the private keywords to public. However, I'm not sure this is allowed by Oracle. Check their license.

Answer 5

One way you could go about doing this is by using getLast() to grab the last element off the one of the lists and then use addFirst() on the other in order to add it to the front.

As has been said here, however, addAll() would not be copying anything and could be used just as easily.

If your issue is with the actual instantiation of node objects in the LinkedList, you may need to implement your own version that exposes more of the implementation mechanisms in its API.

Answer 6

why not create a wrapper/proxy class that implements List and contains references to the 2 sublists, then implement the List methods (or at least the ones you need downstream) - a little bit of work but if copying either of the lists is really the issue sounds like it is worth it.