Was ist eine Datenstruktur, die O (1) für das Anfügen, Voranstellen und Abrufen von Elementen an einem beliebigen Ort hat?

Question

Ich suche Java-Lösung, aber jede allgemeine Antwort ist auch OK.

Vector/ArrayList ist O (1) für Append und Retrieve, aber O (n) für Prepend.

LinkedList (in Java als doppelt verkettete Liste implementiert) ist O (1) für Append und Prepend, aber O (n) für Retrieval.

Deque (ArrayDeque) ist O (1) für alles oben, kann aber kein Element bei beliebigem Index abrufen.

In meiner Meinung eine Datenstruktur, die die obige Anforderung erfüllen, hat 2 growable Liste innerhalb (eine für Prepend und eine für Append) und speichert auch einen Offset, um zu bestimmen, wo das Element während des Abrufs erhalten.

Answer 1

Sie suchen nach einer doppelendigen Warteschlange. Dies ist so implementiert, wie Sie es in der C++ - STL wünschen, in die Sie indizieren können, aber nicht in Java, wie Sie bemerkt haben. Sie könnten Ihre eigenen aus Standardkomponenten rollen, indem Sie zwei Arrays verwenden und speichern, wo "Null" ist. Dies könnte Speicherverschwendung sein, wenn Sie sich weit von Null entfernt bewegen, aber wenn Sie zu weit kommen, können Sie eine Rebase durchführen und es der Deque erlauben, in ein neues Array zu kriechen.

Eine elegantere Lösung, die bei der Verwaltung von zwei Arrays nicht so viel Geschicklichkeit erfordert, ist das Anlegen eines kreisförmigen Arrays an ein zuvor zugewiesenes Array. Dies würde die Implementierung von push_front, push_back und der Größenanpassung des Arrays dahinter erfordern, aber die Bedingungen für die Größenanpassung und dergleichen wären viel sauberer.

Answer 2

Ihre Idee könnte funktionieren. Wenn dies die einzigen Operationen sind, die Sie unterstützen müssen, dann brauchen Sie nur zwei Vektoren (nennen Sie sie Head und Tail). Voranstellen, an Kopf anhängen und anhängen, an Schwanz anhängen. Um auf ein Element zuzugreifen, wenn der Index kleiner als head.Length ist, dann gebe head [head.Length-1-index] zurück, andernfalls return tail [index-head.Length]. Alle diese Operationen sind eindeutig O (1).

Answer 3

Wenn Sie zu einem Vektor/Arraylist als O anhängen behandeln (1) - die es wirklich nicht, aber vielleicht in der Praxis nahe genug sein -
(EDIT - zu klären - append kann konstante Zeit amortisiert Das heißt, im Durchschnitt wäre die Addition O (1), könnte aber bei Spikes etwas schlechter sein.In Abhängigkeit vom Kontext und den genauen beteiligten Konstanten kann dieses Verhalten tödlich sein.

(Dies ist nicht Java, aber einige erfundene Sprache ...).

Ein Vektor, der "Forward" genannt wird. Ein zweiter Vektor, der "Rückwärts" genannt wird.

Wenn aufgefordert, anzufügen - Forward.Append().

Wenn gefragt, vor - Backwards.Append().

Wenn die Abfrage gefragt -

if (Index < Backwards.Size()) 
{ 
    return Backwards[ Backwards.Size() - Index - 1 ] 
} 
else 
{ 
    return Forward[ Index - Backwards.Size() ] 
} 

(und auch für den Index überprüfen außerhalb der Grenzen ist).

Answer 4

Was Sie wollen, ist eine doppelendige Warteschlange (deque) wie die STL hat, seit Java ArrayDeque fehlt get() aus irgendeinem Grund.Es gab einige gute Vorschläge und Links zu Implementierungen hier:

• Java equivalent of std::deque?

Answer 5

A deque (Deque) implementiert werden können alle diese Operationen in O (1) Zeit zur Verfügung zu stellen, obwohl nicht alle Implementierungen. Ich habe nie das ArrayDeque von Java benutzt, also dachte ich, du würdest Witze darüber machen, dass es keinen Direktzugriff unterstützt, aber du hast absolut Recht - als "reines" Objekt erlaubt es nur einfachen Zugriff an den Enden. Ich kann sehen, warum, aber das ist sicher ärgerlich ...

Für mich ist der ideale Weg, um eine extrem schnelle Deque zu implementieren, eine circular buffer zu verwenden, vor allem, da Sie nur daran interessiert sind, entfernen an der Vorder- und Rückseite. Ich bin mir in Java nicht sofort bewusst, aber ich habe einen in Objective-C als Teil eines Open-Source-Frameworks geschrieben. Sie können den Code entweder unverändert oder als Muster für die Implementierung Ihres eigenen Codes verwenden.

Hier ist eine WebSVN portal to the code und die related documentation. Das echte Fleisch ist in der CHAbstractCircularBufferCollection.m Datei - suchen Sie nach den appendObject: und prependObject: Methoden. Es ist sogar ein benutzerdefinierter Enumerator ("Iterator" in Java) definiert. Die wesentliche Ringpuffer Logik ist ziemlich trivial und wird in diesen drei zentralen #define Makros erfaßt:

#define transformIndex(index) ((headIndex + index) % arrayCapacity) 
#define incrementIndex(index) (index = (index + 1) % arrayCapacity) 
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1) 

Wie Sie in der objectAtIndex: Methode sehen können, alles, was Sie tun, um das n-te Element in einer deque zuzugreifen, ist array[transformIndex(N)]. Beachten Sie, dass ich tailIndex immer auf einen Steckplatz hinter dem letzten gespeicherten Element zeigen, also wenn headIndex == tailIndex, das Array voll ist, oder leer, wenn die Größe 0 ist.

Hoffe, dass hilft. Ich entschuldige mich für die Veröffentlichung von nicht-Java-Code, aber die Frage Autor tat sagen allgemeine Antworten waren akzeptabel.

Answer 6

Hier ist eine Datenstruktur, die O (1) append, prepend, first, last und size unterstützt. Wir können leicht hinzufügen andere Methoden von AbstractList<A> wie delete und update

import java.util.ArrayList; 

public class FastAppendArrayList<A> { 
    private ArrayList<A> appends = new ArrayList<A>(); 
    private ArrayList<A> prepends = new ArrayList<A>(); 

    public void append(A element) { 
     appends.add(element); 
    } 

    public void prepend(A element) { 
     prepends.add(element); 
    } 

    public A get(int index) { 
     int i = prepends.size() - index; 
     return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size()); 
    } 

    public int size() { 
     return prepends.size() + appends.size(); 
    } 

    public A first() { 
     return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size()); 
    } 

    public A last() { 
     return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size()); 
    }