1.1 Algorithmen und Datenstrukturen

Als Datenstruktur wird die Organisation von Daten (Variablen) für ihre Verarbeitung durch Programme bezeichnet. Während wir in Band 1 des Java-Hamster-Buches noch ausschließlich mit einzelnen Variablen, also einfachen Datenstrukturen, gearbeitet haben, haben wir in Band 2 Konzepte kennen gelernt, Variablen zu größeren Einheiten zusammenzufassen.

Die grundlegendsten solcher komplexen Datenstrukturen stellen Arrays und Klassen dar.

• Arrays ermöglichen die Zusammenfassung mehrerer Variablen gleichen Typs zu einer Einheit.
• Klassen ermöglichen die Zusammenfassung mehrerer Variablen unter Umständen unterschiedlichen Typs zu einer neuen Einheit.

Auf diesen Konzepten aufbauend wurden in Kapitel 9.3 von Band 2 bereits weiterführende Datenstrukturen vorgestellt:

• Verkettete Listen vermeiden das Problem von Arrays, dass bei ihrer Erzeugung bereits die Anzahl der zusammenzufassenden Variablen angegeben werden muss.
• Stapel organisieren die in ihnen gespeicherten Daten nach dem Aktenhaufen-Prinzip: Es kann immer nur auf den zuletzt abgespeicherten Wert zugegriffen werden.

Mit diesen und weiteren Datenstrukturen werden wir uns in diesem Buch ausführlich auseinandersetzen.

Derartige Datenstrukturen bilden die Grundlage von Algorithmen. Der Begriff des Algorithmus wurde in Band 1 des Java-Hamster-Buches ausführlich analysiert. Ein Algorithmus ist eine Arbeitsanleitung zum Lösen eines Problems bzw. einer Aufgabe, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann.

Wir werden in diesem Buch viele grundlegende, wichtige und nützliche Algorithmen untersuchen, die jeder Programmierer kennen sollte, wie bspw. das Sortieren oder Suchen. Warum ist das notwendig, werden jetzt vielleicht diejenigen von Ihnen fragen, die bereits die JDK-Klassenbibliothek kennen. Hierin sind doch bereits die wichtigsten Algorithmen implementiert und werden uns Programmierern zur Verfügung gestellt. Das ist in der Tat richtig. Nichtsdestotrotz sprechen einige Gründe dafür, dass wir uns damit nicht zufrieden geben:

• Nicht in jeder Situation ist ein über das JDK zur Verfügung gestellter Algorithmus auch der beste. Wenn es bspw. um das Sortieren von Datenmengen geht, implementiert das JDK mit Quicksort einen Sortieralgorithmus, der im Durchschnitt schneller ist als andere Sortieralgorithmen. Weiss man jedoch, dass die zu sortierende Datenmenge bereits nahezu sortiert ist oder viele gleiche Daten enthält, gibt es schnellere Alternativen.
• Neben der eigentlichen Implementierung werden wir auch eine Analyse der Algorithmen durchführen. Diese gibt Auskünfte darüber, wie gut (in einem bestimmten technischen Sinne) ein Algorithmus in einer bestimmten Situation ist.
• Viele der vorgestellten Algorithmen enthalten grundsätzliche Lösungsansätze, die sich in anderen Zusammenhängen wiederverwenden lassen. Programmieren hat auch viel mit Erfahrung zu tun. Das Studium der grundlegenden Algorithmen der Informatik hilft Ihnen als Programmieranfänger, sich diesen Erfahrungsschatz aufzubauen.