Мне нужно объединить 2 больших коллекции в 1. Какой тип коллекции я могу использовать лучше всего? Мне не нужен случайный доступ к отдельным элементам. Обычно я бы пошел на связанный список, однако я не могу объединить 2 связанного списка в Java со временем выполнения O (1), что можно было бы сделать на многих других языках, так как мне придется скопировать каждый элемент в новый список.
Изменить: Спасибо за все ваши ответы. Ваши ответы были очень полезными, и мне удалось выполнить эту работу. В следующий раз я начну использовать собственную реализацию связанного списка.
Вы можете создать конкатенированный вид Iterable в O (1), используя один из Guava Iterables.concat:
Iterable<T> combined = Iterables.concat(list1, list2);
Это позволит вам перебирать все элементы обоих списков как один объект без копирования каких-либо элементов.
Самое простое решение здесь - это список списков. Значит, вам нужны простые функции обертки, но ничего сложного.
В теории вы можете объединить 2 связанных списка в O (1), так как все, что вам нужно сделать, это указать последний node первого на первый node второго (при условии, что у вас есть эти ссылки).
Метод коллекции addAll, по-видимому, подразумевает время работы O (n), поскольку они говорят об итераторах. Детали могут быть специфичными для JVM...
Я не думаю, что есть какие-то коллекции, которые будут объединены в O (n). Возможно, вам придется сворачивать самостоятельно.
Я думаю, что лучше всего было бы создать реализацию List, которая принимает List > в качестве своих аргументов, а затем делегирует. Другими словами, иметь список списков и связать их, чтобы действовать как один список. Когда вы проходите мимо элементов списка 1, вы начинаете смотреть на список 2.
По какой-то причине я думал, что у гуавы есть такой список. Но я не могу найти его в своих javadocs.
Если вы просто хотите иметь коллекции объектов и объединить их в O (1) раз, и не возражаете реализовать свою собственную структуру данных, тогда самый простой способ сделать это - использовать несбалансированное двоичное дерево: каждый node является либо листом (хранящим значение), либо комбинацией двух деревьев, и вы можете просто реализовать их как два класса с абстрактным суперклассом или интерфейсом. Для извлечения элементов можно использовать обход глубины.
Это по сути то же самое, что и предложение ColinD конкатенации итератора, но больше голых костей.
Уловка заключается в том, что итерация по этой коллекции будет не быть O (n)! Это будет O (n + m), где m - количество слияний, которые вы выполнили (так как каждый из них проходит через node). Это верно как для моего решения, так и для ColinD. Я не знаю, верно ли это для всех возможных решений этой проблемы.
Не обращай внимания на вышеизложенное. Согласно этой схеме каждое слияние добавляет по меньшей мере один элемент, поэтому m < n, и поэтому стоимость итерации по-прежнему равна O (n). (Если вы используете конкатенацию итератора, убедитесь, что вы не часто объединяете пустые итераторы, так как это добавит стоимость.)
Объединение связанных списков - это действительно O (1), и вы можете рассматривать списки на основе массивов одинаково, т.е. иметь несколько Object [], связанных между собой.
Существуют версии выше, это быстрее, чем ArrayList при удалении/вставке из середины/начала. Итерация практически такая же. Случайный доступ может быть немного медленнее, хотя.
Я хотел предложить класс 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();
}
}
Используя два связанных списка в качестве ваших коллекций и сохраняя указатели на первый и последний элементы каждого списка (оба указателя, возможно, необходимо будет обновить при добавлении/удалении элементов), вы можете объединить оба списка в O (1) - просто подключите последний элемент первого списка к первому элементу второго списка и соответствующим образом настройте первые/последние указатели.
Я боюсь, вам нужно будет запустить собственную реализацию связанных списков в Java, поскольку у вас нет прямого доступа к базовым узлам LinkedList, и поэтому вы не можете подключить последний элемент первый список для первого элемента второго списка.
К счастью, легко найти реализации связанных списков в Java, поскольку это очень распространенная тема в курсах структуры данных. Например, здесь - я знаю, имена указаны на испанском языке, но код в ListaEncadenada ( "LinkedList" ) и NodoLista ( "ListNode" ) достаточно прост и должен быть понятным, а главное - реализация содержит указатели на первый и последний элементы списка и может быть легко изменена в соответствии с вашими потребностями.