CODEWITHSUNDEEP
javadata-structureslinked-listtime-complexityreverse
mango
mango

Reputation: 13

Reversing a LinkedList

So I need to reverse a Linked List in O(N) time/space.

This implementation is what I came up with using only the LinkedList class in the Java standard library (which doesn't give me access to the nodes themselves).

Upvotes: 1

Views: 388

Answers (4)

Levent Divilioglu
Levent Divilioglu

Reputation: 11622

You should always check apache commons, they have better and more flexible implementations for the linkedlist and collections in general;

https://commons.apache.org

And secondly, it would be more easy for you to use a doubly linked list if you want to reverse a list.

Upvotes: 0

Ray Toal
Ray Toal

Reputation: 88488

The "better way" you ask of can exploit the fact that the Java LinkedList class has methods

  • addFirst
  • addLast
  • removeFirst
  • removeLast

Each of these are O(1).

You can get O(n) time and space behavior in a few ways here. One such way is:

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

This does the reversal "in place" (that is, the variable a references the exact same object at all times). It is equivalent to using a stack as temporary storage (b is the "stack").

It is O(n) time and O(n) space, despite the ugly copying.

Upvotes: 4

user545680
user545680

Reputation:

The Java API has a method for this that completes in O(n): Collections.reverse(List<?> list). Assuming this is homework you should implement this yourself, but in real life you would use the library function.

Alternatively, you can create a reverse decorator which makes the reversal O(1). An example of the concept is below.

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.
}

Note that it is generally (always?) bad form to make a decorator extend a concrete class. Ideally you should implement the public interface and accept a constructor parameter as an instance of the public interface. The above example is purely for illustration purposes, as the LinkedList happens to implement a lot of interfaces (e.g. Dequeue, List etc).

Also, insert the typical "Premature optimisation is evil" comment here - you would only create this reversed dequeue class in real life if your list was actually a bottleneck.

Upvotes: 1

Matthew Flaschen
Matthew Flaschen

Reputation: 285077

No, it's not. input.get(idx); is itself O(idx) in time, which makes your implementation quadratic in time.

You will probably want to use an iterator (or better yet listIterator).

EDIT: Also, you could easily eliminate holdPopped with a little rearrangement.

holdPopped.add will be trivially O(1) in both time and space since you're pre-allocating space (which is O(n) in space) by passing the size.

IIRC, holdLL.add is amortized O(1) in time and space as well. Sometimes it will be more, sometimes less, but the total space is n, so it should average to to O(n). You can simplify the analysis by using holdLL.ensureCapacity.

Upvotes: 2

Related Questions