Gibt es eine bekannte Implementierung eines indizierten verlinkten Liste?

Ich glaube nicht, dass es möglich sein wird, zu bekommen O(1) für beide einführen und lookup. Die minute, die Sie hinzufügen, ein array (oder auch Lust, teilbare Vektoren), die Einfügung wird O(n).

Gibt es Möglichkeiten zur Milderung der Schäden in Abhängigkeit vom erwarteten Verhalten Ihrer Liste. Wenn es eine Menge mehr lookups als Insertionen/Deletionen, kann es besser sein, nur Vektoren verwenden (variable-sized-arrays) - diese sind einigermaßen effizient, nicht ganz wie arrays, aber besser als die Traversierung von Listen (da diese Häufig werden Listen von arrays, es ist immer noch technisch traversieren einer Liste, sondern jedes element in der Liste hat in der Regel seine Größe, die macht es effizienter).

Wenn Einfüge-und Löschoperationen sind häufiger, können Sie den index erstellen ein fauler, so dass es nur dann gemacht, wenn erforderlich. Zum Beispiel, eingefügt und gelöscht werden, ändern Sie nur die verlinkten Liste Teil (und markieren Sie den index, wie schmutzig) - nur, wenn jemand versucht, verwenden Sie den index wird es wieder aufgebaut werden und markiert als sauber.

Können Sie noch optimieren, neu erstellen, indem Sie einen Datensatz der erste dirty Eintrag. Dies bedeutet, wenn Sie nur einfügen oder löschen in der letzten Hälfte der Liste, Sie brauchen nicht, um den Wiederaufbau der gesamten index, wenn jemand es benutzen möchte.

Einer Lösung, die ich einmal durchgeführt werden, wurde eine 2D-Liste. Damit meine ich:

        +-----------+    +-----------+    +-----------+
List -> | count = 7 | -> | Count = 4 | -> | Count = 6 | -> null
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [0]    |    |    [7]    |    |   [11]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [1]    |    |    [8]    |    |   [12]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              :                :                :
              :                :                :
              |                |                |
              V                V                V
        +-----------+    +-----------+    +-----------+
        |    [6]    |    |   [10]    |    |   [16]    |
        +-----------+    +-----------+    +-----------+
              |                |                |
              V                V                V
             null             null             null

Während dieses gemacht beiden einfügen und Suche in O(n), die balance war genau richtig. In einem reinen array-Lösung lookup O(1) und einfügen ist O(n). Für einen reinen verkettete Liste, einfügen O(1) (sobald Sie gefunden haben, die Einfügemarke, natürlich, ein Vorgang, der sich O(n)) und lookup O(n).

Die 2D-Liste ist O(n) für beide, aber mit einem geringeren Faktor. Wenn Sie schauen, um fügen, finden Sie in der rechten Spalte einfach durch die Untersuchung der ersten Zeile jeder Spalte ein. Dann Sie sich durch die Spalte selbst, der Suche nach der richtigen Zeile. Dann wird das Element eingefügt wird, und die Zählung für die Spalte erhöht. Ähnliches gilt für Löschungen, obwohl in diesem Fall die Zählung wird verringert, und die gesamte Spalte wird entfernt, wenn seine Zählung null erreicht.

Für ein index-lookup, in den Sie sich durch die Spalten zu finden, die richtige Spalte, dann durchqueren Sie die Elemente in der Spalte zu bekommen, das richtige Element.

Und kann es sogar sein auto-Einstellung, indem Sie versuchen, halten Sie die maximale Höhe und Breite etwa die gleichen.

Wenn ich war die Implementierung einer verketteten Liste, in der Klasse, dachte ich über Optimierung des Zugriffs Zeit, indem 3 zusätzliche Felder: Der Knoten in der Mitte der Liste, wird der index der zuletzt aufgerufenen Knoten und der zuletzt aufgerufenen Knoten selbst.

Abrufen eines Knotens, die durch den index würde ich dann den ersten Blick auf alle verfügbaren Pfade zu erreichen, die den Knoten am gegebenen index und dann entschied sich für die billigste Weg, es zu tun. Die Möglichkeiten wären einfach:

1. Gehen von Anfang an den gewünschten index
2. Gehen von der zuletzt aufgerufenen Knoten an die gewünschte index (vorne)
3. Gehen von der zuletzt aufgerufenen Knoten an die gewünschte index (rückwärts)
4. Ausgehend von der Mitte Knoten an die gewünschte index (vorne)
5. Ausgehend von der Mitte Knoten an die gewünschte index (rückwärts)
6. Die von dem Ende den Knoten an die gewünschte index

Den Pfad mit den kleinsten Unterschied in unseren gewünschten index und wir starten mit index wäre die Günstigste option. Wenn keine Knoten zugegriffen wurde, doch der zuletzt besuchten Knoten gesetzt werden könnte, um den mittleren Knoten. Natürlich mit einer geraden Anzahl von Elementen gibt es keine eigentliche Mitte, also würde ich wählen Sie einfach den Boden von n/2.

Jedenfalls bin ich nie dazu gekommen, tatsächlich umzusetzen, diese Optimierung oder sogar wirklich zu analysieren, aber ich hoffe ich konnte helfen.

Wie etwa eine hash-Tabelle? Sie bekommen O(1) random-Zugriff durch Schlüssel und O(1) einfügen/löschen. Der Haken ist, dass die Einträge nicht geordnet.

Für eine effiziente Umsetzung der bestellten Sequenzen, check-out finger Bäumen. Sie geben Sie O(1) Zugriff auf head und last und O(log n) zufällige Zugang zu inneren Knoten. Einfügen oder löschen am Ende in O(1). Insbesondere die Umkehrung der ein-finger-Baum benötigt Konstante Zeit.

Während ich dont denke, dass kann man ganzzahlige Indizierung, eine Unterlage, hashtable könnte funktionieren, wenn Sie mit 'Referenz -' - Typen.