© Profit_Image/Shutterstock.com
Sie haben sich vielleicht mit Arrays beschäftigt, aber es gibt viele Datenstrukturen, die Sie beim Programmieren verwenden können. In mancher Hinsicht ähnelt eine verknüpfte Liste einem Array, es gibt jedoch einige wesentliche Unterschiede. Entdecken Sie, was eine verknüpfte Liste ist, erkunden Sie die verschiedenen Arten von verknüpften Listen und finden Sie in diesem Artikel heraus, wie man eine verknüpfte Liste verwendet.
Was ist eine verknüpfte Liste?
Wie ein Array, Eine lineare Liste ist eine lineare Datenstruktur. Der Unterschied liegt jedoch in der Art und Weise, wie sie Daten speichern und darauf zugreifen. Während ein Array Elemente in einem zusammenhängenden Speicherblock speichert, enthält eine verknüpfte Liste Elemente als Knoten, wobei jeder Knoten auf das nächste Element in der Liste zeigt. Daher werden sie nicht zusammenhängend gespeichert und auf Elemente wird nicht über einen Index zugegriffen. Stattdessen werden jedem Knoten Zeiger zugewiesen, die den nächsten Knoten in der Sequenz vorgeben. Wie bei einem dynamischen Array können verknüpfte Listen nach Bedarf durch Hinzufügen oder Entfernen von Knoten geändert werden. scaled.jpg” height=”1707″width=”2560″>
Was sind die Vorteile?
Jetzt haben wir genau besprochen, was eine verknüpfte Liste ist, Sie fragen sich vielleicht, warum Sie das tun sollten möchte einen verwenden. Hier sind einige Vorteile:
Sofern Sie kein dynamisches Array verwenden, ist die Array-Größe in der Regel fest, während verknüpfte Listen nach Bedarf vergrößert oder verkleinert werden können. Das Einfügen oder Löschen von Elementen erfordert im Gegensatz zu Arrays eine konstante Zeit wo andere Elemente verschoben werden müssen. Verkettete Listen neigen dazu, Ihre Speicherbeschränkungen zu schonen, insbesondere bei großen Datenmengen. Dies liegt daran, dass Speicher nur für die erforderlichen Knoten verwendet wird, aber die zusammenhängende Natur von Arrays bedeutet, dass Sie möglicherweise einige Daten unterstützen, die Sie für Ihre Operationen nicht benötigen. Es ist einfacher, die Persistenz von Daten mit verknüpften Listen aufrechtzuerhalten als Daten einfacher serialisiert werden als in Arrays. Dies macht es einfacher, Daten zwischen mehreren Programmen oder nach dem Beenden der Programme zu übertragen. Wo Sie Daten mit geringer Dichte haben, also leere Elemente, würde ein Array diese trotzdem speichern. Eine verknüpfte Liste speichert jedoch nur Werte, die nicht leer sind.
Was sind die verschiedenen Arten von verknüpften Listen?
Es gibt eine ganze Reihe verschiedener Arten von verknüpften Listen, die Sie verwenden können, jede mit ihren eigenen Eigenschaften. Wir geben hier einen kurzen Durchlauf und wie man sie in Python implementiert.
Einfache verknüpfte Liste
Wie zu erwarten war, ist dies die einfachste Art von verknüpfter Liste, bei der Sie die Liste nur in einer Richtung durchlaufen können. Jeder Zeiger zeigt auf den nächsten Knoten, wobei der letzte Knoten auf nichts oder NULL zeigt. Dies wird auch als einfach verkettete Liste bezeichnet. Der Code zum Implementieren einer einfachen verketteten Liste in Python lautet wie folgt:
class Node: def __init__(self, data): self.data=data self.next=None class LinkedList: def __init__(self): self. head=None def add(self, data): new_node=Node(data) if self.head ist None: self.head=new_Node else: current_node=self.head while current_node.next is not None: current_node=current_node.next current_node.next=new_node def remove(self, data): wenn self.head None ist: zurück, wenn self.head.data==data: self.head=self.head.next return current_node=self.head, während current_node.next ist not None: if current_node.next.data==data: current_node.next=current_node.next.next return def display(self): current_node=self.head while cur rent_node ist nicht None: print(current_node.data) current_node=current_node.next my_list=LinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(2) my_list.display
Erklärung
Dies ist ein ziemlich umfangreicher Codeblock, aber nicht zu schwer zu verstehen.
Zuerst definieren wir „Node“ und „LinkedList”Klassen. Die Klasse „Node“ repräsentiert einen Knoten in der Liste mit jeweils einem Zeiger (gekennzeichnet durch „self.next“). Die Liste wird durch „LinkedList“ repräsentiert, und wir haben einen Kopfknoten implementiert, der ein einfacheres Einfügen oder Löschen von Elementen ermöglicht.
Die „Hinzufügen“-Funktion zeigt an, dass ein neuer Knoten hinzugefügt werden soll das Ende der Liste. Wenn die Liste leer ist, wird der Kopfknoten auf den neu erstellten Knoten gesetzt. Wenn es nicht leer ist, wird die Liste bis zum letzten Knoten durchlaufen und zeigt diesen auf den neuen Knoten.
Die „Entfernen“-Funktion funktioniert, indem sie den ersten Knoten in der Liste entfernt. Wenn dies der Header-Knoten ist, dann wird der nächste Knoten zum Header-Knoten. Wenn der Kopfknoten die gegebenen Daten nicht hat, dann wird die Liste durchlaufen, um sie zu finden. Sobald es den Knoten mit den angegebenen Daten gefunden hat, wird sein „next“-Attribut auf den darauffolgenden Knoten gesetzt, wodurch dieser Knoten aus der Liste entfernt wird.
„Display“ durchläuft die Liste und gibt die gefundenen Daten aus jedem Knoten.
Die Daten innerhalb der Liste werden mit der „LinkedList“-Klasse am Ende definiert, mit Knoten der Datenwerte 1, 2 und 3. Knoten 2 wurde entfernt, um den Entfernungsprozess zu zeigen, und beide Listen werden zur Ausgabe gedruckt. Sehen Sie sich den Screenshot an, um zu sehen, wie das funktioniert.
Die Daten innerhalb der Liste werden mit der Klasse „LinkedList“ am Ende definiert, mit Knoten der Datenwerte 1, 2 und 3.
©”TNGD”.com
Doppelt Verkettete Liste
Dies ähnelt einer einfachen Liste, außer dass das Durchlaufen in beide Richtungen, vorwärts und rückwärts, erfolgen kann. Um dies zu implementieren, können wir den folgenden Code verwenden:
class Node: def __init__(self, data): self.data=data self.prev=None self.next=None class DoublyLinkedList: def __init__(self): self.head=Keine self.tail=Keine def add(self,data): new_node=Node(data) if self.head ist None: self.head=new_node self.tail=new_node else: new_node.prev=self.tail self.tail.next=neuer_Knoten self.tail=neuer_Knoten def remove(self, data): current_node=self.head while current_node is not None: if current_node.data==data: if current_node.prev is not None: current_node.prev.next=aktueller_Knoten.nächster sonst: self.head=aktueller_Knoten.next wenn aktueller_Knoten.next nicht None ist: aktueller_Knoten.next.prev=aktueller_Knoten.prev else: self.tail=aktueller_Knoten.prev return aktueller_Knoten=aktueller_Knoten.next def display(self): aktueller_Knoten=self.head while current_node is not None: print(current_node.data) current_node=aktueller_Knoten.next my_list=DoublyLinkedList() my_list. add(1) my_list.add(2) my_list.add(3) my_list.display() my_list.remove(3) my_list.display()
Erklärung
Ein Großteil des Codes darin Beispiel ist ähnlich, aber es gibt einige Unterschiede.
Wir definieren die Klasse „Knoten“ auf ähnliche Weise, aber diesmal gibt es sowohl Verweise auf den vorherigen Knoten als auch auf den nächsten Knoten. In ähnlicher Weise repräsentiert die Klasse „DoubleLinkedList“ die Liste, hat aber Instanzen, die sowohl als Kopf als auch als Ende der Liste fungieren.
Wie zuvor fügt die Funktion „Hinzufügen“ einen neuen Knoten am Ende der Liste hinzu. Wenn die Liste jedoch leer ist, werden sowohl der Kopf als auch der Schwanz auf diesen neuen Knoten gesetzt. Wenn die Liste nicht leer ist, wird das „prev“-Attribut des neuen Knotens auf den aktuellen Knoten gesetzt und das „next“-Attribut des aktuellen Knotens auf den neuen Knoten, und der Schwanz wird auf den neuen Knoten geändert.
Die „remove“-Funktion entfernt den ersten Knoten in der Liste mit den angegebenen Daten. Die „prev“-und „next“-Attribute benachbarter Knoten werden aktualisiert, um den aktuellen Knoten zu vermeiden und ihn effektiv aus der Liste zu entfernen. Wenn es sich bei dem fraglichen Knoten um den Kopf oder den Schwanz handelt, wird dieses Attribut ebenfalls aktualisiert, um dies widerzuspiegeln.
Zu guter Letzt sind die Funktionen „display“ und „my_list“ weitgehend gleich, aber diesmal haben wir es getan entfernte den Knoten mit dem Datenwert 3. Die Screenshots veranschaulichen die Codeausführung.
Die „add“-Funktion fügt am Ende der Liste einen neuen Knoten hinzu.
©”TNGD”.com
Die Funktionen „display“ und „my_list“ sind weitgehend gleich, aber dieses Mal haben wir Ich habe den Knoten mit dem Datenwert 3 entfernt.
©”TNGD”.com
Zirkulär verkettete Listen
Eine andere Art von verketteter Liste ist eine kreisförmige Liste. Wie der Name schon sagt, ist dies eine Liste, bei der es kein „Ende“ gibt. Der Endknoten ist wieder mit dem Startknoten verbunden. Ein Beispiel ist im folgenden Code zu sehen:
class Node: def __init__(self, data): self.data=data self.next=None class CircularLinkedList: def __init__(self): self.head=None def add (self, data): new_node=Node(data) if self.head ist None: self.head=new_node new_node.next=self.head else: current_node=self.head while current_node.next is not self.head: current_node=current_node.next current_node.next=neuer_Knoten new_node.next=self.head def remove(self,data): wenn self.head None ist: zurück, wenn self.head.data==data: current_node=self.head while current_node.next ist nicht self.head: current_node=aktueller_node.next current_node.next=self.head.next self.head=self.head.next sonst: aktueller_node=self.head while current_node.next is not self.head: if current_node.next.data==data: current_node.next=current_node.next.next return current_node=current_node.next def display(self): if self.head is None: return current_node=self.head while True: print(current_node.data) current_node=current_node.next if current_node is self.head: break my_list=CircularLinkedList() my_list.add(1) my_list.add(2) my_list.add (3) my_list.display()
Erklärung
Hier gibt es einige wesentliche Unterschiede. „new_node.next=self.head“ bedeutet, dass der neu hinzugefügte Knoten der letzte Knoten in der Liste ist und zurück auf den Kopf der Liste zeigt, der der erste Knoten ist.
Der „ while current_node.next is not self.head“ wird verwendet, um die verknüpfte Liste zu durchlaufen und Elemente hinzuzufügen. Da es kein wahres Ende gibt, wie bei der einfach verketteten Liste, müssen wir prüfen, ob der aktuelle Knoten der Kopfknoten ist, und nicht, ob er einfach nicht Null ist. Dadurch soll vermieden werden, dass der Hauptknoten geändert wird.
Der Code „new_node.next=self.head“ stellt sicher, dass der zur Liste hinzugefügte Knoten mit dem Hauptknoten verbunden wird.
Der Die „Remove“-Funktion funktioniert insofern ähnlich, als wenn die angegebenen Daten im ersten Knoten enthalten sind, diese entfernt werden und der nächste Knoten zum neuen Hauptknoten wird. Wenn der Kopfknoten die angegebenen Daten nicht enthält, wird die Liste wie zuvor durchlaufen, bis die Daten gefunden werden. Dem übernächsten Knoten wird dann das Attribut „next“ zugewiesen, wodurch dieser Knoten übersprungen wird. Im Großen und Ganzen ist die Funktion dieselbe, aber die Implementierung ist aufgrund der kreisförmigen Natur der Liste etwas aufwändiger.
Die Funktion „Anzeigen“ ist auch sehr ähnlich, nur dass wir sie überprüfen müssen beginnen am Kopfknoten und unterbrechen die Traversierung, sobald wir diesen Punkt wieder erreichen.
Der Code’new_node.next=self.head’stellt sicher, dass der zur Liste hinzugefügte Knoten mit dem Hauptknoten verbunden ist.
©”TNGD”.com
Die „Anzeige“ Die Funktion ist auch fast dieselbe, aber wir müssen am Kopfknoten beginnen und die Traversierung unterbrechen, sobald wir diesen Punkt wieder erreichen.
©”TNGD”.com
Double Circular Linked Lists
Da wir einfach, doppelt und kreisförmig verknüpfte Listen betrachtet haben, macht es nur Sinn e zum Abschluss mit einer doppelten kreisförmigen verknüpften Liste. Ziemlich mundvoll, aber nicht ganz schwer fassbar. Erwartungsgemäß bezieht sich dies auf eine kreisförmige verknüpfte Liste, die wir sowohl in Vorwärts-als auch in Rückwärtsrichtung durchlaufen können. Die Implementierung dieses Listentyps kann wie folgt dargestellt werden:
class Node: def __init__(self, data): self.data=data self.next=None self.prev=None class DoubleCircularLinkedList: def__init__(self): self.head=None def add(self, data): new_node=Node(data) if self.head ist None: new_node.next=new_node new_node.prev=new_node self.head=new_node else: last_node=self.head. prev last_node.next=neuer_Knoten new_node.prev=letzter_Knoten new_node.next=self.head self.head.prev=new_node def remove(self,data): wenn self.head None ist: return current_node=self.head while current_node.data !=Daten: aktueller_Knoten=aktueller_Knoten.next wenn aktueller_Knoten==self.head: zurückgeben wenn aktueller_Knoten==self.head: se lf.head=aktueller_Knoten.nächster aktueller_Knoten.prev.next=aktueller_Knoten.nächster aktueller_Knoten.next.prev=aktueller_Knoten.prev def display(self): wenn self.head None ist: return current_node=self.head while True: print(current_node.data) aktueller_Knoten=aktueller_Knoten.next if aktueller_Knoten==self.head: break my_list=DoubleCircularLinkedList() my_list.add(1) my_list.add(2) my_list.add(3) my_list.display()
Erklärung
Der Hauptunterschied zwischen einer doppelt kreisförmigen verketteten Liste und einer standardmäßigen kreisförmigen verketteten Liste besteht darin, dass die doppelte Liste wie zuvor bei der nicht kreisförmigen verketteten Liste jeden Knoten sowohl auf den vorherigen als auch auf den nächsten Knoten zeigt. Dies wird erreicht, indem beim Hinzufügen eines Knotens die Attribute „prev“ und „next“ des letzten Knotens und des neuen Knotens aktualisiert werden. Beim Entfernen eines Knotens müssen diese Attribute des entfernten Knotens und benachbarter Knoten aktualisiert werden. Wenn Sie den Hauptknoten entfernen, müssen die Zeiger des letzten Knotens aktualisiert werden, um dies widerzuspiegeln.
Die doppelte Liste zeigt jeden Knoten auf den vorherigen Knoten sowie den nächsten Knoten.
©”TNGD”.com
Wenn Sie den Hauptknoten entfernen , dann müssen die Zeiger des letzten Knotens aktualisiert werden, um dies widerzuspiegeln.
©”TNGD”.com
Zusammenfassung
Viele Arten von verknüpften Listen können als verwendet werden eine Alternative zu Arrays, wenn Sie z. B. regelmäßig Elemente einfügen und löschen müssen oder Speicherbeschränkungen haben. Obwohl Arrays bei bestimmten Operationen schneller arbeiten, sind verknüpfte Listen nicht ohne ihre einzigartigen Vorteile, daher ist es hilfreich zu verstehen, wie sie funktionieren.
Als Nächstes …
Die verknüpfte Liste Häufig gestellte Fragen zur Datenstruktur und ihrer Verwendung
Was ist eine verknüpfte Liste?
Eine verknüpfte Liste ist eine Datenstruktur, in der die Daten wird in „Knoten“ gespeichert und nicht zusammenhängend, wie bei einem Array. Sie können einfach oder kreisförmig sein, wobei bei letzterem der letzte Knoten zurück zum Kopfknoten zeigt. Sie können auch doppelt verknüpfte Listen implementieren, bei denen das Durchlaufen der Liste vorwärts und rückwärts erfolgen kann.
Was sind die Vor-und Nachteile verknüpfter Listen?
Verkettete Listen können besser sein als Arrays, wenn Sie häufig Daten einfügen und löschen müssen oder Speicherbeschränkungen haben. Ein Array kann jedoch besser sein, wenn Sie eine binäre Suche verwenden müssen, und da sie zusammenhängend sind, sind sie Cache-freundlicher. Während das Einfügen von Elementen schneller geht, kann der Zugriff auf ein bestimmtes Element langsamer sein, da Sie die gesamte Liste durchlaufen müssen.
Welche Arten von verknüpften Listen gibt es?
Die Arten von verknüpften Listen umfassen einfache und doppelt verknüpfte Listen sowie kreisförmige und doppelt kreisförmig verknüpfte Listen.
Wie fügen Sie einen Knoten aus einer verknüpften Liste ein oder löschen ihn?
Um einen Knoten einzufügen, müssen Sie den neuen Knoten erstellen und das „nächste“ Attribut dieses Knotens auf den nächsten Knoten in der Liste verweisen, sowie das „nächste“ Attribut des vorherigen Knotens auf diesen verweisen neuer Knoten. Um einen Knoten zu löschen, müssen Sie die Liste durchlaufen, um die angegebenen Daten zu finden. Dann müssen Sie das „nächste“ Attribut des vorherigen Knotens auf den Knoten vor dem Knoten, den Sie löschen möchten, zeigen, damit er in der Liste übersprungen wird.
Wie durchlaufen Sie a verknüpfte Liste?
Um die Liste zu durchlaufen, beginnen Sie mit dem Kopfknoten und bewegen sich zu jedem Knoten in der Sequenz, bis Sie den Endknoten erreichen.
Wie hoch ist die zeitliche Komplexität von Operationen mit verknüpften Listen?
Jede Operation hat ihre eigene zeitliche Komplexität. Operationen mit einer Zeitkomplexität von O(1) umfassen das Einfügen eines Elements am Anfang und das Löschen eines Elements am Anfang. Die meisten anderen Operationen haben eine Komplexität von O(n). Dazu gehören der Zugriff auf ein Element, das Einfügen oder Löschen eines Elements am Ende, das Einfügen oder Löschen eines Elements an einem bestimmten Index und das Suchen nach einem bestimmten Element. Dies liegt daran, dass die Liste durchlaufen werden muss, sodass die Komplexität von der Größe der Liste abhängt.
Welche Alternativen gibt es stattdessen zu verknüpften Listen?
Stattdessen einer verknüpften Liste könnten Sie ein Array verwenden, in dem Daten in einem zusammenhängenden Block gespeichert werden. Hash-Tabellen werden verwendet, um Schlüssel Indizes in einem Array zuzuordnen, sodass diese in Verbindung miteinander verwendet werden können. Oder Sie könnten einen Baum verwenden, bei dem Knoten in einem hierarchischen Format verbunden sind. Heaps sind eine Art binärer Baum und eine weitere Option. Schließlich können Stapel und Warteschlangen entweder mit Arrays oder verknüpften Listen verwendet werden, und obwohl sie nicht so flexibel sind wie einige Optionen, bieten sie eine effiziente Änderung von Elementen.
Was sind einige Anwendungen von Verlinkte Listen?
Verlinkte Listen sind dort sinnvoll, wo Sie die Größe der Liste nicht kennen, weitere Datenstrukturen implementieren wollen, in der Bild-und Musikbearbeitung und um Graphen und Bäume darzustellen.