Softwaretechnik, 8.4. Implementierung

Material für die Softwaretechnik Vorlesung, Bernhard Rumpe

Abschnitt 8.4. Datenstrukturen

  • Dieser Teil der Vorlesung ist für Studierende, die sich bisher mit den Datenstrukturen, wie sie Bibliotheken typischerweise zur Verfügung stellen noch nicht auseinandergesetzt haben. Wir analysieren die wichtigsten Datenstrukturen der Java Klassenbibliothek und wie wir sie einsetzen können.

  • Merke:
    • In den ersten Kursen eines Informatikstudiums lernen wir Algorithmen und Datenstrukturen zu definieren. Dazu gehört zum Beispiel die doppelt verkettete Liste.
    • Softwaretechnik bedeutet auch Wiederverwendung.
    • Niemals mehr werden wir eine der Datenstrukturen, wie etwa die Liste neu implementieren, wenn sie bereits existiert. Und die meisten Datenstrukturen sind schon implementiert worden.

  • Software ist eine so komplexe Angelegenheit, dass wir zur Erstellung qualitativ hochwertiger Software alles nutzen wollen, was wir bekommen können, um uns den applikationsspezifischen Herausforderungen zu widmen. Bekannte und bekanntermaßen qualitätsgesicherte Bibliotheken wie java.util und java.lang, die Java standardmäßig mitliefert, gehören zum Handwerkszeug.

  • Wer eine Sprache beherrschen will muss seine (wichtigsten) Bibliotheken kennen.

  • Bibliotheken gehören übrigens bei Programmiersprachen genauso zur Sprache wie zum Beispiel ein Duden zur deutschen Sprache gehört. Ohne all die darin definierten Begriffe ist eine Sprache wenig hilfreich.
    • Und genau wie mit einem eigenem fachspezifischen Glossar innerhalb der deutschen Sprache bauen wir uns mit eigenen Klassen in Java die verfügbare Sprache weiter aus.
  • Ein Datentyp hat grundsätzlich zwei unterschiedliche Sichtweisen:
    • der abstrakte Datentyp definiert uns was nach außen zur Verfügung steht und wie wir ihn benutzen wollen, also im Wesentlichen die Methoden und ihre Eigenschaften,
    • der konkrete Datentyp liefert eine Implementierung.

  • Die altbekannte Liste zeigt sehr schön, dass es
    unterschiedliche Implementierungen gibt, die zwar alle nach außen hin die gleiche Verhaltensweise liefern, aber intern unterschiedlich realisiert sind und daher unterschiedliche Leistungscharakteristiken, insbesondere im Bezug auf zeitliches Verhalten, gegebenenfalls aber auch Speicherplatzverbrauch liefern.

  • Die Möglichkeit, zwischen verschiedenen Realisierungen auszuwählen, bietet uns Optimierungsmöglichkeiten in Bezug auf die intendierte Verwendung. Die Nutzer des Datentyps aber braucht das nicht zu kümmern. Gegebenenfalls kann die Implementierung auch relativ einfach ausgetauscht werden.

  • Wie immer sind Vorgehensweisen idealisierte Beschreibungen dessen, wie man zu einer Lösung kommt. Tatsächlich hat man in der Praxis meist schon eine mögliche Realisierung im Kopf, sollte aber nicht vergessen noch mal kritisch zu hinterfragen, ob diese für das angelegte Problem optimal bzw. ausreichend ist.

  • Domänenspezifische Datenstrukturen beschäftigen sich zumeist mit den Fragen:
    • Können alle relevanten Daten gespeichert werden?
    • Ist möglichst wenig Redundanz enthalten?
    • Kann effizient von einem Objekt zum nächsten navigiert werden?
    • Kann eine aggregierende Berechnung schnell durchgeführt werden?
  • Siehe dazu auch das Thema Modellierung mit Klassendiagrammen. Für die grundlegenden Datenstrukturen gibt es jedoch sehr gute, hochoptimierte vorgefertigte Lösungen:

  • Es wäre verwunderlich, wenn Sie nicht fast alle dieser abstrakten Datentypen früher oder später einsetzen würden. Deshalb kann man nur empfehlen:: Verstehen Sie im Detail, wie Set, List, Queue und Map verwendet werden können – und vergessen Sie deren Implementierungen. Ergänzend gibt es übrigens auch noch den Stack sowie die in ihrer Verwendungsformen unterschiedliche Realisierungen für allgemeine Graphen oder Bäume, die dann aber auch unterschiedliche Signaturen (APIs) besitzen.

  • Siehe List, Set, Map.

  • Je mehr Worte einer einer Sprache bekannt sind, um so besser beherrscht man sie. Das gilt auch für Bibliotheken.
  • Für Java gibt es im Internet die API Dokumentation. Die ist hilfreich. Und wenn Sie eine moderne IDE haben, dann nutzt die häufig die dort verfügbare Information auch bei der Hilfetext-Anzeige.
  • Anbei zu sehen ist übrigens Information über die Klasse java.io.File inklusive ihrer Superklasse und die von ihr realisierten Interfaces in etwas älterem Layout. Weiter unten käme jetzt die Liste der Methoden und Attribute. Links sehen wir oben eine Sammlung von Paketen und unten die Klassen des ausgewählten Pakets java.io.

  • Java hat schon viel zu bieten und nicht alles müssen wir explizit beherrschen, manchmal können wir die Dinge auch indirekt nutzen, weil sie aufeinander aufbauen und wir idealerweise ihr weiter oben in den Schichten ansetzen.

  • Diese Schichten-Architektur ist typisch für Softwaresysteme, deren Komponenten aufeinander aufbauen und deren obere Komponenten jeweils die unteren benutzen.

  • Wenn man nicht gerade eine ganz besondere Datenstruktur oder sehr starke Optimierung benötigt, dann sollte man im normalen Regelungsbereich mit den vorhandenen Realisierungen sehr gut arbeiten können.

  • Siehe Collection

  • Über das Einfügen von null in eine Liste lässt sich übrigens streiten. Viele Softwareentwickler:innen sind ja der Meinung, dass null sowieso zu vermeiden ist und benutzen statt dessen für die Anzeige abwesender Werte den Datentyp Optional<.> der an dieser Stelle ebenfalls als hilfreicher Mechanismus erwähnt sei. Google bietet übrigens eine Alternativimplementierung für Listen, die null direkt verbietet.
  • ArrayList ist eine hochgradig effiziente Realisierung, denn zum Beispiel der Umgang mit Löschen von Elementen mitten in der Liste ist dort effizient und sicher korrekt realisiert.

  • Queue wirkt zunächst wie eine abgespeckte Version der Listen, und es kann auch gut sein, dass Listen als Realisierungstechnologie benutzt werden.

  • Queue hat aber ganz spezielle Vorzüge bei der Entwicklung verteilter Systeme, wo Queues die Realisierung von Kommunikationskanälen von Nachrichten oder auch bei der parallelen Bearbeitung von Aktivitäten innerhalb eines Prozessraums durch verschiedene Threads sehr gut unterstützen.

  • Wie auch bei allen vorhergehenden Datentypen gehen wir davon aus, dass sie den Datentyp an sich und die für diesen Typ geltenden Gesetze bereits in den Vorlesungen Programmieren oder Datenstrukturen gelernt und verstanden haben. Deshalb auch hier nur der Hinweis, dass Map existiert, verschiedene Realisierungsmöglichkeiten zur Verfügung stehen und eine Großzahl von Methoden in dem Interface einen komfortablen und effizienten Zugriff, Iteration und ähnliches mehr erlaubt.
  • anbei einige der wichtigsten Methoden zur Erinnerung bzw. zum geistigen Abbilden des gelernten, abstrakten Datentypen auf konkrete Methoden der Java-Realisierung.
  • Wir hoffen, die knappe Übersicht hilft Ihnen in Zukunft die richtigen Klassen einzusetzen und hat Sie neugierig gemacht auch nach anderen wiederverwendbaren Bibliotheken und Frameworks Ihrer Lieblingssprache Ausschau zu halten.

Join our mailing list for updates regarding courses and theses: