Datenstrukturen

Hinweise

• 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.
• n entspricht immer dem Count der Datenstruktur, d.h. der Anzahl an Elementen in der Struktur.
• Mit Element-Typ wird hier der Wert bezeichnet, den der Enumerator bei einer foreach-Anweisung zurückgibt.
• ElementAt ist eine spezielle Extension Method. Bei Strukturen die das Interface IList<T> implementieren gibt sie das Element an der angegebenen Position an, ansonsten iteriert sie so oft wie angegeben und gibt das Element an dieser Stelle zurück.
• 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)

ein-elementige Datenstrukturen

	Laufzeiten
	Add	Remove	ElementAt	Contains	Clear	Count	Element-Typ	Thread-safe	Bemerkungen
HashSet<T>	O(1) O(n) wenn Count + 1 > Capacity	O(1)	O(n)	O(1)	O(n)	O(1)	T	Nein	keine Duplikate
LinkedList<T>	O(1)	O(1)	O(n)	O(n)	O(n)	O(1)	T	Nein
List<T>	O(1) O(n) wenn Count + 1 > Capacity	O(n)	O(1)	O(n)	O(n)	O(1)	T	Nein
Queue<T>	O(1) O(n) wenn Count + 1 > Capacity	O(1)	O(n)	O(n)	O(n)	O(1)	T	Nein	Remove und Add sind Deqeue und Enqueue
Stack<T>	O(1) O(n) wenn Count + 1 > Capacity	O(1)	O(n)	O(n)	O(n)	O(1)	T	Nein	Remove und Add sind Pop und Push
SynchronizedCollection<T>	O(1) O(n) wenn Count + 1 > Capacity	O(n)	O(1)	O(n)	O(n)	O(1)	T	Ja	benutzt intern List<T>, hat aber zusätzliche Mechanismen um Thread-safety zu garantieren

zwei-elementige Datenstrukturen

	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