Datenstrukturen: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 7: | Zeile 7: | ||
* Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|Generics]]. Ihre Verwendung wird im [[Generic]]-Artikel erklärt. | * Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind [[Generic|Generics]]. Ihre Verwendung wird im [[Generic]]-Artikel erklärt. | ||
* Mit ''Element-Typ'' wird hier der Wert bezeichnet, den der [[CSharp:Enumerator|Enumerator]] bei einer [[CSharp:foreach|foreach]]-Anweisung zurückgibt. | * Mit ''Element-Typ'' wird hier der Wert bezeichnet, den der [[CSharp:Enumerator|Enumerator]] bei einer [[CSharp:foreach|foreach]]-Anweisung zurückgibt. | ||
* Datenstrukturen die auf Arrays basieren besitzen intern eine ''Capacity''. Diese gibt die aktuelle Größe des internen Arrays an. ''Capacity'' ist immer größer bzw. gleich ''Count''. Sollte beim Hinzufügen eines Elements die ''Capacity'' der Struktur überschritten werden, muss diese wachsen. Dazu erzeugt sie intern einen neuen, größeren Array und kopiert alle bis dahin vorhandenen Einträge in diesen neuen Array. Typischerweise ist die neue Größe des Arrays die erste Primzahl, die größer als das Doppelte der alten Capacity ist. | |||
== Laufzeiten und Eigenschaften (nach [http://msdn.microsoft.com/en-us/ MSDN]) == | == Laufzeiten und Eigenschaften (nach [http://msdn.microsoft.com/en-us/ MSDN]) == | ||
Version vom 19. April 2009, 12:15 Uhr
Hinweise
- n entspricht immer dem Count der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
- Falls nicht anders angegeben sind Laufzeiten immer Average Case.
- Alle Links zu den Datenstrukturen zeigen auf die englische Version der MSDN. Diese ist typischerweise vollständiger und genauer als ihre deutsche Übersetzung.
- Die meisten der hier vorgestellten Datenstrukturen (alle außer Hashtable) sind Generics. Ihre Verwendung wird im Generic-Artikel erklärt.
- Mit Element-Typ wird hier der Wert bezeichnet, den der Enumerator bei einer foreach-Anweisung zurückgibt.
- Datenstrukturen die auf Arrays basieren besitzen intern eine Capacity. Diese gibt die aktuelle Größe des internen Arrays an. Capacity ist immer größer bzw. gleich Count. Sollte beim Hinzufügen eines Elements die Capacity der Struktur überschritten werden, muss diese wachsen. Dazu erzeugt sie intern einen neuen, größeren Array und kopiert alle bis dahin vorhandenen Einträge in diesen neuen Array. Typischerweise ist die neue Größe des Arrays die erste Primzahl, die größer als das Doppelte der alten Capacity ist.
Laufzeiten und Eigenschaften (nach MSDN)
...
| Laufzeiten von Methoden | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Add | Remove | ElementAt | Contains | Clear | Count | Element-Typ | Thread-safe | Bemerkungen | |
| HashSet<T> | O(1) O(n) wenn Count + 1 > Capacity |
O(1) | ? | O(1) | O(n) | O(1) | T | Nein | keine Duplikate keine Ordnung |
| LinkedList<T> | O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
T |
Nein |
Ordnung Duplikate |
| List<T> | O(1) O(n) wenn Count + 1 > Capacity |
O(n) |
O(1) |
O(n) |
O(1) |
T |
Nein |
||
| Queue<T> | O(1) O(n) wenn Count + 1 > Capacity |
T |
Nein |
||||||
| Stack<T> | O(1) O(n) wenn Count + 1 > Capacity |
O(1) |
T |
Nein |
|||||
| SynchronizedCollection<T> | O(1) O(n) wenn Count + 1 > Capacity |
O(n) |
O(1) |
O(n) |
O(1) |
T |
Ja |
benutzt intern List<T> | |
...
| Laufzeiten von Methoden | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Add | Remove | ElementAt | Contains | Clear | Count | Element-Typ | Thread-safe | Bemerkungen | |
| Dictionary<TKey, TValue> | O(1) O(n) wenn Count + 1 > Capacity |
O(1) |
O(1) |
Nein |
|||||
| SortedDictionary<TKey, TValue> | O(log n) |
O(log n) |
O(log n) |
Nein |
schneller als SortedList bei unsortierten Daten | ||||
| Hashtable | Read-Only mit einem schreibenden Thread |
||||||||
| SortedList<TKey, TValue> | O(n) |
O(n) |
O(log n) |
Nein |
schneller als SortedDictionary bei vorsortierten Daten | ||||