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

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

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

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

Спасибо,

Источник

4 ответа

Решение

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

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

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

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

Источник

Вы можете реализовать Composite "обертку" вокруг нескольких Lists. Для простоты я сделал мой пример неизменным, но вы всегда можете реализовать 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.
}
Источник

Вы можете сделать следующие шаги: получить 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
Источник

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

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

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

list1.addAll(list2);

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

Источник
Другие вопросы по тегам