Java объединяет 2 коллекции в O (1)

Ответ 1

Вы можете создать конкатенированный вид Iterable в O (1), используя один из Guava Iterables.concat:

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

Это позволит вам перебирать все элементы обоих списков как один объект без копирования каких-либо элементов.

Ответ 2

Самое простое решение здесь - это список списков. Значит, вам нужны простые функции обертки, но ничего сложного.

Ответ 3

В теории вы можете объединить 2 связанных списка в O (1), так как все, что вам нужно сделать, это указать последний node первого на первый node второго (при условии, что у вас есть эти ссылки).

Метод коллекции addAll, по-видимому, подразумевает время работы O (n), поскольку они говорят об итераторах. Детали могут быть специфичными для JVM...

Я не думаю, что есть какие-то коллекции, которые будут объединены в O (n). Возможно, вам придется сворачивать самостоятельно.

Ответ 4

Я думаю, что лучше всего было бы создать реализацию List, которая принимает List > в качестве своих аргументов, а затем делегирует. Другими словами, иметь список списков и связать их, чтобы действовать как один список. Когда вы проходите мимо элементов списка 1, вы начинаете смотреть на список 2.

По какой-то причине я думал, что у гуавы есть такой список. Но я не могу найти его в своих javadocs.

Ответ 5

Если вы просто хотите иметь коллекции объектов и объединить их в O (1) раз, и не возражаете реализовать свою собственную структуру данных, тогда самый простой способ сделать это - использовать несбалансированное двоичное дерево: каждый node является либо листом (хранящим значение), либо комбинацией двух деревьев, и вы можете просто реализовать их как два класса с абстрактным суперклассом или интерфейсом. Для извлечения элементов можно использовать обход глубины.

Это по сути то же самое, что и предложение ColinD конкатенации итератора, но больше голых костей.

Уловка заключается в том, что итерация по этой коллекции будет не быть O (n)! Это будет O (n + m), где m - количество слияний, которые вы выполнили (так как каждый из них проходит через node). Это верно как для моего решения, так и для ColinD. Я не знаю, верно ли это для всех возможных решений этой проблемы.

Не обращай внимания на вышеизложенное. Согласно этой схеме каждое слияние добавляет по меньшей мере один элемент, поэтому m < n, и поэтому стоимость итерации по-прежнему равна O (n). (Если вы используете конкатенацию итератора, убедитесь, что вы не часто объединяете пустые итераторы, так как это добавит стоимость.)

Ответ 6

Объединение связанных списков - это действительно O (1), и вы можете рассматривать списки на основе массивов одинаково, т.е. иметь несколько Object [], связанных между собой.

Существуют версии выше, это быстрее, чем ArrayList при удалении/вставке из середины/начала. Итерация практически такая же. Случайный доступ может быть немного медленнее, хотя.

Ответ 7

Я хотел предложить класс CompositeCollection из apache.commons, но, глядя на исходный код, это также выполняется в O (n). Если вам нужно только перебирать элементы и не хотите использовать коллекцию Google, как было предложено ColinD, вы можете легко создать свой собственный композитный итератор, например.

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

Ответ 8

Используя два связанных списка в качестве ваших коллекций и сохраняя указатели на первый и последний элементы каждого списка (оба указателя, возможно, необходимо будет обновить при добавлении/удалении элементов), вы можете объединить оба списка в O (1) - просто подключите последний элемент первого списка к первому элементу второго списка и соответствующим образом настройте первые/последние указатели.

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

К счастью, легко найти реализации связанных списков в Java, поскольку это очень распространенная тема в курсах структуры данных. Например, здесь - я знаю, имена указаны на испанском языке, но код в ListaEncadenada ( "LinkedList" ) и NodoLista ( "ListNode" ) достаточно прост и должен быть понятным, а главное - реализация содержит указатели на первый и последний элементы списка и может быть легко изменена в соответствии с вашими потребностями.