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

Question

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

Как может я concat два связанных списка в O (1) с Java через jdk1.6, Google или апачский набор свободного городского населения или безотносительно? Например, в jdk существует только addAll метод, который является O (n).

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

a-> b-> c-> электронный> f-> g
a-> b-> c-> g-> f-> e
c-> b-> a-> электронный> f-> g
c-> b-> a-> g-> f-> e

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

Поскольку MicSim указал на Слияние вопроса, два списка в постоянное время в Java связаны, но не реальный дубликат! Теперь вопросы:

действительно ли это возможно с другим набором, освобождает?
как к concat инверсия?

20

java collections linked-list apache-commons guava

задан Community 23 May 2017 в 12:08

6 ответов

Другие вопросы по тегам:

java collections linked-list apache-commons guava

Похожие вопросы:

score 0 · Answer 1

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

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

addAll обнаружит LinkedList и затем делаю что-то. например:

 JdkLinkedList secondList = (JdkLinkedList) secondColl; 
int numNew = secondList.size (); 
if (numNew == 0) return false; 
modCount ++; { {1}} Запись  successor = (index == size? Header: entry (index)); 
Entry  predcessor = successor.previous; 
 // ДАЛЬШЕ ПОЗЖЕ, если обратное 
 
 // соединяем последний элемент этого списка с первым элементом второго списка 
 // связанный список реализован как 'цикл' => header.next == первый элемент второго списка 
Запись  first = secondList.header.next; 
предшественник.next = first; 
first.previous = предшественник; 
 { {1}} // добавляем последний элемент второго списка к остальной части этого списка 
Entry  last = secondList.header; 
successor.previous = last; {{1} } last.next = преемник;

score 0 · Answer 2

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

score 0 · Answer 3

Для concat я бы посоветовал вам сделать следующее:

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

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

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

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

score 0 · Answer 4

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

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

score 6 · Answer 5

Если вы готовы довольствоваться результатом Iterable, вы можете использовать коллекции Google 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)

score 2 · Answer 6

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

public EnhancedList (List l1, List l2)

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