Löschen Sie ein beliebiges Element aus einer verketteten Liste in O (1) - Java vs C++

Question

In C++, ich würde manchmal Objekte in einer verknüpften Liste speichern. Ich würde das Objekt mit einem Iterator verknüpfen, der auf seine Position zeigt. Mit dem Iterator könnte ich dann das Objekt aus der verknüpften Liste in O (1) -Zeit entfernen. Die Operation ist O (1), weil die Liste nur die Zeiger auf die vorherigen und nächsten Elemente in der Liste aktualisiert. Die C++ - Methode, über die ich rede: http://www.cplusplus.com/reference/list/list/erase/

Gibt es eine Möglichkeit, dies mit der gleichen Komplexität O (1) in Java zu tun?

LinkedList scheint nachfolgende Elemente zu verschieben: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#remove(int)

Vielleicht eine andere Java-Klasse gibt es dies zu erreichen?

Dank

Answer 1

Die Standardbibliothek LinkedList macht Sie das nicht tun lassen. remove(int) muss Elemente nicht verschieben, aber es muss finden den Listenknoten zu entfernen, und das dauert lineare Zeit. Sie könnten einen Iterator verwenden, aber die Java-Iterator-Invalidierung ist viel aggressiver als die C++ - Iterator-Invalidierung. Nach dem Entfernen eines Elements durch einen Iterator, der an diesem Element positioniert ist, werden alle anderen Iteratoren ungültig gemacht.

Sie müssten wahrscheinlich Ihre eigene LinkedList Klasse schreiben.

Answer 2

Niemand hat je gesagt, dass die Manipulation des vorherigen und des nächsten Zeigers O (n) -Zeit in einer Linked List nahm. Es ist das Finden des Elements, das es zu O (n) macht.

Wenn Sie für jedes Element in der Liste einen dieser "Iteratoren" hätten (was nicht so heißen könnte), müssten Sie immer noch jeden dieser "Iteratoren" durchlaufen, um den einen zu finden für irgendein zufälliges Objekt in der Liste. Das ist eine O (n) -Operation.

Sobald Sie das richtige Objekt gefunden haben, ist die Aktualisierung der vorherigen und nächsten Elemente unabhängig von der Anzahl der Elemente, also unabhängig von der Sprache O (n).

Answer 3

Sobald Sie ein Element mit einem Iterator gefunden haben, können Sie remove() darauf aufrufen und das Element in O(1) entfernen. Dies funktioniert jedoch nur, wenn Sie die Liste nicht geändert haben oder eine Liste verwenden, die gleichzeitige Aktualisierungen unterstützt.