Объедините два списка в постоянное время в Java
Кто-либо знает, возможно ли объединить два списка (или какой-либо набор) в постоянное время в Java?
http://www.cppreference.com/wiki/stl/list/splice
Настолько легко сделать то использование связанные списки в C...
Спасибо,
3 ответа
Насколько мне известно, классы в библиотеке JDK не поддерживают это.
Это возможно, если вы создадите свою собственную реализацию List - что вы можете делать свободно, это совершенно законно. Вы можете использовать LinkedList и признать особый случай, когда добавляемая коллекция также является LinkedList .
При документировании вашего класса вам нужно указать, что добавленный объект становится частью нового объекта, другими словами, теряется много общности. Также есть много возможностей для ошибки: изменение любого из исходных списков (если они изменяемые) после присоединения позволит вам создать список с пробелом в нем или с двумя хвостами. Кроме того, ваш взломанный класс не принесет пользы большинству других операций. Другими словами, на первый взгляд это кажется безумной идеей.
Обратите внимание, что «объединение» списков обычно имеет разные коннотации; при объединении отсортированных списков, например, можно было бы ожидать, что результирующий список будет иметь такой же порядок. То, о чем вы говорите о соединении двух связанных списков, на самом деле лучше назвать «сращиванием». Или, может быть, просто «присоединиться».
Вы можете реализовать составную «оболочку» вокруг нескольких Список с. Для простоты я сделал свой пример неизменяемым, но вы всегда можете реализовать add для добавления к «окончательному» списку , хранящемуся в составном объекте.
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.
}
Если это легко сделать со связным списком в C, то я бы предположил, что класс LinkedList предлагает такую же производительность
Все операции выполняются так, как можно было бы ожидать для дважды связного списка. Операции, индексирующие список, обходят список с начала или конца, в зависимости от того, что ближе к указанному индексу.
List list1 = new LinkedList();
list1.add(...);
List list2 = new LinkedList();
list2.add(...);
list1.addAll(list2);
edit: Nevermind. Похоже, что LinkedList.addAll(Collection) вызывает LinkedList.addAll(int, Collection), который выполняет итерации по новой коллекции.