CODEWITHSUNDEEP
javamerge
Damien
Damien

Reputation: 1473

Merge two lists in constant time in Java

Does anyone know if it's possible to merge two lists (or any collection) in constant time in Java ?

http://www.cppreference.com/wiki/stl/list/splice

It's so easy to do that using linked lists in C...

Thanks,

Upvotes: 14

Views: 8905

Answers (4)

Eldoran
Eldoran

Reputation: 51

You could do the next steps: get the LinkedList of Java source here: LinkedList.java

Then over this implementation add the next function:

public void concatenate(LinkedList<E> list)
{   
    header.previous.next = list.header.next;
    list.header.next.previous = header.previous;
    list.header.previous.next = header.next;
    header.next.previous = list.header.previous; 
    list.header.next = header.next;
    header.previous = list.header.previous;

    size = size + list.size;
    modCount = modCount + list.modCount + 1;
    list.size = size;
    list.modCount = modCount;
}

With this code, the 2 LinkedList will be the same LinkedList, so you'll merge in one. The container LinkedList will add the param LinkedList at the end and finally the header of both LinkedList will point to the first and last element. In this method I dont care about if one of the two list is empty so make sure you have the two list with elements before use it or you'll have to check and take care about this.

Test1:

public static void main(String[] args)
{
    LinkedList<String> test1 = new LinkedList<String>();
    LinkedList<String> test2 = new LinkedList<String>();
    test1.add("s1");
    test1.add("s2");
    test2.add("s4");
    test2.add("s5");
    test1.concatenate(test2);
    System.out.println(test1);
    System.out.println(test2);
}

out:

[s1, s2, s4, s5]
[s1, s2, s4, s5]

Test2 performance:

public static void main(String[] args)
{
    int count = 100000;
    myutil.LinkedList<String> test1 = new myutil.LinkedListExt<>();
    myutil.LinkedList<String> test2 = new myutil.LinkedListExt<>();
    test1.add("s1");
    test1.add("s2");
    test2.add("s3");
    test2.add("s4");
    for (int i=0; i<count; ++i)
        test2.add("s");

    long start = System.nanoTime();
    test1.concatenate(test2);
    long elapsedTime = System.nanoTime() - start;
    System.out.println(elapsedTime/1000000.0);

    java.util.LinkedList<String> test3 = new java.util.LinkedList<>();
    java.util.LinkedList<String> test4 = new java.util.LinkedList<>();
    test3.add("s1");
    test3.add("s2");
    test4.add("s3");
    test4.add("s4");
    for (int i=0; i<count; ++i)
        test4.add("s");

    start = System.nanoTime();
    test3.addAll(test4);
    elapsedTime = System.nanoTime() - start;
    System.out.println(elapsedTime/1000000.0);
}

out:

0.004016
10.508312

Upvotes: 1

Adamski
Adamski

Reputation: 54705

You could implement a Composite "wrapper" around multiple Lists. For simplicity I've made my example immutable but you could always implement add to append to the "final" List stored within the composite object.

public class CompositeImmutableList<T> implements List<T> {
  private final List<T> l1;
  private final List<T> l2;

  public CompositeImmutableList(List<T> l1, List<T> l2) {
    this.l1 = l1;
    this.l2 = l2;
  }

  public boolean add(T t) {
    throw new UnsupportedOperationException();
  }

  public int size() {
    return l1.size() + l2.size();
  }

  public T get(int i) {
    int sz1 = l1.size();
    return i < s1 : l1.get(i) : l2.get(sz1 - i);
  }

  // TODO: Implement remaining List API methods.
}

Upvotes: 3

matt b
matt b

Reputation: 139931

If it's easy to do with a linked list in C, then I'd guess that the LinkedList class offers the same performance

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

List list1 = new LinkedList();
list1.add(...);
List list2 = new LinkedList();
list2.add(...);

list1.addAll(list2);

edit: Nevermind. Looks like LinkedList.addAll(Collection) invokes LinkedList.addAll(int, Collection) which iterates through the new collection.

Upvotes: 0

Carl Smotricz
Carl Smotricz

Reputation: 67760

The classes in the JDK library don't support this, as far as I know.

It's possible if you build your own implementation of List - which you're free to do, it's perfectly legal. You could use LinkedLists and recognize the special case that the collection to be added is also a LinkedList.

In documenting your class, you'd need to point out that the added object becomes part of the new object, in other words a lot of generality is lost. There's also lots of potential for error: Altering either of the original lists (if they're mutable) after joining would allow you to create a list with a gap in it, or with two tails. Also, most other operations wouldn't benefit from your hacked-up class. In other words, at first blush it seems like a crazy idea.

Note that "merging" lists usually has different connotations; when merging sorted lists, for example, one would expect the resultant list to have the same ordering. What you're talking about with joining two Linked Lists is really better termed as "splicing". Or maybe just "joining."

Upvotes: 13

Related Questions