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

Question

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

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

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

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

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

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

Answer 1

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

http://google -collections.googlecode.com / SVN / багажник / Javadoc / COM / Google / общие / собирать / 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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

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

2. addAll обнаружит LinkedList и затем выполнит sth.как:

   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

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