CODEWITHSUNDEEP
javaalgorithmcollectionsmerge
Tiddo
Tiddo

Reputation: 6544

Java merge 2 collections in O(1)

I need to be able to merge 2 large collections into 1. Which collection type can I use best? I don't need random access to the individual elements. Usually I'd go for a linkedlist, however I can't merge 2 linkedlist in Java with a runtime of O(1), which could be done in many other languages, since I'll have to copy each element to the new list.

Edit: Thank you for all your answers. Your answers were all very helpful, and I managed to get the job done. Next time I will use my own implementation of a linked list to begin with.

Upvotes: 41

Views: 7870

Answers (8)

Óscar López
Óscar López

Reputation: 236004

By using two linked lists as your collections, and storing pointers to the first and last element of each list (both pointers would potentially need to be updated when adding/removing items), you can merge both lists in O(1) - simply connect the last element of the first list to the first element of the second list, and adjust the first/last pointers accordingly.

I'm afraid you'd need to roll your own implementation of linked lists in Java, since you don't have direct access to the underlying nodes of LinkedList, and therefore you can't connect the last element of the first list to the first element of the second list.

Luckily, it's easy to find linked list implementations in Java, since it's a very common topic in data structure courses. For instance, here is one - I know, the names are in spanish, but the code in ListaEncadenada ("LinkedList") and NodoLista ("ListNode") is quite simple and should be self-explanatory, and most importantly - the implementation contains pointers to the first and last elements of the list, and can be easily modified to suit your needs.

Upvotes: 1

Kevin Reid
Kevin Reid

Reputation: 43773

If you just want to have collections of objects and merge them in O(1) time, and don't mind implementing your own data structure, then the simplest way to do this is to use an unbalanced binary tree: each node is either a leaf (storing a value) or the combination of two trees, and you can just implement these as two classes with an abstract superclass or interface. A depth-first traversal can be used to extract the elements.

This is essentially the same as ColinD's suggestion of iterator concatenation, but more bare-bones.

The catch is that iterating over this collection will not be O(n)! It will be O(n + m) where m is the number of merges you have performed (since each one is a node to be traversed). This is true both of my solution and ColinD's. I don't know whether it is true for all possible solutions to this problem.

Never mind the above. Under this scheme, every merge adds at least one element, so m < n and so the iteration cost is still O(n). (If you do use iterator concatenation, make sure you're not frequently concatenating empty iterators as that would add cost.)

Upvotes: 2

ColinD
ColinD

Reputation: 110054

You can create a concatenated Iterable view in O(1) using one of Guava's Iterables.concat methods:

Iterable<T> combined = Iterables.concat(list1, list2);

This will allow you to iterate over all the elements of both lists as one object without copying any elements.

Upvotes: 59

Robin
Robin

Reputation: 36611

I wanted to suggest the CompositeCollection class from apache.commons, but looking at the source code this runs in O(n) as well. If you only need to iterate over the elements and do not want to use the Google Collections as suggested by ColinD, you can easily create your own composite iterator, e.g.

public class CompositeCollectionIterator<T> implements Iterator<T>{

  private Iterator<T>[] iterators;
  private int currentIteratorIndex = 0;
  public CompositeCollectionIterator( Collection<T>... aCollections ) {
    iterators = new Iterator[ aCollections.length];
    for ( int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++ ) {
      Collection<T> collection = aCollections[ i ];
      iterators[i] = collection.iterator();
    }
  }

  public boolean hasNext() {
    if ( iterators[currentIteratorIndex].hasNext() ) return true;
    else if ( currentIteratorIndex < iterators.length - 1 ){
      currentIteratorIndex++;
      return hasNext();
    }
    return false;
  }

  public T next() {
    return iterators[currentIteratorIndex].next();
  }

  public void remove() {
    iterators[currentIteratorIndex].remove();
  }
}

Upvotes: 1

bestsss
bestsss

Reputation: 12056

Merging linked lists is indeed O(1), and you can consider array-based lists the same way, i.e. having multiple Object[] linked between.

There are implementations of the above, it's faster than ArrayList when removing/inserting from middle/start. And iteration is virtually the same. Random access can be slightly slower though.

Upvotes: 1

yshavit
yshavit

Reputation: 43391

I think your best best would be to create an implementation of List which takes a List> as its arguments, and then delegates. In other words, have a list of lists, and wire them up to act as one list. When you go past the elements of list 1, you start looking at list 2.

For some reason, I thought guava had such a list. But I can't find it in their javadocs.

Upvotes: 3

hvgotcodes
hvgotcodes

Reputation: 120198

In theory, you can merge 2 linked lists in O(1), since all you have to do is point the last node of the first to the first node of the second (assuming you have those references).

The addAll method of collection seems to imply a running time of O(n), since they are talking about iterators. The details might be JVM specific...

I don't think there are any collections that will combine in O(n). You might have to roll your own.

Upvotes: 10

Voo
Voo

Reputation: 30216

The simplest solution here really is a List of Lists. Means you need some simple wrapper functions, but nothing complicated.

Upvotes: 12

Related Questions