Share
Soms wilt u de flexibele dimensionering en het gebruiksgemak van een gekoppelde lijst, maar moet u de directe (constante tijd) indexering van een array hebben. In deze gevallen, een ArrayList kan een redelijke middenweg bieden.
ArrayList is een verzameling die de. implementeert IList interface maar wordt gedekt door een array in plaats van een gekoppelde lijst. Net als bij een gekoppelde lijst kan een willekeurig aantal items worden toegevoegd (alleen beperkt door het beschikbare geheugen), maar gedragen zich als een array in alle andere opzichten.
De klasse ArrayList implementeert de IList interface. IList biedt alle methoden en eigenschappen van ICollection terwijl het ook directe indexering en indexgebaseerde invoeging en verwijdering toevoegt. Het volgende codevoorbeeld bevat stubs die zijn gegenereerd met de opdracht Werktuiginterface van Visual Studio 2010.
Het volgende codevoorbeeld bevat ook drie toevoegingen aan de gegenereerde stubs:
Accentsconagua
T (_items). Deze array bevat de items in de verzameling.ArrayList klasse om het aantal keren te minimaliseren dat de interne array opnieuw moet worden toegewezen.public class ArrayList: System.Collections.Generic.IList T [] _items; public ArrayList (): this (0) public ArrayList (int length) if (length < 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(); Een item toevoegen aan een ArrayList is waar het verschil tussen de array en de gekoppelde lijst echt zichtbaar is. Daar zijn twee redenen voor. De eerste is dat een ArrayList ondersteunt het invoegen van waarden in het midden van de verzameling, terwijl een gekoppelde lijst het toevoegen van items aan het begin of einde van de lijst ondersteunt. De tweede is dat het toevoegen van een item aan een gelinkte lijst altijd een O (1) bewerking is, maar items toevoegen aan een ArrayList is een O (1) - of een O (n) -bewerking.
Naarmate items aan de verzameling worden toegevoegd, kan de interne array mogelijk vol raken. Wanneer dit gebeurt, moet het volgende worden gedaan:
De enige vraag die we moeten beantwoorden, is hoe groot de nieuwe array moet worden? Het antwoord op deze vraag wordt bepaald door de ArrayList groeipolitiek.
We zullen kijken naar twee groeibeleid en voor elk daarvan kijken we hoe snel de array groeit en hoe deze de prestaties kan beïnvloeden.
Er zijn twee implementaties van de ArrayList klasse die we online kunnen bekijken: Mono en Rotor. Beiden gebruiken een eenvoudig algoritme dat de omvang van de array verdubbelt telkens als een toewijzing nodig is. Als de array een grootte nul heeft, is de standaardcapaciteit 16. Het algoritme is:
size = size == 0? 1: grootte * 2;
Dit algoritme heeft minder toewijzingen en array-kopieën, maar verspilt gemiddeld meer ruimte dan de Java-benadering. Met andere woorden, het is bevooroordeeld in de richting van meer O (1) invoegingen, wat het aantal keren dat de verzameling de tijdrovende allocatie- en kopieerbewerking moet uitvoeren, vermindert. Dit gaat ten koste van een grotere gemiddelde geheugenvoetafdruk en, gemiddelder, meer lege array-slots.
Java gebruikt een vergelijkbare aanpak, maar groeit de array een beetje langzamer. Het algoritme dat wordt gebruikt om de array te laten groeien is:
grootte = (grootte * 3) / 2 + 1;
Dit algoritme heeft een langzamere groeicurve, wat betekent dat het een voorkeur heeft voor minder overheadkosten ten koste van meer toewijzingen. Laten we eens kijken naar de groeicurve voor deze twee algoritmen voor een ArrayList met meer dan 200.000 items toegevoegd.
De groeicurve voor Mono / Rotor versus Java voor meer dan 200.000 items Je kunt in deze grafiek zien dat het 19 toewijzingen kostte voor het verdubbelingsalgoritme om de 200.000 grens te overschrijden, terwijl het langzamere (Java) algoritme 30 toewijzingen kostte om op hetzelfde punt te komen.
Dus welke is juist? Er is geen goed of fout antwoord. Verdubbeling voert minder O (n) -bewerkingen uit, maar heeft gemiddeld meer geheugenoverhead. Het langzamere groei-algoritme voert meer O (n) -bewerkingen uit maar heeft minder geheugenoverhead. Voor een collectie voor algemeen gebruik is elke benadering aanvaardbaar. Uw probleemdomein kan specifieke vereisten hebben die u aantrekkelijker maken, of waarvoor u mogelijk een andere benadering moet maken. Ongeacht de aanpak die je volgt, blijft het fundamentele gedrag van de verzameling ongewijzigd.
Onze ArrayList klasse gebruikt de verdubbelings (Mono / Rotor) benadering.
private void GrowArray () int newLength = _items.Length == 0? 16: _items.Length << 1; T[] newArray = new T[newLength]; _items.CopyTo(newArray, 0); _items = newArray;
| Gedrag | Voegt de opgegeven waarde toe aan de opgegeven index in de verzameling. Als de opgegeven index gelijk is aan of groter is dan tellen, er wordt een uitzondering gegenereerd |
| Prestatie | Op) |
Invoegen op een specifieke index vereist het verschuiven van alle items na het invoegpunt naar rechts met één. Als de achtergrondarray vol is, moet deze worden gekweekt voordat het schakelen kan worden voltooid.
In het volgende voorbeeld is er een array met een capaciteit van vijf items waarvan er vier in gebruik zijn. De waarde drie wordt ingevoegd als het derde item in de array (index twee).
De array vóór het invoegen (één open slot aan het einde) 
De array na verschuiving naar rechts 
De array met het nieuwe item toegevoegd aan de open slot public void Insert (int index, T item) if (index> = Count) gooi nieuw in IndexOutOfRangeException (); if (_items.Length == this.Count) this.GrowArray (); // Verplaats alle items volgens index één sleuf naar rechts. Array.Copy (_items, index, _items, index + 1, Count - index); _items [index] = item; Count ++;
| Gedrag | Voegt de geleverde waarde toe aan het einde van de verzameling. |
| Prestatie | O (1) wanneer de arraycapaciteit groter is dan Count; O (n) wanneer groei nodig is. |
public void Toevoegen (T item) if (_items.Length == Count) GrowArray (); _items [Tel ++] = item;
| Gedrag | Verwijdert de waarde bij de opgegeven index. |
| Prestatie | Op) |
Verwijderen met een index is in wezen het omgekeerde van de invoegbewerking. Het item wordt uit de array verwijderd en de array wordt naar links verschoven.
De array vóór de waarde 3 is verwijderd 
De array met de waarde 3 verwijderd 
De array verschoof naar links en bevrijdde het laatste slot openbare ongeldige RemoveAt (int index) if (index> = Count) gooi nieuwe IndexOutOfRangeException (); 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--;
| Gedrag | Verwijdert het eerste item in de verzameling waarvan de waarde overeenkomt met de opgegeven waarde. Komt terug waar als een waarde is verwijderd. Anders komt het terug vals. |
| Prestatie | Op) |
public bool Remove (T item) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) RemoveAt(i); return true; return false;
| Gedrag | Retourneert de eerste index in de verzameling waarvan de waarde gelijk is aan de opgegeven waarde. Retourneert -1 als er geen overeenkomende waarde wordt gevonden. |
| Prestatie | Op) |
public int IndexOf (T item) for (int i = 0; i < Count; i++) if (_items[i].Equals(item)) return i; return -1;
| Gedrag | Hiermee wordt de waarde opgehaald of ingesteld op de opgegeven index. |
| Prestatie | 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();
| Gedrag | Retourneert true als de opgegeven waarde in de verzameling aanwezig is. Anders wordt false geretourneerd. |
| Prestatie | Op) |
public bool Bevat (T item) return IndexOf (item)! = -1;
| Gedrag | Retourneert een IEnumerator bijvoorbeeld waarmee de waarden van de arraylijst opgesomd kunnen worden van begin tot einde. |
| Prestatie | Het retourneren van de enumerator-instantie is een O (1) -bewerking. Het opsommen van elk item is een O (n) -bewerking. |
Merk op dat we niet eenvoudigweg kunnen wachten op de _items array GetEnumerator omdat dat ook de items zou retourneren die momenteel niet met gegevens zijn gevuld.
openbare 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();
| Gedrag | Verwijdert alle items uit de arraylijst. |
| Prestatie | O (1) |
Er zijn twee opties bij het implementeren Duidelijk. De array kan alleen worden gelaten of deze kan opnieuw worden toegewezen als een matrix met 0-lengte. Met deze implementatie wordt een nieuwe array opnieuw toegewezen met een lengte van nul. Een grotere array wordt toegewezen wanneer een item aan de array wordt toegevoegd met behulp van de Toevoegen of invoegen methoden.
Publieke leegte Wissen () _items = nieuwe T [0]; Aantal = 0;
| Gedrag | Kopieert de inhoud van de interne array van start tot finish in de opgegeven array vanaf de opgegeven array-index. |
| Prestatie | Op) |
Merk op dat de methode niet eenvoudigweg naar de _items array Kopiëren naar methode. Dit komt omdat we alleen het bereik van de index willen kopiëren 0 naar tellen, niet de volledige arraycapaciteit. Gebruik makend van Array.Copy stelt ons in staat om het aantal te kopiëren items te specificeren.
openbare void CopyTo (T [] array, int arrayIndex) Array.Copy (_items, 0, array, arrayIndex, Count);
| Gedrag | Retourneert een geheel getal dat het aantal items aangeeft dat momenteel in de verzameling is. Als de lijst leeg is, is de waarde 0. |
| Prestatie | O (1) |
tellen is gewoon een automatisch geïmplementeerd eigendom met een openbare vangstof en een privézetter. Het echte gedrag gebeurt in de functies die de inhoud van de verzameling manipuleren.
openbare int graaf krijg; privé set;
| Gedrag | Retourneert false omdat de verzameling niet alleen-lezen is. |
| Prestatie | O (1) |
public bool IsReadOnly krijg return false;
