Inversion d'une LinkedList

Question

J'ai donc besoin d'inverser une Liste Liée en O/N (temps).

Cette implémentation est ce que j'ai trouvé en utilisant uniquement la classe LinkedList dans la bibliothèque standard Java (qui ne me donne pas accès aux nœuds eux-mêmes).

Answer 1

Non, ce n'est pas le cas. input.get(idx); est lui-même O(idx) dans le temps, ce qui rend votre implémentation quadratique dans le temps. Vous voudrez probablement utiliser un itérateur (ou mieux encore, listIterator).

EDIT: En outre, vous pouvez facilement éliminer holdPopped avec un peu de réarrangement.

holdPopped.add sera trivialement O (1) à la fois dans le temps et dans l'espace puisque vous pré-allouer de l'espace (qui est O (n) dans l'espace) en passant la taille.

IIRC, holdLL.add est amorti O (1) dans le temps et l'espace ainsi. Parfois, ce sera plus, parfois moins, mais l'espace total est n, il devrait donc être moyen de O (n). Vous pouvez simplifier l'analyse en utilisant holdLL.ensureCapacity.

Answer 2

La "meilleure façon" vous demande peut exploiter le fait que la classe Java LinkedList a des méthodes

• addFirst
• addLast
• removeFirst
• removeLast

Chacun ce sont O (1).

Vous pouvez obtenir le comportement du temps et de l'espace O (n) de plusieurs façons ici. Une telle façon est:

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

Cela ne l'inversion « en place » (à savoir les variables a références exactement le même objet en tout temps). Cela équivaut à utiliser une pile comme stockage temporaire (b est la "pile").

C'est l'heure O (n) et l'espace O (n), malgré la copie laide.

Answer 3

L'API Java a une méthode pour cela qui se termine par O (n): Collections.reverse(List<?> list). En supposant que ce soit des devoirs, vous devriez l'appliquer vous-même, mais dans la vraie vie, vous utiliseriez la fonction de la bibliothèque.

Alternativement, vous pouvez créer un décorateur inverse qui fait l'inversion O (1). Un exemple du concept est ci-dessous. Notez qu'il est généralement (toujours?) Mal formulé de faire un décorateur étendre une classe de béton. Idéalement, vous devez implémenter l'interface publique et accepter un paramètre constructeur en tant qu'instance de l'interface publique. L'exemple ci-dessus est uniquement à des fins d'illustration, car LinkedList arrive à implémenter un grand nombre d'interfaces (par exemple, Dequeue, List, etc.).En outre, insérez le commentaire typique "L'optimisation prématurée est mauvaise" ici - vous ne créeriez cette classe de déqueue inversée dans la vraie vie que si votre liste était en fait un goulot d'étranglement.

Answer 4

Vous devriez toujours vérifier communes apache, ils ont une meilleure et mises en œuvre plus souples pour le chaînée et collections en général;

https://commons.apache.org

Et d'autre part, il serait plus facile pour vous d'utiliser une liste chaînée doublement si vous voulez inverser une liste.