Datenstruktur

Die Art, wie Daten im Speicher abgelegt werden.

Bücher zum Thema bei Amazon.de

Als Datenstruktur bezeichnet man das Konstrukt in einem Programm (bzw. im Speicher, im Programm wird die Struktur lediglich definiert und angewandt), das Daten auf eine gewisse Weise speichert.

Durch den speziellen Aufbau einer bestimmten Datenstruktur versucht man gewünschte Funktionen besonders effizient zu implementieren, wobei man zumeist entweder auf geringen Speicherbedarf oder hohe Geschwindigkeit hin optimiert.

Durch eine falsche Datenstruktur für ein Problem, kann ein Programm um ein Vielfaches länger für die Lösung benötigen als eines, das auf eine für das Problem besser geeignete Datenstruktur zurückgreift.

Beispiel

Speichert man die Telefonbucheinträge einer Stadt (N Stück) irgendwie (=ungeordnet) im Speicher ab, muss man im Extremfall (worst case) alle Einträge (also N) durchgehen, bis man beim gewünschten Eintrag gefunden hat.

Wenn man dieselben Daten in einem sogenannten binären Baum speichert, ist man in ld N (logarithmus dualis = Logarithmus zur Basis 2) Schritten beim gewünschten Eintrag. Bei einem Telefonbuch mit 2 Millionen Einträgen würde man dann knapp 21 Schritte benötigen, man ist bis zu 95.550 Mal schneller.