Combinar dos listas en tiempo constante en Java

Question

¿Alguien sabe si es posible fusionar dos listas (o cualquier colección) en tiempo constante en Java?

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

Es tan fácil de hacer que el uso de listas enlazadas en C ...

Gracias,

Answer 1

Las clases en la biblioteca JDK no son compatibles con este, por lo que yo sé .

Es posible si construyes tu propia implementación de List, que eres libre de hacer, es perfectamente legal. Puede usar LinkedList sy reconocer el caso especial de que la colección que se agregará también es LinkedList.

En la documentación de su clase, que había necesidad de señalar que el objeto añadido se convierte en parte del nuevo objeto, en otras palabras, se pierde una gran cantidad de generalidad. También hay muchas posibilidades de error: Alterar cualquiera de las listas originales (si son mutables) después de la unión le permitiría crear una lista con un espacio en ella, o con dos colas. Además, la mayoría de las otras operaciones no se beneficiarían de su clase pirateada. En otras palabras, a primera vista parece una idea loca.

Tenga en cuenta que "la fusión" listas por lo general tiene diferentes connotaciones; al fusionar listas ordenadas, por ejemplo, uno esperaría que la lista resultante tuviera el mismo orden. De lo que estás hablando al unirte a dos listas vinculadas se lo denomina mejor como "empalme". O tal vez simplemente "unirse".

Answer 2

Si es fácil de hacer con una lista enlazada en C, entonces yo supongo que la clase LinkedList ofrece el mismo rendimiento

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); 

editar: No importa. Parece que LinkedList.addAll (Collection) invoca LinkedList.addAll (int, Collection) que itera a través de la nueva colección.

Answer 3

Puede implementar un "envoltorio" compuesto alrededor de múltiples List s. Para simplificar, he hecho que mi ejemplo sea inmutable, pero siempre se puede implementar add para anexar al "final" List almacenado dentro del objeto compuesto.

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

Answer 4

Usted podría hacer los siguientes pasos: obtener la ListaEnlazada de fuente de Java aquí: LinkedList.java

Luego sobre esta implementación añadir la siguiente función:

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; 
} 

Con este código, el 2 LinkedList será la misma LinkedList, por lo que se fusionará en una. El contenedor LinkedList agregará param LinkedList al final y finalmente el encabezado de LinkedList apuntará al primer y último elemento. En este método, no me importa si una de las dos listas está vacía, así que asegúrese de tener las dos listas con los elementos antes de usarlo o tendrá que verificar y tener cuidado con esto.

Prueba1:

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); 
} 

a cabo:

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

Prueba2 rendimiento:

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); 
} 

fuera:

0.004016 
10.508312