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

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

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

  • a- > b- > c- > e- > f- > g
  • a- > b- > c- > g- > f- > e
  • c- > b- > a- > e- > f- > g
  • c- > b- > a- > g- > f- > е

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

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

  • Возможно ли это с другими коллекционными библиотеками?
  • как выполнить обратное?

Ответы

Ответ 1

Если вы готовы согласиться на результат 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)

Ответ 2

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

public EnhancedList (List l1, List l2)

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

Ответ 3

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

Ответ 4

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

  • элемент метода() и заголовок и размер переменных и внутренняя запись класса будут защищены.

  • 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;

Ответ 5

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

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

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

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

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

Ответ 6

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

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