11 - Dynamische Datenstrukturen und anonyme Klassen Flashcards
Was sind dynamische Datenstrukturen?
Datenstrukturen, welche aus verketteten Objekten (Knoten) bestehen, werden als dynamisch bezeichnet, weil sie zur Laufzeit beliebig wachsen und schrumpfen können, ihre Größe nicht von vorneherein festgelegt ist und solange Speicher vorhanden ist, neue Knoten (mit new) erzeugt und an die Datenstruktur angehängt werden können.
Was sind Beispiele für dynamische Datenstrukturen?
Liste, Baum, Graph, Dictionary/Map
Was sind Listen?
Bei einer Liste hat jeder Knoten eine Referenz auf den Nachfolger (außer der letzte Knoten).
O—>O—>O—>O—>O
Was ist ein Baum?
Bei einem Baum kann jeder Knoten mehrere Referenzen auf Nachfolger haben.
O
Ó Ò
Ó Ò
Was ist ein Graph?
Graphen sind ähnlich wie Bäume, allerdings kann ein Knoten auch mehrere Vorgänger haben.
O
Ó Ò
Ò´-Ó Ò
Wozu werden Listen, Bäume und Graphen verwendet?
Listen, Bäume und Graphen werden in der Praxis zur Modellierung vieler Probleme eingesetzt.
- Liste: sortierte/unsortierte Liste von Daten, die sich verändern kann
- Baum: Dateisysteme,…
- Graph: Abläufe, Netzwerk,…
Woraus besteht eine Liste?
Jedes Element einer Liste besteht aus einer Variable für die Nutzdaten und einer Referenz auf den nächsten Knoten. Zusätzlich gibt es eine Referenz auf den Beginn der Liste.
Was sind Collections?
Collections sind Container für andere Objekte (viele vordefinierte Klassen in der Java Bibliothek). Sie können für dynamische Daten verwendet werden und erlauben es, Knoten/Daten zu speichern, zu suchen, zu löschen usw. Normalerweise speichern sie Werte vom Typ Object, damit sie zu allen abgeleiteten Klassen kompatibel sind.
Was sind Generics?
Mit Generics kann man per Spitzklammern die Objekte in einer Collection auf einen bestimmten Typ festlegen. Beispiel:
Vector<String> strings = new Vector<String>();
strings.add("bla");
strings.add("bla");</String></String>
Was ist ein Vector und was ist eine ArrayList?
Beide implementieren ein dynamisches Array (intern als statisches Array realisiert). Zunächst wird intern ein statisches Array mit einer bestimmten Größe erzeugt, das vergrößert wird, falls es zu klein ist (Vector: auf doppelte Größe; ArrayList: um Hälfte der aktuellen Größe). Es gibt Methoden zum Einfügen (add(…)), Indizieren (get(…) und set(…)), Löschen (remove(…)) und vieles mehr (size(), contains(…), clear()).
Was ist eine LinkedList?
Eine LinkedList ist eine doppelt verkettete Liste. Sie verbraucht mehr Speicher als eine ArrayList, ist aber schneller. Es gibt Methoden zum Einfügen (add, addFirst, addLast, push), Indizieren (get, set), Löschen (remove, removeFirst, removeLast) uvm. (size, contains, clear).
Was ist ein HashSet?
Ein HashSet ist eine unsortierte Menge von Elementen, wobei intern auch ein statisches Array sowie eine Hash-Funktion (um vom Wert den Index im Array zu ermitteln) verwendet wird. Es gibt Methoden zum Einfügen (add), Indizieren (direkt per Schlüssel/Iterator), Löschen (remove) uvm. (size, contains, clear).
Was ist eine Hash-Funktion?
Eine Hash-Funktion bildet einen beliebigen Datenraum auf Daten bestimmter Größe ab (z.B. auf 16 oder 256 Integer-Werte). Die Abbildung erfolgt möglichst gleichmäßig. Die Hash-Funktion ist dabei deterministisch und nicht invertierbar. Beispiel: Zeichensumme bei String.
Wozu dient eine HashMap?
Eine HashMap dient dem Speichern von Schlüssel-Werte Paaren (Hash-Table) und verwendet intern auch eine Hash-Funktion für möglichst schnelle Indizierung. Es gibt Methoden zum Hinzufügen (put), Auslesen (get), Ersetzen (replace), Entfernen (remove), für Abfragen bzgl. Größe und Inhalt (isEmpty, size) und zum Auslesen der Werte (Collection<V> values()).</V>
Sind dynamische Datenstrukturen mit dem List-Interface java.util.List kompatibel?
Ja.
