Grundlagen der Programmierung: Datenstrukturen

Listen

LinkedIn Learning kostenlos und unverbindlich testen!

Jetzt testen Alle Abonnements anzeigen
Listen können im Unterschied zu Arrays leichter verändert werden. Allerdings ist das Suchen in einer Liste rechentechnisch aufwendiger.

Transkript

Listen sind wie Arrays auch Sammlungen. Ich verwende den Begriff Sammlung in seiner umfassendsten Bedeutung. Arrays und Listen gruppieren beide verschiedene Elemente unter einem Namen. Ob dieses Element nun ein Integer, eine Zeichenkette oder ein allgemeines Objekt ist. Aber der größte Unterschied zwischen einem einfachen Array und einer einfachen Liste besteht in der Idee des direkten Zugriffs versus einem sequentiellen Zugriff. Das alles hat etwas damit zu tun, wie diese Datenstrukturen im Speicher abgelegt werden. Dies hier ist ein einfaches Array. Es wird normalerweise einem zusammenhängenden Bereich des Speichers zugeordnet. Alle Elemente, was sie auch darstellen: integer, double oder Objektreferenzierungen, sie liegen beieinander. Und wegen der Vorhersagbarkeit dieser Struktur können wir sofort zu jedem beliebigen Punkt gelangen, indem wir einfach den Index verwenden. Dabei ist es egal, wie groß das Array ist. Wir können direkt an jede beliebige Position springen. Und das direkt. Jedes Element ist gleich schnell erreichbar. Wir müssen uns nicht durch das ganze Array durcharbeiten, außer wir machen etwas aufwendiges, wie zum Beispiel eine lineare Suche. Das meine ich, wenn ich sage, dass ein Array direkten Zugriff auf seine einzelnen Elemente ermöglicht. Zusatzinformation: Direkter Zugriff wird auch willkürlicher Zugriff oder random access genannt. Ich bin kein Freund dieser Bezeichnungen, da Willkür suggeriert, wir hätten keine Kontrolle über das, was wir tun. Wir schütteln das magische Ei und bekommen ein willkürliches Element. Das ist mit willkürlichem Zugriff nicht gemeint. Wenn Sie den Begriff im Zusammenhang mit einer Datenstruktur sehen, denken Sie einfach an direkten Zugriff. Wir können ein bestimmtes Element direkt ansprechen, ohne uns vorwärts oder rückwärts durch die gesamte Sammlung arbeiten zu müssen. Ende dieser Zusatzinformation. Das also ist ein Array. Was ist dann eine Liste? Die klassische Unterscheidung ist diese: Wenn es bei Arrays um direkten Zugriff geht, dann geht's bei Listen um sequentiellen, also aufeinanderfolgenden Zugriff. Denn die Liste ist eine Zusammenstellung verschiedener Objekte oder verschiedener Elemente. Aber ihre Struktur baut nicht auf einer streng numerierten Indexierung auf, wie bei einem Array. Statt dessen geht die Liste einer Abfolge von Elementen nach. Es können 5 Elemente in einer Liste sein, 10, oder auch 1 000. Aber diese Elemente, was auch immer sie darstellen, können irgendwo im Speicher abgelegt werden. Sie müssen nicht beisammenliegen wie üblicherweise beim Array der Fall. Das klingt nach einem Haufen unterschiedlicher Objekte, werden Sie sich denken. Aber warten Sie. Das war's noch nicht. Im Gegensatz zum Array hat die Liste keinen numerischen Index. Das ist wahr. Statt dessen, wenn Sie auf eine Liste zugreifen, bekommen Sie das erste Element, manchmal erster Listenknoten genannt. Ein Listenknoten ist ein sehr einfaches Verpackungsobjekt. Oft so etwas Grundlegendes wie eine Verstrebung, ein Pfeiler, der Ihr Element, Ihren Wert enthält. Was auch immer es für ein Objekt sein mag. Und es verfügt über eine Verknüpfung zum nächsten Knoten, zum zweiten. In Sprachen wie Java und C# wäre das eine Objektreferenz. In C und C++ wäre das ein Pointer. Aber auf jeden Fall irgendeine Art von Verweis auf den nächsten Knoten. Wenn wir also das erste Element auslesen, ist das der erste Listenknoten. Wir verbinden diesen mit einem Link mit dem zweiten Knoten. Wo auch immer dieser im Speicher abgelegt sein mag. Wir können den Wert auslesen und bekommen zusätzlich einen Link zum dritten Knoten. Und so weiter. Bis wir zum abschließenden Knoten kommen. Wir stoßen an einen Knoten, von dem aus es nicht mehr weitergeht. Entweder, die Verlinkung zum nächsten Knoten beträgt dann Null oder es verweist auf einen sogenannten Terminator oder auch Wächterknoten genannt. Ein Wächterknoten ist lediglich ein Dummy-Knoten, ein Dummy-Objekt, das kein Element, keinen Wert enthält. Es ist nur dazu da, um eindeutig anzuzeigen, dass Sie nun ans Ende der Liste gekommen sind. Wir haben's noch immer mit einer geordneten Datenstruktur zu tun. Es gibt eine spezielle Abfolge von Knoten, wobei jeder Knoten einen Wert enthält und ebenso einen Verweis zum nächsten Knoten. Der große Unterschied: Erstens, der große Nachteil bei einer klassischen Liste wie dieser ist der, dass es nur einen sequentiellen Zugriff gibt. Das liegt am Aufbau der Liste. Wir können nicht direkt zum Eintrag 15 oder 1 000 springen, ohne beim ersten Listenknoten zu beginnen und uns zu diesem Eintrag vorzuarbeiten, indem wir uns von Knoten zu Knoten immer weiter vorarbeiten. Das ist ein sequentieller Zugriff. Und Sie denken sich: So einen sequentiellen Zugriff kann ich doch auch bei einem Array haben. Denn bei allem Gesagten können wir auch beim Array eine for-Schleife machen oder ein for each und durch das ganze Array interieren, indem wir den Index immer um 1 erhöhen. Wenn uns also Arrays beides ermöglichen, direkten Zugriff und sequentiellen Zugriff, warum sollte ich mich für so ein Listen-Ding entscheiden, was mich auf einen sequentiellen Zugriff beschränkt? Hier ist der große Unterschied Nummer zwei. Der Riesenvorteil einer verlinkten Liste: Wegen ihres Aufbaus ist das Hinzufügen und Entfernen von Elementen viel, viel einfacher als bei einem Array. Denn bei einem Array ist es nun mal so, dass, falls Sie an der zweiten Stelle eine neuen Wert einfügen wollen, Sie diesen ganzen Array-Komplex verschieben müssen, um dann Ihren Wert eintragen zu können. Bei Listen ist das ganz anders. Um einen Knoten am Anfang einer Liste einzufügen, brauchen Sie nur einen neuen Knoten erzeugen. Wo auch immer dafür gerade Platz sein mag. Ich würde in der Liste auf ihn verweisen, indem ich einfach von ihm aus auf den ehemals ersten Knoten verweise. Der Liste sage ich dann, dass er jetzt mein neuer erster Knoten ist. Der frühere erste Knoten wird dann einfach zu einem ganz normalen. Noch immer ist alles in der richtigen Reihenfolge. Fertig. Und kein anderer Knoten musste verschoben oder verändert werden. Dasselbe funktioniert auch am Ende. Sogar das Löschen eines Knotens, sogar aus der Mitte heraus, ist einfach. Wollte ich Objekt drei hier rechts entfernen, so reicht es, wenn ich das Objekt zwei, was derzeit auf drei verweist, seine Verlinkung entfernen lasse und direkt auf Objekt vier verweise. Dann entferne ich die Verlinkung von Objekt drei zu Objekt vier und habe nun Objekt drei richtig freigestellt, so dass es überhaupt kein Problem mehr ist, Objekt drei zu entfernen. Das funktioniert an jeder beliebigen Position der Liste. Wenn Sie's also mit sehr kurzlebigen, veränderlichen Daten zu tun haben, kann der Unterschied gewaltig sein, da hierbei existierende Elemente nicht nur umarrangiert werden müssen, sondern ein Element ganz einfach hinzugefügt oder auch wieder entfernt werden kann. Egal, ob die Liste groß oder klein ist. Es ist ein festgelegter Zeitrahmen für diesen Prozess. Das ist ein Unterschied zum Array, wo dieses schnelle Verändern und Entfernen viel komplizierter ist. Unsere zentrale Herausforderung besteht eigentlich darin, unsere Daten soweit zu verstehen, dass wir wissen, was wir für sie brauchen. Ein Array ist wirklich gut, wenn's ums direkte Indexieren geht und schlecht, wenn's ums Hinzufügen und Entfernen von Elementen geht. Und Listen sind gut, wenn's ums Hinzufügen und Entfernen von Elementen geht. Und sie sind schlecht, wenn's um die direkte Indexierung geht. Keiner von beiden ist gut, wenn es um eine volle lineare Suche geht. Obwohl Arrays einfacher zu sortieren sind und einfacher zu behandeln, wenn es um eine binäre Suche geht. Wir haben einfach zwei unterschiedliche Datenstrukturen, jeweils mit ihren Vor- und Nachteilen, und es liegt an uns, wie wir welche Datenstrukturen einsetzen.

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!