Grundlagen der Programmierung: Datenstrukturen

Wie werden Listen unterstützt?

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Verlinkte Listen finden in vielen Sprachen eine Umsetzung zumeist als doppelt verlinkte Liste, außer in Python, wo es sich bei einer Liste eigentlich um ein größenveränderbares Array handelt.

Transkript

Ich habe diesen Abschnitt damit begonnen, dass ich über den Begriff Liste gesagt habe, dass es verschiedene Auswirkungen in der Umsetzung gibt. Damit bin ich jetzt eigentlich in einer guten Position, um das Ganze aus der Nähe zu betrachten. Zuerst wollen wir uns das in Java ansehen. Einmal mehr existiert hier der Begriff Liste. Es ist Teil der grundlegenden java.util-Sammlung. Hier ist es aber so, dass die Liste als Schnittstelle bezeichnet wird. Es ist eine Klasse. Das heißt, es beschreibt ein Verhalten, das eine andere Klasse einsetzen kann. Eine dieser Klassen – wir kennen sie bereits – ist die ArrayList. Wir haben die ArrayList als größenveränderbares Array gesehen Es ist also ein interessanter Name. Ist das überhaupt ein Array? Oder eine Liste? Es ist ein wenig von beidem, wenn's um das Verhalten geht. Es ist sehr einfach, durch die ArrayList hindurchzuiterieren, indem spezielle Indices zum Einsatz kommen. Das ist ein sehr überzeugendes Verhalten für eine Liste, aber eigentlich ist diese ein Array. Intern wird die ArrayList wie ein Array abgelegt. Es unterstützt also direkten Zugriff und es sind keine großen Performance-Einbußen zu befürchten, wenn etwas eingefügt oder gelöscht wird. Nein, die für unsere Diskussion hier interessanteste Java-Klasse wäre die LinkedList. Es gibt da zwei Dinge, auf die ich hinweisen möchte. Erstens, dass es sich hierbei um eine doppelt verlinkte Liste handelt. Und das ist eine sehr gute Sache. Damit sollte das Einfügen und Löschen sehr schnell möglich sein. Hier ist aber noch eine andere Sache. Wenn ich etwas nach unten scrolle, dann komme ich zu den Methoden. Bei den Methoden gibt es eine Methode get. Diese Methode get ist sehr interessant, weil sie mir erlaubt, einen Index zu setzen. Das ist natürlich für eine Liste etwas sehr ungewöhnliches. Was das aber genau bedeutet, kann ich mir wieder weiter oben, wenn ich zum Anfang zurückscrolle, anschauen. Damit wirkt das Ganze dann nicht mehr so erstrebenswert. Schauen Sie mal auf diese Zeile. Diese Zeile besagt nämlich nicht mehr und nicht weniger, als dass Operationen, die in dieser Liste einen Index setzen, diese Liste nichtsdestotrotz durchlaufen müssen. Entweder von vorne oder von hinten. Je nachdem, was näher bei der indexierten Zahl liegen wird. Das heißt also, ich habe da keinen besonderen Performance-Gewinn. Ganz im Gegenteil. Es könnte sein, dass dieses nette Stückchen Code letztendlich zu einer ziemlichen Performance-Katastrophe führen kann, weil eben, wie bei Listen üblich, das Ganze, auch wenn ein Index gesetzt werden kann, nur sequentiell durchlaufen wird. Soviel zu Java. Wenn wir uns das Ganze jetzt auch für die Unterstützung anderer Sprachen ansehen, ist es eben bei Java so, dass die LinkedList in den java.utils drinnen ist. Bei C# ist es wiederum so, da gibt's eine LinkedList-Klasse direkt in der Systemsammlung. Es ist genau das, was Sie erwarten. Es ist eine doppelt verlinkte Liste. In Objective C gibt es jedoch keine eingebaute verlinkte Liste. Es gibt Implementierungen von Drittanbietern, die Sie einsetzen können, aber es gibt kein direktes Äquivalent, das von diesem Framework bereitgestellt wird. Ebenso hat auch Ruby keine eingebauten verlinkten Listen. Es hat Arrays und wie wir sehen werden hat es Dinge wie Hash-Tabellen oder Sets. Aber eben kein Äquivalent zu einer verlinkten Liste. Python. Python ist ja dieser spezielle Fall. Python hat zwar Listen, aber die Listen in Python haben mehr von einem dynamischen Array als tatsächlich von einer Liste. Und um das zu beweisen, wechseln wir jetzt nochmal rüber zur FAQ von Python. Wenn wir uns da bei den Fragen durcharbeiten, werden Sie sehen, dass eine von diesen Fragen die ist, wie Listen implementiert werden. How are lists implemented? Hier sehen Sie jetzt: Python lists are really variable length arrays. Wir haben es hier also mit größenveränderbaren Arrays zu tun. Direkt beschrieben in der FAQ von Python. Aber zurück zu unserer Gegenüberstellung. Uns fehlt nämlich noch C++. Bei C++ ist es so, dass der Listencontainer und die Standardvorlagenbibliothek eine doppelt verlinkte Liste ist. Wenn die von Ihnen gewählte Sprache keine spezifische verlinkte Liste besitzt, so ist das nicht das Ende der Welt. Im praktischen Programmieralltag brauchen Sie Array-Strukturen bedeutend häufiger als klassische verlinkte Listen. Sogar dann, wenn Sie eine große Menge an Iterationen, Löschvorgängen, et cetera haben. Was auf Arrays definitiv nicht zutrifft. Gibt's doch auch noch andere Datenstrukturen, die besser geeignet sind.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!