9

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..

Victor
  • 3,520
  • 3
  • 38
  • 58

7 Answers7

3

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?

Community
  • 1
  • 1
phlogratos
  • 13,234
  • 1
  • 32
  • 37
3

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

Stephen Connolly
  • 13,872
  • 6
  • 41
  • 63
  • @phlogratos's answered while I was typing mine up. If you can use Guava as a dependency, then please do... Guava has a much more correct and well tested implementation than any you or I could write... though my answer shows you what is going on under the hood in the Guava code – Stephen Connolly Aug 27 '13 at 15:52
  • This solution seems the most practical one till now. I suppose I could use guava, but there is a bunch of coding done already. I am using linkedList exactly because insertions and removals are the main operations ;) – Victor Aug 27 '13 at 15:57
2

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.

Martijn Courteaux
  • 67,591
  • 47
  • 198
  • 287
2

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.

pamphlet
  • 2,054
  • 1
  • 17
  • 27
1

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.

Surveon
  • 729
  • 5
  • 12
  • 2
    But it allocates new entries and copies *all* the references. OP wants (reasonably) to only copy ONE reference. – pamphlet Aug 27 '13 at 14:44
  • 1
    `getLast()` + `addFirst()` will not merge the lists. – arshajii Aug 27 '13 at 14:46
  • 2
    You're right. If the overhead from creating new nodes is an issue, I think the only way to solve it is to create a custom implementation. Java's LinkedList implementation does not expose nodes to client code and I don't think it has any mechanisms for "merging". – Surveon Aug 27 '13 at 14:46
  • I was afraid that was the case – Victor Aug 27 '13 at 14:47
  • You could create a wrapper that just contains the linked lists in some order (maybe in a map) and effectively allows you to manipulate them as a single list. This would remove the need to create new nodes, at the very least. – Surveon Aug 27 '13 at 14:49
  • 2
    Creating your own linked list class that implements AbstractSequentialList would be pretty close to trivial--an hour's work tops. – Jonathan Henson Aug 27 '13 at 14:51
  • Pretty much, what's needed is a method that merges one linked list with another by just connecting the head node of one with the tail node of the second. – Surveon Aug 27 '13 at 14:52
  • I know it would be trivial to make my own, but using as much code from the API is also a concern... to avoid bugs... software engineering and so.. boss is around – Victor Aug 27 '13 at 14:59
  • well, if there is no way, there is no way... I gonna think about the suggestions you guys made. Thank you very much for then BTW – Victor Aug 27 '13 at 15:00
  • If a requirement is to use the Java implementation of LinkedList, you'll have to wrap them somehow in order to provide sequential access through several lists as though they were one. This would effectively mimic what your own implementation would be doing. – Surveon Aug 27 '13 at 15:00
1

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.

Jay
  • 435
  • 3
  • 5
0

import java.util.LinkedList;

public class MergeLinkedList {

public static void main(String[] args) {

    LinkedList<String> mainlist = new LinkedList<String>() ;

    mainlist.add("A");
    mainlist.add("B");

    LinkedList<String> secondlist = new LinkedList<String>() ;

    secondlist.add("C");
    secondlist.add("D");

    mainlist.addAll(secondlist);
    System.out.println(mainlist);
}

}

O/P [A, B, C, D]

you have to use addall();

Amaldev
  • 983
  • 8
  • 10