Datenstrukturen: Unterschied zwischen den Versionen
Aus Das Sopra Wiki
Justus (Diskussion | Beiträge) |
Justus (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 13: | Zeile 13: | ||
{| class="default" | {| class="default" | ||
|- | |- | ||
| class="blank" | <br> | | class="blank" | <br> | ||
! colspan="6" | Laufzeiten von Methoden | ! colspan="6" | Laufzeiten von Methoden | ||
| class="blank" | <br> | | class="blank" | <br> | ||
|- | |- | ||
| class="blank" | <br> | | class="blank" | <br> | ||
! Add | ! Add | ||
! Remove | ! Remove | ||
! ElementAt | ! ElementAt | ||
! Contains | ! Contains | ||
! Clear | ! Clear | ||
! Count | ! Count | ||
! Element-Typ | ! Element-Typ | ||
! [[ThreadSafety|Thread-safe]] | ! [[ThreadSafety|Thread-safe]] | ||
! Bemerkungen | ! Bemerkungen | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>] | ! [http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet<T>] | ||
| O(1)<br>O(n) wenn Count + 1 > Capacity | | O(1)<br>O(n) wenn Count + 1 > Capacity | ||
| O(1) | | O(1) | ||
| ? | | ? | ||
| O(1) | | O(1) | ||
| O(n) | | O(n) | ||
| O(1) | | O(1) | ||
| T | | T | ||
| Nein | | Nein | ||
| class="close" | keine Duplikate<br>keine Ordnung | | class="close" | keine Duplikate<br>keine Ordnung | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList<T>] | ! [http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx LinkedList<T>] | ||
| O(1)<br> | | O(1)<br> | ||
| O(1)<br> | | O(1)<br> | ||
| O(n)<br> | | O(n)<br> | ||
| O(n)<br> | | O(n)<br> | ||
| O(1)<br> | | O(1)<br> | ||
| O(1)<br> | | O(1)<br> | ||
| T<br> | | T<br> | ||
| Nein<br> | | Nein<br> | ||
| class="close" | Ordnung<br>Duplikate<br> | | class="close" | Ordnung<br>Duplikate<br> | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List<T>] | ! [http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx List<T>] | ||
| O(1)<br>O(n) wenn Count + 1 > Capacity<br> | | O(1)<br>O(n) wenn Count + 1 > Capacity<br> | ||
| O(n)<br> | | O(n)<br> | ||
| O(1)<br> | | O(1)<br> | ||
| O(n)<br> | | O(n)<br> | ||
| <br> | | <br> | ||
| O(1)<br> | | O(1)<br> | ||
| T<br> | | T<br> | ||
| Nein<br> | | Nein<br> | ||
| class="close" | <br> | | class="close" | <br> | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue<T>] | ! [http://msdn.microsoft.com/en-us/library/7977ey2c.aspx Queue<T>] | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| T<br> | | T<br> | ||
| Nein<br> | | Nein<br> | ||
| class="close" | <br> | | class="close" | <br> | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack<T>] | ! [http://msdn.microsoft.com/en-us/library/3278tedw.aspx Stack<T>] | ||
| O(1)<br>O(n) wenn Count + 1 > Capacity <br> | | O(1)<br>O(n) wenn Count + 1 > Capacity <br> | ||
| O(1)<br> | | O(1)<br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| <br> | | <br> | ||
| T<br> | | T<br> | ||
| Nein<br> | | Nein<br> | ||
| class="close" | <br> | | class="close" | <br> | ||
|- | |- | ||
! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection<T>] | ! [http://msdn.microsoft.com/en-us/library/ms668265.aspx SynchronizedCollection<T>] | ||
| <br> | | O(1)<br>O(n) wenn Count + 1 > Capacity<br> | ||
| <br> | | O(n)<br> | ||
| <br> | | O(1)<br> | ||
| <br> | | O(n)<br> | ||
| <br> | | <br> | ||
| <br> | | O(1)<br> | ||
| T<br> | | T<br> | ||
| Ja<br> | | Ja<br> | ||
| class="close" | benutzt intern List<T><br> | | class="close" | benutzt intern List<T><br> | ||
|} | |} | ||
Version vom 18. April 2009, 23:32 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 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> | 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> | |||||||||
| SortedDictionary<TKey, TValue> | |||||||||
| Hashtable | |||||||||
| SortedList<TKey, TValue> | |||||||||
