Datenstrukturen: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
Justus (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 5: | Zeile 5: | ||
* Falls nicht anders angegeben sind Laufzeiten immer Average Case. | * Falls nicht anders angegeben sind Laufzeiten immer Average Case. | ||
* Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung]. | * Alle Links zu den Datenstrukturen zeigen auf die englische Version der [http://msdn.microsoft.com/en-us/ MSDN]. Diese ist typischerweise vollständiger und genauer als ihre [http://msdn.microsoft.com/de-de/ deutsche Übersetzung]. | ||
* Die meisten der hier vorgestellten Datenstrukturen 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. | ||
Version vom 19. April 2009, 11:09 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.
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 | ||||
