Объединение двух списков в постоянное время в Java

Question

Кто-нибудь знает, возможно ли объединить два списка (или любую коллекцию) в постоянное время в Java?

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

Это так легко сделать, используя связанные списки в C ...

Спасибо

Answer 1

Насколько мне известно, классы в библиотеке JDK не поддерживают это.

Это возможно, если вы создадите собственную реализацию List - что вы можете делать свободно, это совершенно законно. Вы можете использовать LinkedList s и распознать особый случай, когда добавляемая коллекция также является LinkedList.

При документировании вашего класса вам нужно указать, что добавленный объект становится частью нового объекта, другими словами, много общности теряется. Существует также много возможностей для ошибки: изменение любого из первоначальных списков (если они изменчивы) после объединения позволит вам создать список с пробелом в нем или с двумя хвостами. Кроме того, большинство других операций не выиграют от вашего взломанного класса. Другими словами, на первый взгляд это кажется сумасшедшей идеей.

Обратите внимание, что списки "слияния" обычно имеют разные значения; например, при объединении отсортированных списков можно ожидать, что результирующий список будет иметь такой же порядок. То, о чем вы говорите, присоединившись к двум связанным спискам, на самом деле лучше называть «объединением». Или, может быть, просто "присоединиться".

Answer 2

Вы можете реализовать Composite «обертку» вокруг нескольких List с. Для простоты я сделал мой пример неизменным, но вы всегда можете реализовать add для добавления к «окончательному» List, хранящемуся в составном объекте.

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 3

Вы можете сделать следующие шаги: получить источник LinkedList из Java здесь: LinkedList.java

Затем над этой реализацией добавьте следующую функцию:

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

С этим кодом 2 LinkedList будет таким же LinkedList, что вы объедините его в один. Контейнер LinkedList добавит параметр LinkedList в конце, и, наконец, заголовок обоих LinkedList будет указывать на первый и последний элемент. В этом методе меня не волнует, если один из двух списков пуст, поэтому перед его использованием убедитесь, что у вас есть два списка с элементами, иначе вам придется проверить и позаботиться об этом.

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

из

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

Тест2 производительности:

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

из

0.004016
10.508312

Answer 4

Если это легко сделать со связанным списком в C, то я предполагаю, что класс LinkedList предлагает такую ​​же производительность

Все операции выполняются, как и следовало ожидать для двусвязного списка. Операции, которые индексируют в списке, будут проходить по списку с начала или конца, в зависимости от того, что ближе к указанному индексу.

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

list1.addAll(list2);

редактировать: Nevermind. Похоже, LinkedList.addAll (Collection) вызывает LinkedList.addAll (int, Collection), который перебирает новую коллекцию.