Share
Manchmal möchten Sie die flexible Größenanpassung und Benutzerfreundlichkeit einer verknüpften Liste, aber die direkte Indizierung eines Arrays (konstante Zeit). In diesen Fällen ein Anordnungsliste kann einen angemessenen Mittelweg bieten.
Anordnungsliste ist eine Sammlung, die das implementiert IList Schnittstelle, sondern wird durch ein Array anstelle einer verknüpften Liste gesichert. Wie eine verknüpfte Liste kann eine beliebige Anzahl von Elementen hinzugefügt werden (nur durch den verfügbaren Speicher begrenzt), sie verhalten sich jedoch in allen anderen Punkten wie ein Array.
Die ArrayList-Klasse implementiert das IList Schnittstelle. IList liefert alle Methoden und Eigenschaften von ICollection Sie fügen außerdem direktes Indexieren und indexbasiertes Einfügen und Entfernen hinzu. Im folgenden Codebeispiel werden Stubs mit dem Befehl Implement Interface von Visual Studio 2010 generiert.
Das folgende Codebeispiel enthält außerdem drei Ergänzungen zu den generierten Stubs:
Accentsconagua
T (_items). Dieses Array enthält die Elemente in der Sammlung.Anordnungsliste Klasse, um zu minimieren, wie oft das interne Array neu zugewiesen werden muss.öffentliche Klasse ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): this (0) public ArrayList (int length) if (Länge) < 0) throw new ArgumentException("length"); _items = new T[length]; public int IndexOf(T item) throw new NotImplementedException(); public void Insert(int index, T item) throw new NotImplementedException(); public void RemoveAt(int index) throw new NotImplementedException(); public T this[int index] get throw new NotImplementedException(); set throw new NotImplementedException(); public void Add(T item) throw new NotImplementedException(); public void Clear() throw new NotImplementedException(); public bool Contains(T item) throw new NotImplementedException(); public void CopyTo(T[] array, int arrayIndex) throw new NotImplementedException(); public int Count get throw new NotImplementedException(); public bool IsReadOnly get throw new NotImplementedException(); public bool Remove(T item) throw new NotImplementedException(); public System.Collections.Generic.IEnumerator GetEnumerator() throw new NotImplementedException(); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() throw new NotImplementedException(); Hinzufügen eines Elements zu einem Anordnungsliste Hier zeigt sich der Unterschied zwischen dem Array und der verknüpften Liste. Dafür gibt es zwei Gründe. Das erste ist das eine Anordnungsliste unterstützt das Einfügen von Werten in die Mitte der Sammlung, wohingegen eine verknüpfte Liste das Hinzufügen von Elementen am Anfang oder Ende der Liste unterstützt. Zweitens ist das Hinzufügen eines Elements zu einer verknüpften Liste immer eine O (1) -Operation, das Hinzufügen von Elementen zu einer Anordnungsliste ist entweder eine O (1) - oder eine O (n) -Operation.
Wenn Elemente zur Sammlung hinzugefügt werden, kann das interne Array möglicherweise voll werden. In diesem Fall müssen Sie Folgendes tun:
Die einzige Frage, die wir an dieser Stelle beantworten müssen, ist, wie groß das neue Array werden soll. Die Antwort auf diese Frage wird durch das definiert Anordnungsliste Wachstumspolitik.
Wir werden uns zwei Wachstumsstrategien ansehen, und für jede davon wird untersucht, wie schnell das Array wächst und wie es die Leistung beeinflussen kann.
Es gibt zwei Implementierungen von Anordnungsliste Klasse, die wir online anschauen können: Mono und Rotor. Beide verwenden einen einfachen Algorithmus, der die Größe des Arrays jedes Mal verdoppelt, wenn eine Zuordnung erforderlich ist. Wenn das Array eine Größe von Null hat, ist die Standardkapazität 16. Der Algorithmus ist:
Größe = Größe == 0? 1: Größe * 2;
Dieser Algorithmus hat weniger Zuordnungen und Array-Kopien, verbraucht jedoch im Durchschnitt mehr Speicherplatz als der Java-Ansatz. Mit anderen Worten, es ist darauf ausgerichtet, mehr O (1) -Einsätze zu haben, wodurch die Anzahl der Male reduziert werden muss, zu denen die Sammlung den zeitaufwändigen Zuweisungs- und Kopiervorgang durchführt. Dies geht zu Lasten eines größeren durchschnittlichen Speicherplatzbedarfs und durchschnittlich mehr leeren Array-Slots.
Java verwendet einen ähnlichen Ansatz, vergrößert jedoch das Array etwas langsamer. Der Algorithmus, den das Array vergrößert, ist:
Größe = (Größe * 3) / 2 + 1;
Dieser Algorithmus weist eine langsamere Wachstumskurve auf, was bedeutet, dass auf Kosten von mehr Zuweisungen weniger Speicheraufwand anfällt. Schauen wir uns die Wachstumskurve für diese beiden Algorithmen an Anordnungsliste mit mehr als 200.000 zusätzlichen Artikeln.
Die Wachstumskurve für Mono / Rotor gegenüber Java für 200.000 Artikel In diesem Diagramm sehen Sie, dass der Verdopplungsalgorithmus 19 Zuordnungen benötigte, um die 200.000-Grenze zu überschreiten, wohingegen die langsameren (Java-) Algorithmus-Zuweisungen 30 zum selben Punkt führten.
Also welches ist richtig? Es gibt keine richtige oder falsche Antwort. Das Verdoppeln führt weniger O (n) -Operationen durch, hat aber im Durchschnitt mehr Speicherplatz. Der langsamere Wachstumsalgorithmus führt mehr O (n) -Operationen durch, hat jedoch weniger Speicheraufwand. Für eine allgemeine Sammlung sind beide Ansätze akzeptabel. Ihre Problemdomäne kann spezifische Anforderungen haben, die eine Attraktivität erhöhen, oder Sie müssen möglicherweise einen anderen Ansatz erstellen. Unabhängig von der Vorgehensweise bleiben die grundlegenden Verhaltensweisen der Sammlung unverändert.
Unsere Anordnungsliste Die Klasse verwendet den Verdopplungsansatz (Mono / Rotor).
private void GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Verhalten | Fügt den angegebenen Wert am angegebenen Index in der Auflistung hinzu. Wenn der angegebene Index gleich oder größer als ist Anzahl, eine Ausnahme wird ausgelöst |
| Performance | Auf) |
Beim Einfügen an einem bestimmten Index müssen alle Elemente nach der Einfügemarke um eins nach rechts verschoben werden. Wenn das Backing-Array voll ist, muss es vergrößert werden, bevor die Verschiebung durchgeführt werden kann.
Im folgenden Beispiel gibt es ein Array mit einer Kapazität von fünf Elementen, von denen vier verwendet werden. Der Wert drei wird als drittes Element in das Array eingefügt (Index zwei)..
Das Array vor dem Insert (ein offener Slot am Ende) 
Das Array nach dem Verschieben nach rechts 
Das Array mit dem neuen Element wurde am offenen Steckplatz hinzugefügt public void Insert (int index, T item) if (index> = Count) werfen neue IndexOutOfRangeException (); if (_items.Length == this.Count) this.GrowArray (); // Verschieben Sie alle Elemente nach dem Index um einen Platz nach rechts. Array.Copy (_items, index, _items, index + 1, count - index); _items [index] = item; Count ++;
| Verhalten | Hängt den angegebenen Wert an das Ende der Sammlung an. |
| Performance | O (1) wenn die Array-Kapazität größer als Count ist; O (n) wenn Wachstum notwendig ist. |
public void Add (T item) if (_items.Length == Count) GrowArray (); _items [Count ++] = item;
| Verhalten | Entfernt den Wert am angegebenen Index. |
| Performance | Auf) |
Das Entfernen an einem Index ist im Wesentlichen die Umkehrung des Einfügevorgangs. Das Element wird aus dem Array entfernt und das Array wird nach links verschoben.
Das Array vor dem Wert 3 wird entfernt 
Das Array mit dem Wert 3 wurde entfernt 
Das Array verschob sich nach links und gab den letzten Steckplatz frei public void RemoveAt (int index) if (index> = Count) neue IndexOutOfRangeException () werfen; int shiftStart = index + 1; if (shiftStart < Count) // Shift all the items following index one slot to the left. Array.Copy(_items, shiftStart, _items, index, Count - shiftStart); Count--;
| Verhalten | Entfernt das erste Element in der Sammlung, dessen Wert mit dem angegebenen Wert übereinstimmt. Kehrt zurück wahr wenn ein Wert entfernt wurde. Ansonsten kehrt es zurück falsch. |
| Performance | Auf) |
public bool Remove (T item) für (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Verhalten | Gibt den ersten Index in der Auflistung zurück, dessen Wert dem angegebenen Wert entspricht. Gibt -1 zurück, wenn kein übereinstimmender Wert gefunden wird. |
| Performance | Auf) |
public int IndexOf (T item) für (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Verhalten | Ruft den Wert am angegebenen Index ab oder legt diesen fest. |
| Performance | O (1) |
public T this [int index] get if (index < Count) return _items[index]; throw new IndexOutOfRangeException(); set if (index < Count) _items[index] = value; else throw new IndexOutOfRangeException();
| Verhalten | Gibt "true" zurück, wenn der angegebene Wert in der Auflistung vorhanden ist. Andernfalls wird falsch zurückgegeben. |
| Performance | Auf) |
public bool Enthält (T item) return IndexOf (item)! = -1;
| Verhalten | Liefert ein IEnumerator Instanz, die das Auflisten der Array-Listenwerte in der Reihenfolge vom ersten bis zum letzten ermöglicht. |
| Performance | Die Enumerator-Instanz zurückgeben ist eine O (1) -Operation. Aufzählen jedes Elements ist eine O (n) -Operation. |
Beachten Sie, dass wir uns nicht einfach auf das verschieben können _Artikel Arrays GetEnumerator denn das würde auch die Elemente zurückgeben, die aktuell nicht mit Daten gefüllt sind.
public System.Collections.Generic.IEnumerator GetEnumerator () for (int i = 0; i < Count; i++) yield return _items[i]; System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() return GetEnumerator();
| Verhalten | Entfernt alle Elemente aus der Array-Liste. |
| Performance | O (1) |
Bei der Implementierung gibt es zwei Möglichkeiten klar. Das Array kann in Ruhe gelassen werden oder es kann als Array der Länge 0 neu zugeordnet werden. Diese Implementierung ordnet ein neues Array mit einer Länge von Null neu zu. Ein größeres Array wird zugewiesen, wenn dem Array mit dem Element ein Element hinzugefügt wird Hinzufügen oder Einfügen Methoden.
Öffentliches Void Clear () _items = new T [0]; Zählung = 0;
| Verhalten | Kopiert den Inhalt des internen Arrays von Anfang bis Ende in das bereitgestellte Array, beginnend am angegebenen Arrayindex. |
| Performance | Auf) |
Beachten Sie, dass die Methode nicht einfach auf den Wert verschoben wird _Artikel Arrays Kopieren nach Methode. Dies liegt daran, dass wir nur den Bereich aus dem Index kopieren möchten 0 zu Anzahl, nicht die gesamte Array-Kapazität. Verwenden Array.Copy ermöglicht es uns, die Anzahl der zu kopierenden Elemente anzugeben.
public void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Verhalten | Gibt eine Ganzzahl zurück, die die Anzahl der Elemente in der Auflistung angibt. Wenn die Liste leer ist, ist der Wert 0. |
| Performance | O (1) |
Anzahl ist einfach eine automatisch implementierte Eigenschaft mit einem öffentlichen Getter und privaten Setter. Das tatsächliche Verhalten geschieht in den Funktionen, die den Inhalt der Sammlung bearbeiten.
public int Count erhalten; privates Set;
| Verhalten | Gibt false zurück, da die Auflistung nicht schreibgeschützt ist. |
| Performance | O (1) |
public bool IsReadOnly get return false;
