Существует ли быстрый метод concat для связанного списка в Java?

Question

Как я могу соединить два связанных списка в O(1) с Java через jdk1.6, коллекцию google или apache commons или что-то еще? Например, в JDK есть только метод addAll, который является O(n).

Еще одна особенность, которую мне не хватает, - объединить два списка, где каждый из них может быть в обратном порядке. Для иллюстрации предположим, что два списка a-> b-> c и e-> f-> g могут быть объединены в

1. a-> b-> c-> e-> f-> г
2. a-> b-> c-> g-> f-> е
3. c-> b-> a-> e-> f-> г
4. c-> b-> а-> g-> f-> е

Знаете ли вы о такой реализации списка или я должен реализовать свой собственный связанный список? Также было бы полезно узнать, как настроить существующие решения (например, в jdk LinkedList есть только много закрытых методов). Эти особенности кажутся мне очень очевидными, надеюсь, я не пропускаю что-то глупое.

Как указал MicSim, вопрос " Объединение двух списков в постоянном времени на Java" связан, но не является реальным дубликатом! Теперь вопросы:

1. это возможно с другими коллекционными библиотеками?
2. как конкатать обратное?

Answer 1

Если вы готовы согласиться на результат Iterable, вы можете использовать google-collection Iterables.concat и Iterables.reverse.

http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Iterables.html

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c)

public static <T> Iterable<T> concat(Iterable<? extends T> a,
                                 Iterable<? extends T> b,
                                 Iterable<? extends T> c,
                                 Iterable<? extends T> d)

public static <T> Iterable<T> concat(Iterable<? extends T>... inputs)

public static <T> Iterable<T> concat(Iterable<? extends Iterable<? extends T>> inputs)

Answer 2

Единственное решение, которое я вижу на данный момент, - это реализовать List, сделать конструктор наподобие:

public EnhancedList (List l1, List l2)

и переопределить все методы. В таком решении на самом деле не важно, хотите ли вы объединить LinkedLists или любые другие списки.

Answer 3

Для ознакомления я бы предложил вам сделать следующее:

• Убедитесь, что все ваши параметры / переменные объявлены как List<...> not LinkedList<...>
• Изменить новый LinkedList<...>(); новому ArrayList<...>();
• профиль приложения
• Измените новый ArrayList<...> на новый LinkedList<...>();
• профиль приложения

В зависимости от вашего использования ArrayList может быть значительно быстрее, чем LinkedList. Кроме того, просматривая данные профиля, вы можете увидеть, насколько сильно вы снизили производительность, используя addAll - если он не такой большой, не пытайтесь его "исправить".

Для некоторых вещей ваш опыт работы с другими языками не будет верным. Вы можете обнаружить, что addAll соответствует вашим требованиям в Java.

Если вы хотите написать свой собственный совместимый список, убедитесь, что он соответствует интерфейсу List, затем измените код, измените его профиль и убедитесь, что он работает быстрее. Если это не так, выбросьте его и придерживайтесь стандартных типов списков.

Answer 4

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

Answer 5

Адаптация LinkedList для получения конкатата O(1) в jdk будет работать, если:

1. метод entry() и переменные header и size и внутренний класс Entry будут защищены

2. addAll будет обнаруживать LinkedList и затем делать что-то. лайк:

   JdkLinkedList secondList = (JdkLinkedList) secondColl;
   int numNew = secondList.size();
   if (numNew == 0)  return false;
   modCount++;
   Entry<E> successor = (index == size ? header : entry(index));
   Entry<E> predecessor = successor.previous;
   // TODO LATER if reverse
   
   // connect the last element of this list with the first element of the second list
   // linked list is implemented as a 'cycle' => header.next == first element of second list
   Entry<E> first = secondList.header.next;
   predecessor.next = first;
   first.previous = predecessor;
   
   // append the last element of the second list with the rest of this list
   Entry<E> last = secondList.header;
   successor.previous = last;
   last.next = successor;
   

Answer 6

FastList от javolution - это не готовое решение, но с tail() и head(), довольно близкими к моим любимым.

Я думаю, что trove - это решение, хотя в O (1) нет удобного метода для инвертирования или добавления addAll.