Lineare Datenstrukturen: Queue, Liste und Array
In diesem Abschnitt werden grundlegende lineare Datenstrukturen der Informatik vorgestellt. Der Fokus liegt auf Queues, Listen und Arrays, die für die Verwaltung und Organisation von Daten essentiell sind.
Queue - Die Warteschlange der Informatik
Eine Queue, auf Deutsch auch als Warteschlange bekannt, ist eine Datenstruktur, die nach dem FIFO-Prinzip (First In - First Out) arbeitet. Sie kann eine beliebige Menge von Objekten aufnehmen und gibt diese in der Reihenfolge ihres Einfügens zurück.
Definition: Das FIFO-Prinzip besagt, dass das zuerst eingefügte Element auch als erstes wieder entfernt wird.
Die wichtigsten Operationen einer Queue sind:
- enqueue: Hinzufügen eines Objektes
- dequeue: Entfernen eines Objektes
Beispiel: Eine praktische Anwendung des FIFO-Prinzips in der Informatik ist die Druckerwarteschlange. Druckaufträge werden in der Reihenfolge bearbeitet, in der sie eingegangen sind.
Liste - Flexible lineare Datenstruktur
Eine Liste ist eine lineare Datenstruktur, die beliebig viele Objekte verwalten und löschen kann. Im Gegensatz zur Queue ist das Einfügen und Löschen von Elementen an jeder Position der Liste möglich.
Highlight: Der Unterschied zwischen Array und Liste in Python liegt hauptsächlich in ihrer Flexibilität. Listen sind dynamisch und können ihre Größe ändern, während Arrays eine feste Größe haben.
Es gibt verschiedene Arten von Listen:
- Einfach verkettete Liste
- Doppelt verkettete Liste
Wichtige Methoden für Listen sind:
- isEmpty(): Prüft, ob die Liste leer ist
- toFirst(): Setzt den Zeiger an den Anfang der Liste
- toLast(): Setzt den Zeiger ans Ende der Liste
- hasAccess(): Prüft, ob es ein aktuelles Objekt gibt
- next(): Zur Navigation innerhalb der Struktur
- setContent() und getContent(): Zum Zugreifen auf Inhalte
- append(): Einfügen eines neuen Elements
- insert(): Neues Element vor dem aktuellen einfügen
- concat(): Andere Liste anhängen
- remove(): Löschen des aktuellen Objekts
Vocabulary: Ein einzelnes Element einer Liste wird als Knoten bezeichnet. In einer verketteten Liste kennt jeder Knoten seinen Nachfolger und besitzt somit eine Referenz auf das nächste Objekt.
Array - Statische Datenstruktur mit direktem Zugriff
Arrays sind Datenstrukturen mit einer konstanten Länge, die nach der Erstellung nicht verändert werden kann. Jedes Element eines Arrays hat einen Index, über den es direkt adressierbar ist.
Beispiel: In Java kann ein Array zur Speicherung von int-Werten wie folgt erstellt werden: int[] arr = new int[5];
Eigenschaften von Arrays:
- Schneller direkter Zugriff auf Elemente
- Geeignet, wenn die Anzahl der Elemente im Vorhinein bekannt ist
- Alle gespeicherten Werte müssen den gleichen Datentyp haben
Highlight: Der Unterschied zwischen Array und Liste in Python zeigt sich besonders bei der Performanz: Arrays ermöglichen einen schnelleren Zugriff auf einzelne Elemente, während Listen flexibler bei Änderungen der Größe sind.
