Сторнирование LinkedList - PullRequest
Новая
       59

Сторнирование LinkedList

1 голос
/ 01 ноября 2011

Так что мне нужно перевернуть связанный список в O (N) времени / пространстве.

Эта реализация - то, что я придумал, используя только класс LinkedList в стандартной библиотеке Java (которая не дает мне доступ к самим узлам).

Ответы [ 4 ]

5 голосов
/ 01 ноября 2011

«Лучший способ», о котором вы просите, может использовать тот факт, что класс Java LinkedList имеет методы

  • addFirst
  • addLast
  • removeFirst
  • removeLast

Каждый из них является O (1).

Вы можете получить O (n) время и пространство внесколько способов здесь.Один из таких способов: 

LinkedList<E> b = new LinkedList<E>();
while (!a.isEmpty()) {
    b.addFirst(a.removeFirst());
}
a.addAll(b);

Это делает обращение «на месте» (то есть переменная a всегда ссылается на один и тот же объект).Это эквивалентно использованию стека в качестве временного хранилища (b - это «стек»).

Это время O (n) и пространство O (n), несмотря на уродливое копирование.

3 голосов
/ 01 ноября 2011

Нет, это не так.input.get(idx); само по себе O(idx) во времени, что делает вашу реализацию квадратичной во времени.

Возможно, вы захотите использовать итератор (или еще лучше listIterator).

РЕДАКТИРОВАТЬ: Кроме того, вы можете легко устранить holdPopped с небольшой перестановкой.

holdPopped.add будет тривиально O (1) как во времени и пространстве, так как вы предварительно выделяете пространствоO (n) в пространстве), передавая размер.

IIRC, holdLL.add амортизируется O (1) также во времени и пространстве.Иногда это будет больше, иногда меньше, но общее пространство равно n, поэтому оно должно быть в среднем до O (n).Вы можете упростить анализ, используя holdLL.ensureCapacity.

1 голос
/ 01 ноября 2011

Java API имеет метод для этого, который завершается в O (n): Collections.reverse(List<?> list).Предполагая, что это домашнее задание, вы должны реализовать это самостоятельно, но в реальной жизни вы бы использовали библиотечную функцию.

В качестве альтернативы, вы можете создать обратный декоратор, который делает инверсию O (1).Ниже приведен пример концепции. 

public class ReversedLinkedList<T> extends LinkedList<T> {

  private final LinkedList<T> list;

  public ReversedLinkedList(LinkedList<T> list) {
    this.list = list;
  }

  public Iterator<T> descendingIterator() {
    return list.iterator();
  }

  public Iterator<T> iterator() {
    return list.descendingIterator();
  }

  public T get(int index) {
    int actualIndex = list.size() - index - 1;
    list.get(actualIndex);
  }

  // Etc.
}

Обратите внимание, что обычно (всегда?) Плохая форма - заставлять декоратор расширять конкретный класс.В идеале вы должны реализовать открытый интерфейс и принять параметр конструктора в качестве экземпляра открытого интерфейса.Приведенный выше пример предназначен исключительно для иллюстрации, поскольку в LinkedList реализовано множество интерфейсов (например, «Удаление очереди», «Список» и т. Д.).

Кроме того, вставьте сюда типичный комментарий «Преждевременная оптимизация - это зло» - вам нужно толькосоздайте этот перевернутый класс dequeue в реальной жизни, если ваш список был узким местом.

0 голосов
/ 13 марта 2016

Вы должны всегда проверять apache commons , они имеют более совершенные и гибкие реализации для Связного списка и коллекций в целом;

https://commons.apache.org

А во-вторых, вам будет проще использовать двусвязный список , если вы хотите перевернуть список.

...