Schlange und Stapel

Die Queue (Schlange) ist eine dynamische Datenstruktur nach dem FiFo-Prinzip (First in, first out), d.h. das zuerst eingefügte Element wird auch als erstes wieder entnommen.

Der Stack (Stapel oder Keller) ist eine dynamische Datenstruktur nach dem LiFo-Prinzip (Last-In-First-Out), d.h. das zuletzt eingefügte Objekt wird als erstes wieder entnommen.

Liste

Die Liste ist eine dynamische Datenstruktur zum Speichern von Objekten.

Bei der einfach verketteten Liste besitzt jedes Listenelement einen Verweis auf seinen Nachfolger.

Bei der doppelt verketteten Liste besitzt jedes Listenelment einen Verweis auf Vorgänger und Nachfolger. Dies bewirkt ein effizienteres Suchen, erhöht allerdings ein wenig auch den Speicherbedarf.

Generische Datenstukturen in Java

Generische Datentypen, in Java auch Generics genannt, fügen einen Typparameter hinzu. So können in eine Liste<Type> nur Elemente des Typs Type eingefügt werden.

Einfache Sortieralgorithmen

Bei Bubblesort wird das Array jeweils von links nach rechts durchlaufen, ggf. werden dabei nebeneinanderliegende Einträge vertauscht.

Insertionsort bringt nacheinander alle Elemente an die richtige Stelle.

Selectionsort sucht nacheinander jeweils den kleinsten Wert in einem Array und baut so das sortierte Array auf.

Der Aufwand dieser einfachen Sortierverfahren liegt bei O(n²).

Rekursive Sortieralgorithmen

Mergesort halbiert die zu sortierende Liste solange, bis einzelne Elemente übrig bleiben. So wird schrittweise sortiert.

Bei Quicksort erfolgt die Halbierung beim sog. Pivotelement.

Der Aufwand rekursiver Sortierverfahren liegt bei O(n log n).