Bei einer Datenstruktur handelt es sich um eine Menge von Objekten, auf denen eine Reihe von Operationen definiert sind:

1. Datenstruktur = Datenmenge + Operationen

Datenstrukturen stellen die Grundlage für Algorithmen dar, denn gute Algorithmen können nur dann gefunden werden, wenn angemessene Datenstrukturen verwendet werden.

Ein paar Datenstrukturen:

• Keller (stack)
• Warteschlange (queue)
• Baum (tree)
• Ringpuffer (ring buffer)

Je nach Art des Algorithmus werden Varianten und Unterarten gefordert, welche weiteren Anforderungen angepasst werden.

Mit dem sinnvollen Einsatz einer Datenstruktur kann man häufig gewissen Problemen aus dem Wege gehen.

Die meisten Datenstrukturen unterliegen dem modularen Prinzip Information-Hiding (Geheimnisprinzip). Nur mittels den zur Verfügung stehenden Operationen hat der Benutzer Zugriff auf die Datenmenge selbst. Manchmal weiß der Benutzer gar nicht wie die Datenstruktur intern geregelt und aufgebaut ist. In den meisten Fällen ist dies auch nicht erforderlich, wenn Komplexitätsaussagen zu den jeweiligen Operationen hinreichend bekannt sind.
Aufgrund des Geheimnisprinzips kann sich der Algorithmen-Entwickler auf das Wesentliche konzentrieren. Die Details zur Realisierung der benötigten Datenstrukturen müssen nicht zum Thema gemacht werden — besser noch — die Entwicklung dieser Datenstrukturen kann an dritte delegiert werden. Ordentliche Datenstrukturen verfügen deshalb über klar definierte Schnittstellen.

Dabei sei bemerkt, dass Information-Hiding ein allgemeines Prinzip des objektorientierten Designs ist: Jedes Objekt besitzt mindestens ein (Realisierungs-) Geheimnis. Falls ein Objekt kein Geheimnis enthält, kann es auch weggelassen werden (überflüssiges Objekt).

Die Datenstruktur wird über Operationen, die sie selbst zur Verfügung stellt, genutzt bzw. gesteuert.

Viele Programmiersprachen ermöglichen die Definition der Schnittstellen ihrer Module bzw. Klassen mit dem Schlüsselwort Interface (zu deutsch: Schnittstelle). Das Interface bzw. die Schnittstelle legt lediglich fest, wie man auf ein Modul bzw. auf eine Klasse zugreifen kann. Die Implementierung steht an anderer Stelle und kann je nach Bedarf gegen effizientere Implementierungen ausgetauscht werden, wobei das Interface unverändert stets dasselbe bleibt (siehe ANSI-Norm). Dies stellt sich besonders unter den Gesichtspunkten der Aufwärtskompatibilität und der Wartbarkeit der Software als vorteilhaft heraus.

Damit Programmteile isoliert vom Gesamtsystem betrachtet, geändert, getestet und korrigiert werden können, muss der Zugriff auf eine Datenstruktur stets über die dazugehörige Schnittstelle erfolgen. Wenn dies konsequent eingehalten wird, dann können fehlerbereinigte Datenstrukturen aber auch Algorithmen, problemlos in andere Projekte übernommen werden — das Rad musste auch nicht zweimal erfunden werden. :-)

Die Nebenläufigkeit ist ein Begriff in der Informatik, der im Zusammenhang mehrerer gleichzeitig ablaufender Vorgänge auftritt.

• Programme laufen auf bestimmten Betriebssystemen (z. B.: Unix, Windows) augenscheinlich gleichzeitig ab. Das laufende Programm wird als Prozess bezeichnet.
• Innerhalb eines Programms können ebenso Programmteile nebenläufig ablaufen, die sogenannten Kindprozesse oder Programmfäden, die Threads.

Das Betriebssystem entscheidet wieviel Takte bzw. wieviel Zeit ein Prozess bzw. Thread bekommt. Wenn die Zeit für einen Prozess verstrichen ist, kommt es zum Prozesswechsel, ein anderer Prozess kann seine Operationen ausführen, die ihrerseits ebenfalls unvorhersagbar unterbrochen werden können, gleichwohl ob eine Operation beendet wurde oder nicht. Man kann nie vorhersagen, wann oder in welcher Reihenfolge die Prozesse oder Threads auftreten, was eigentlich auch kein größeres Problem darstellen würde, wenn es da nicht gemeinsam genutzte Datenstrukturen gäbe.

Eine Datenstruktur stellt Operationen zur Verfügung, welche wiederum weitere Unteroperationen aufrufen können. Beispielsweise könnte eine Datenstruktur beim Einfügen eines Elements die Einfügeposition suchen und daraufhin an der gefunden Stelle das gegebene Element einfügen, wobei die Positionssuche und das Einfügen an gefundener Stelle wiederum in weitere Operationen zerlegt werden kann.
Kommt es nun bei einer Operation zum Prozesswechsel, stoppt der Ablauf dieser Operation und kann zum späteren Zeitpunkt fortgesetzt werden. Problematisch wird es, wenn nun ein anderer Prozess ebenfalls ein Element in diese Datenstruktur einfügen möchte. Diese Datenstruktur befindet sich nämlich noch nicht in einem abgeschlossenen Zustand und kann somit unbrauchbar gemacht werden. Die Operationen kommen sich in die Quere!

Solche Operationen werden als unterbrechungskritisch bezeichnet und sollten demnach auch nicht unterbrechbar sein. Die Java-Programmierer kennen für diesen Zweck das Schlüsselwort synchronized. Der mit synchronized ausgezeichnete Code wird innerhalb eines Prozesses nicht parallel, sondern nur sequenziell zur Ausführung kommen. D. h. enthält ein Prozess mehrere Kindprozesse (Threads), welche unabhängig voneinander ein und denselben synchronisierten Code ausführen, dann darf dieser Code nicht „gleichzeitig” ablaufen. Nur so kann sichergestellt werden, dass längere Codesequenzen quasi atomar ablaufen. Synchronisierte Operationen kommen sich nicht mehr in die Quere!

Der Begriff Synchronisation ist jedoch ein wenig verwirrend, denn:

1. Was wird nun eigentlich synchronisiert?

Der dynamisch ablaufende Prozess wird sozusagen mit dem statisch vorliegenden Programmcode synchronisiert und richtet sich Zeile für Zeile an den Programmcode. Im Falle einer Unterbrechung werden unverträgliche Programmsequenzen durch Synchronisation nicht unmittelbar zur Ausführung kommen, sondern erst dann, wenn die kritische Programmsequenz abgearbeitet wurde.

Haben Sie beim Schach schon einmal mit dem Matt von Blackburne …

… punkten können?

Mehr ...