Java слияния 2 коллекции в O (1)

Question

Мне нужно объединить две большие коллекции в одну. Какой тип коллекции я могу использовать лучше всего?Мне не нужен произвольный доступ к отдельным элементам.Обычно я выбираю связанный список, однако я не могу объединить 2 связанных списка в Java со средой выполнения O (1), что может быть сделано во многих других языках, поскольку мне придется копировать каждый элемент в новый список.

Редактировать: Спасибо за все ваши ответы.Ваши ответы были очень полезны, и мне удалось выполнить работу.В следующий раз я начну с собственной реализации связанного списка.

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

По сути, это то же самое, что и предложение ColinD о конкатенации итераторов, но более простое.

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

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

Answer 6

Я хотел бы предложить класс 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();
  }
}

Answer 7

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

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

Answer 8

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

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

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