Knotenverweis in verkettete Liste wie. NET hat, um O (1) Artikel einfügen

Question

.Net LinkedList hat eine nice grundlegende verknüpfte Liste Feature, die mir erlaubt, eine Knotenreferenz, ein "Zeiger" in einer verketteten Liste zu halten sozusagen, und verwenden Sie diese Referenz, um die verknüpfte Liste von dort in einer O (1) -Mode zu navigieren und zu manipulieren. Nämlich:

LinkedList<string> linkedList = new LinkedList<string>(); 
LinkedListNode<string> cur = linkedList.First; 
LinkedListNode<string> rememberThis = null; 
do 
{ 
    if (...) 
     rememberThis = cur; 
} while ((cur = cur.Next) != null); 

if (rememberThis != null) 
    linkedList.AddAfter(rememberThis, "added-value"); 

Ich bin Fehler zu sehen, wie ich das gleiche in Java tun, nämlich

1. Iterieren durch ein LinkedList (dies natürlich O(n))
2. Herstellung der Anmerkung von a Listenknoten
3. verwenden, die Knotenreferenz auch nach weiteren Iteration für O(1) Insertion

Java macht give me access zu einem ListIterator, der mir erlaubt, die Liste um den Gegenstand, an dem ich bin, zu manipulieren, aber ich kann nicht scheinen, weiter zu iterieren, während ich an einem vorherigen Knoten festhalte.

Fehle ich etwas?

Answer 1

Nein, tu das nicht, das wird kaputt gehen. Wenn Sie jemals die LinkedListstrukturell später geändert haben, wird eine ConcurrentModificationException geworfen werden nächste Mal, wenn Sie die ListIterator 's Crusor verschieben, und es gibt keinen Weg darum herum. Dies ist bekannt als fail-fast Verhalten.

Wie auch immer, Iteratoren sollen einen Cursor nicht lange in einer Liste halten. Und derzeit gibt es keine Möglichkeit, einen Cursor an einer bestimmten Position in einer Liste zu halten, einschließlich LinkedList s, für eine lange Zeit, sogar für openjdk 9 ea IIRC. Der Grund dafür kann die Zweideutigkeit sein, wie die vorhandenen Cursor verschoben werden. Dies kann in vielen Situationen offensichtlich sein, aber nicht immer.

Schließlich ist es (fast) unmöglich, es zu einem Superschnitt von LinkedList hinzufügen (Queue, Deque, List) jetzt. (Dies ist eindeutig eine API-Design Schuld!) Sie können Ihre eigene Version von LinkedList erstellen zu implementieren, dass .

Wenn Sie wirklich eine Referenz behalten möchten, irgendwie. Sie müssen die Interna mit Reflexionen hacken, was sich vielleicht gar nicht lohnt.

Answer 2

Fehle ich etwas?

Nr LinkedList # ListItr Klasse nicht Lesezeichen. Sie können also nicht weiter iterieren, während Sie an einem vorherigen Knoten festhalten.
Es gibt keine O (1) Methode addAfter (Node Knoten, E-Element) inVerketteteListe, weil VerketteteListe # Node privat ist. Es gibt add (int Index, E-Element) was O (n) ist. Zu traurig.

Eine Abhilfe ist die Verwendung von 2 ListIterator. Einer läuft weiter, der andere stoppt an der Stelle, an die Sie sich erinnern wollen.Dann können Sie ListIterator # hinzufügen (E e) am Ende, die O (1) ist. Aber der erste kann die Liste nicht ändern, sonst wird der zweite unterbrochen.