Verkettete Liste in Python

  2. How-To's
  3. Python How-To's
  4. Verkettete Liste in Python
Aditya Raj 30 Januar 2023
Python Python Data Structure
  1. Was ist eine verknüpfte Liste in Python?
  2. So erstellen Sie eine verknüpfte Liste in Python
  3. Drucken Sie alle Elemente einer verknüpften Liste in Python
  4. Fügen ein Element in eine verknüpfte Liste in Python ein
  5. Löschen Sie ein Element aus der verknüpften Liste in Python
  6. Zählen Sie die Anzahl der Elemente in einer verknüpften Liste in Python
  7. Aktualisieren Sie einen Knoten in der verknüpften Liste in Python
  8. Warum eine verknüpfte Liste in Python verwenden
  9. Vollständige verkettete Implementierungsliste in Python
  10. Fazit
Verkettete Liste in Python

Python stellt uns verschiedene eingebaute Datenstrukturen zur Verfügung.

Jede Datenstruktur hat jedoch ihre Einschränkungen. Aus diesem Grund benötigen wir benutzerdefinierte Datenstrukturen.

In diesem Artikel wird eine benutzerdefinierte Datenstruktur namens Linked List erläutert. Wir werden auch eine verknüpfte Liste in Python implementieren und verschiedene Operationen an der verknüpften Liste ausführen.

Was ist eine verknüpfte Liste in Python?

Wie der Name schon sagt, ist eine verknüpfte Liste eine Datenstruktur, die Elemente enthält, die über einen Link verbunden sind.

Eine verknüpfte Liste wird mithilfe von Objekten erstellt, die Knoten genannt werden. Jeder Knoten enthält zwei Attribute – eines zum Speichern der Daten und das andere zum Verbinden mit dem nächsten Knoten in der verknüpften Liste.

Anhand der folgenden Abbildung können Sie den Aufbau eines Knotens nachvollziehen.

Knoten in Python

Hier,

  • Ein Node ist ein Objekt, das die Attribute data und next enthält.
  • Das Attribut data speichert die Daten.
  • Das Attribut next verweist auf den nächsten Knoten in der verknüpften Liste.

Wie im folgenden Bild gezeigt, können wir verschiedene Knoten verbinden, um eine verknüpfte Liste zu erstellen.

Verkettete Liste in Python

Hier,

  • Wir haben eine verkettete Liste erstellt, die aus vier Knoten besteht.
  • Der erste Knoten enthält die Zahl 10, der zweite Knoten enthält 20, der dritte Knoten enthält 30 und der letzte Knoten enthält 40.
  • Wir haben auch eine Variable Head erstellt, die sich auf den ersten Knoten bezieht. Wir behalten nur die Variable Head in einem Linked-List-Objekt. Daten in allen anderen Knoten werden erhalten, indem die verknüpfte Liste durchlaufen wird, beginnend mit dem ersten Knoten, auf den durch Head verwiesen wird.
  • Das Attribut next des letzten Knotens verweist auf ein None-Objekt. Das Attribut next des letzten Knotens einer verknüpften Liste bezieht sich immer auf das Objekt None.
  • Wenn eine verknüpfte Liste leer ist, verweist die Variable Head auf das Objekt None.

Wir verstehen jetzt die Grundstruktur einer verketteten Liste. Lassen Sie uns eine verkettete Liste in Python implementieren.

So erstellen Sie eine verknüpfte Liste in Python

Da Knoten die Bausteine ​​einer verketteten Liste sind, erstellen wir zuerst einen Knoten. Dazu definieren wir eine Node-Klasse mit den Attributen data und next wie unten gezeigt.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)

Ausgabe:

The data in the node is: 10
The next attribute in the node is: None

Im obigen Beispiel können Sie beobachten, dass das Attribut next des Node standardmäßig auf None verweist. Wenn wir es in eine verknüpfte Liste einfügen, weisen wir den Knoten in der verknüpften Liste das Attribut next zu, wie wir weiter unten besprechen werden.

Wir müssen ein Objekt mit dem Attribut Head erstellen, um eine verknüpfte Liste zu erstellen. Wir können die Klasse LinkedList wie unten gezeigt definieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)

Ausgabe:

The linked list is:
10 20 30 40

Im obigen Beispiel haben wir eine verknüpfte Liste erstellt.

Danach haben wir die Knoten mit den angegebenen Daten manuell erstellt, sie einzeln zur verknüpften Liste hinzugefügt und gedruckt. Später werden wir lernen, Elemente in eine verkettete Liste einzufügen, indem wir Pythons while-Schleife verwenden.

Lassen Sie uns nun besprechen, wie wir alle Elemente einer verknüpften Liste drucken können, ohne manuell auf alle Knoten zuzugreifen.

Drucken Sie alle Elemente einer verknüpften Liste in Python

Wir werden eine while-Schleife verwenden, um alle verknüpften Listenelemente auszudrucken.

Ausgehend vom Head-Zeiger drucken wir zuerst die Daten im aktuellen Knoten unter Verwendung des data-Attributs des Knotens. Danach gehen wir mit dem next-Zeiger zum nächsten Knoten.

Wir werden diesem Prozess folgen, bis wir das Ende der verknüpften Liste erreichen (d. h. das next-Attribut eines Knotens wird als None festgestellt). Wie unten gezeigt, können Sie die gesamte Logik in der Methode printList() implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 20 30 40

Fügen ein Element in eine verknüpfte Liste in Python ein

Beim Einfügen eines Elements in eine verknüpfte Liste gibt es vier Situationen.

  1. Die verknüpfte Liste kann vor dem Einfügen leer sein.
  2. Wir müssen ein Element am Anfang einer nicht leeren verketteten Liste einfügen.
  3. Wir müssen ein Element am Ende einer verketteten Liste einfügen.
  4. Wir müssen ein Element an einer bestimmten Position in der verknüpften Liste einfügen.

Lassen Sie uns besprechen, wie ein Element in allen Situationen in die verknüpfte Liste eingefügt wird.

Fügen ein Element in eine leere verknüpfte Liste ein

Um ein Element in eine leere verknüpfte Liste einzufügen, definieren wir eine Methode insertIntoEmptyList(), die das Element als Eingabeargument akzeptiert und der verknüpften Liste einen Knoten hinzufügt, der das Eingabeelement enthält.

Dazu erstellen wir einen Knoten in der insertIntoEmptyList() mit dem Eingabeelement als data. Nach dem Erstellen des Knotens weisen wir dem Knoten das Attribut Head zu.

Auf diese Weise wird der neue Knoten zum ersten Knoten der verknüpften Liste. Das Verfahren kann wie folgt implementiert werden.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10

Einfügen eines Elements am Anfang einer verknüpften Liste

Um ein Element am Anfang einer nicht leeren Liste einzufügen, definieren wir eine Methode insertAtBeginning(), die ein Element als Eingabe nimmt und es am Anfang der verknüpften Liste hinzufügt. In der Methode insertAtBeginning() erstellen wir zuerst einen Knoten mit dem Eingabeelement als Daten.

Danach zeigen wir das next-Attribut des neu erstellten Knotens auf den Knoten, auf den das Head-Attribut der verknüpften Liste zeigt. Als nächstes weisen wir den neu erstellten Knoten dem Attribut Head zu.

Auf diese Weise wird der neue Knoten am Anfang der verknüpften Liste eingefügt.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode

    def insertAtBeginning(self, element):
        newNode = Node(element)
        newNode.next = self.Head
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
30 20 10

Wie unten gezeigt, können wir die obigen Methoden kombinieren, um eine einzige Methode zum Einfügen eines Elements am Anfang einer verknüpften Liste zu erstellen.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
30 20 10

Wir haben die Methode insertIntoEmptyList() mit der Methode insertAtBeginning() zusammengeführt, weil das Einfügen in eine leere verkettete Liste im Wesentlichen bedeutet, dass wir ein Element am Anfang der verketteten Liste einfügen.

Fügen Sie ein Element am Ende einer verknüpften Liste ein

Das Einfügen eines Elements am Ende einer leeren Liste ähnelt dem Einfügen des Elements am Anfang der verknüpften Liste.

Um ein Element am Ende einer verknüpften Liste einzufügen, prüfen wir zunächst, ob die verknüpfte Liste leer ist. Wenn sich herausstellt, dass die verknüpfte Liste leer ist, können wir dem Attribut Head einfach einen Knoten zuweisen, der das neue Element enthält, wie wir es in der Methode insertAtBeginning() getan haben.

Andernfalls durchlaufen wir die verkettete Liste mit einer while-Schleife bis zum Ende. Wir beginnen mit dem Head und bewegen uns mit dem next-Attribut der Knoten zum nächsten Knoten, bis wir feststellen, dass das next-Attribut des Knotens auf None zeigt.

Sobald wir einen Knoten erreichen, dessen Attribut next auf None zeigt, sind wir am letzten Knoten. Jetzt erstellen wir mit den Eingabedaten einen neuen Knoten und weisen diesen Knoten dem nächsten Attribut des letzten Knotens der verknüpften Liste zu.

Auf diese Weise wird das neue Element am Ende der verknüpften Liste eingefügt. Diese ganze Logik können Sie in der Methode insertAtEnd() wie folgt implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 20 30

Fügt ein Element an einer bestimmten Position in der verknüpften Liste ein

Wir werden eine Zählervariable und eine while-Schleife verwenden, um ein Element an einer bestimmten Position in der verknüpften Liste einzufügen.

Wir beginnen beim Head-Zeiger und bewegen uns mit der while-Schleife zum nächsten Knoten. Bei jeder Iteration erhöhen wir auch die Zählervariable.

Sobald wir den Knoten vor der angegebenen Position erreichen, verlassen wir die while-Schleife. Außerdem verlassen wir die Schleife, wenn wir das Ende der verknüpften Liste erreichen. Andernfalls läuft das Programm auf einen Fehler.

Danach, wenn wir immer noch am Head sind, müssen wir das Element an der ersten Position der verknüpften Liste hinzufügen; Wir weisen den Knoten an der angegebenen Position dem next-Zeiger zu, der das neue Knotenelement enthält. Als nächstes weisen wir den Knoten des neuen Elements dem Head der verknüpften Liste zu.

Wenn wir das Element nicht an der 1. Position einfügen müssen, weisen wir den Knoten an der angegebenen Position dem next-Zeiger des Knotens zu, der das neue Element enthält. Als nächstes weisen wir den neuen Knoten dem Attribut next des Knotens an position-1 zu.

Auf diese Weise wird das neue Element an der angegebenen Position eingefügt. Wie unten gezeigt, können Sie die gesamte Logik in der Methode insertAtPosition() implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 
The elements in the linked list are:
10 20 
The elements in the linked list are:
10 20 30 
The elements in the linked list are:
10 40 20 30

Löschen Sie ein Element aus der verknüpften Liste in Python

Es kann drei Situationen geben, in denen wir versuchen, ein Element aus einer verknüpften Liste zu löschen.

  1. Wir müssen das erste Element der verknüpften Liste löschen.
  2. Wir müssen das letzte Element der verknüpften Liste löschen.
  3. Wir müssen das Element an einer beliebigen Position in der verknüpften Liste löschen.

Lassen Sie uns alle diese Fälle einzeln besprechen.

Löschen Sie das erste Element einer verknüpften Liste

Um das erste Element einer verknüpften Liste zu löschen, prüfen wir zunächst, ob die verknüpfte Liste leer ist oder nicht.

Dazu prüfen wir, ob der Head der verlinkten Liste auf None zeigt. Wenn ja, werden wir den Benutzer darüber informieren, dass die verknüpfte Liste leer ist und wir kein Element zum Löschen haben.

Andernfalls weisen wir den ersten Knoten einer temporären Variablen zu. Danach weisen wir dem Attribut Head den zweiten Knoten der verknüpften Liste zu.

Dann löschen wir den ersten Knoten, der in der temporären Variablen gespeichert ist, mit der Anweisung del. Wie unten gezeigt, können Sie die gesamte Logik in der Methode deleteFromBeginning() implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
20 30

Das letzte Element einer verknüpften Liste löschen

Um das letzte Element einer verknüpften Liste zu löschen, prüfen wir zunächst, ob die verknüpfte Liste leer ist oder nicht.

Dazu prüfen wir, ob der Head der verlinkten Liste auf None zeigt. Wenn ja, werden wir den Benutzer darüber informieren, dass die verknüpfte Liste leer ist und wir kein Element zum Löschen haben.

Wenn Elemente in der Liste vorhanden sind, gehen wir wie folgt vor.

  1. Weisen Sie den ersten Knoten einer Variablen current zu.
  2. Initialisieren Sie eine Variable previous auf None.
  3. Durchlaufen Sie die verknüpfte Liste mit einer while-Schleife, weisen Sie den Knoten an der current Variablen der current Variablen zu und rücken Sie die current Variable zum nächsten Knoten vor, bis die current Variable den letzten Knoten erreicht . In diesem Fall wird das Attribut next des Knotens, der current zugeordnet ist, zu None.
  4. Sobald die aktuelle Variable den letzten Knoten erreicht, weisen wir None dem Attribut next der Variable previous zu und löschen den Knoten, der der Variable current zugewiesen ist.

Wir können das letzte Element einer verknüpften Liste löschen, indem wir die obigen Schritte ausführen. Wie unten gezeigt, können Sie die gesamte Logik in der Methode deleteFromLast() implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 
The elements in the linked list are:
10 40

Löschen das Element an einer beliebigen Position in der verknüpften Liste

Um ein Element an einer bestimmten Position in der verknüpften Liste zu löschen, prüfen wir zunächst, ob die verknüpfte Liste leer ist oder nicht.

Dazu prüfen wir, ob der Head der verlinkten Liste auf None zeigt. Wenn ja, werden wir den Benutzer darüber informieren, dass die verknüpfte Liste leer ist und wir kein Element zum Löschen haben.

Wenn in der verknüpften Liste Elemente vorhanden sind und wir ein Element an einer anderen Position löschen müssen, führen wir die folgenden Schritte aus.

  1. Weisen Sie den ersten Knoten einer Variablen current zu.
  2. Initialisieren Sie eine Variable previous auf None.
  3. Initialisieren Sie eine Variable count auf 1.
  4. Durchlaufe die verkettete Liste mit einer while-Schleife, inkrementiere count bei jeder Iteration, weise den Knoten an der current Variablen previous zu und schiebe die current Variable zum nächsten Knoten, bis der count Variable hat die position des zu löschenden Elements oder wir erreichen das Ende der verknüpften Liste. An dieser Stelle bezieht sich die Variable current auf den zu löschenden Knoten.
  5. Sobald die Zählung gleich der Position des zu löschenden Elements wird, kann es zwei Situationen geben.
  6. Wenn wir immer noch beim Head sind, an der 1. Position, werden wir den Knoten, auf den das next-Attribut der aktuellen Variablen verweist, dem Head-Attribut zuweisen. Danach löschen wir die current Variable.
  7. Wenn wir nicht an der 1. Position sind, weisen wir den nächsten Knoten der current Variablen dem nächsten Attribut des Knotens zu, der der current Variablen zugeordnet ist. Wir löschen den Knoten, der der Variablen current zugeordnet ist. Auf diese Weise wird das Element an der angegebenen Position gelöscht.

Wir können die obige Logik in der unten besprochenen Methode deleteAtPosition() implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
40 30

Zählen Sie die Anzahl der Elemente in einer verknüpften Liste in Python

Um die Anzahl der Elemente in einer verketteten Liste zu zählen, initialisieren wir einfach eine Variable count auf 0.

Danach beginnen wir beim Head und bewegen uns mit einer while-Schleife zum nächsten Knoten, bis wir das Ende der verknüpften Liste erreichen. In jeder Iteration der while-Schleife erhöhen wir den count um 1.

Nach Ausführung der while-Schleife haben wir die Anzahl der Elemente in der verknüpften Liste in der Variablen count. Sie können diese Logik wie in der Methode countElements() unten gezeigt implementieren.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
Number of elements in the linked list are: 4

Aktualisieren Sie einen Knoten in der verknüpften Liste in Python

Es kann zwei Situationen geben, um den Wert in einem Knoten in der verknüpften Liste zu aktualisieren.

  1. Wir müssen einen Wert ersetzen.
  2. Wir müssen dem Element an einer beliebigen Position in der verknüpften Liste einen neuen Wert zuweisen.

Ersetzen Sie einen Wert in der verknüpften Liste

Um einen Wert in der verknüpften Liste zu ersetzen, beginnen wir beim ersten Knoten und durchlaufen die verknüpfte Liste mit einer while-Schleife.

Wir werden prüfen, ob der current Knoten den Wert enthält, der an jedem Knoten ersetzt werden soll. Wenn ja, ersetzen wir den Wert im aktuellen Knoten durch den neuen Wert.

Auf diese Weise können wir das erste Vorkommen eines beliebigen Elements in der verknüpften Liste aktualisieren, wie in der Methode replaceElement() gezeigt.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 100 
The elements in the linked list are:
10 40 150 100

Aktualisieren Sie das Element an einer bestimmten Position in der verknüpften Liste

Um das Element an einer bestimmten Position in der verknüpften Liste zu aktualisieren, prüfen wir zunächst, ob die verknüpfte Liste leer ist. Wenn ja, kann es zwei Situationen geben.

Wenn die verknüpfte Liste leer ist und wir ein anderes Element als die erste Position aktualisieren müssen, benachrichtigen wir den Benutzer, dass dies nicht möglich ist.

Wenn die verknüpfte Liste leer ist und wir das Element an der ersten Position aktualisieren müssen, erstellen wir einen neuen Knoten mit dem angegebenen Element und weisen den Knoten dem Head der verknüpften Liste zu. Andernfalls initialisieren wir eine Variable counter auf 1.

Danach durchlaufen wir die verknüpfte Liste mit einer while-Schleife. In jeder Iteration der while-Schleife bewegen wir uns zum nächsten Knoten in der verknüpften Liste, inkrementieren die Variable counter um 1 und prüfen, ob wir die Position des Elements erreicht haben, das aktualisiert werden muss.

Wenn wir die Position erreichen, die aktualisiert werden muss, aktualisieren wir den Wert im aktuellen Knoten der verknüpften Liste und benachrichtigen den Benutzer.

Wenn wir die Position, die aktualisiert werden muss, nicht erreichen können und die while-Schleife beendet wird, benachrichtigen wir den Benutzer, dass nicht genügend Elemente vorhanden sind, und wir können den Wert nicht aktualisieren. Diese Logik kann wie unten gezeigt in der Methode updateAtPosition() implementiert werden.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()

Ausgabe:

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 100 30 
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30

Warum eine verknüpfte Liste in Python verwenden

  • Wenn Sie keinen wahlfreien Zugriff auf die Elemente benötigen, können verkettete Listen eine bessere Alternative sein. Sie sollten verknüpfte Listen anstelle von normalen Listen in Python verwenden, wenn wir Millionen von Elementen speichern müssen und keinen wahlfreien Zugriff benötigen.
  • Die tatsächliche Größe von Listen ist sehr groß im Vergleich zu der Anzahl der darin enthaltenen Elemente. Die tatsächliche Größe einer Liste beträgt etwa das 1,5-fache der Anzahl der darin enthaltenen Elemente. Es stellt sicher, dass wir genügend Speicher haben, um Elemente in die Liste einzufügen. Eine verknüpfte Liste erfordert jedoch keine zusätzlichen Leerzeichen.
  • Wenn wir ein Element in die verknüpfte Liste einfügen, ist nur eine Speicherung erforderlich. Listen erfordern auch zusammenhängende Speicherorte. Im Gegensatz dazu können Knoten einer verketteten Liste an jeder Stelle im physikalischen Speicher vorhanden sein. Sie sind über Referenzen verbunden.
  • Sie können sowohl Stack- als auch Queue-Datenstrukturen effizient implementieren, indem Sie verknüpfte Listen verwenden. Andererseits ist das Implementieren einer Warteschlange unter Verwendung einer Liste hinsichtlich der zeitlichen Komplexität kostspielig.

Vollständige verkettete Implementierungsliste in Python

Im Folgenden finden Sie den vollständigen Ausführungscode zum Implementieren einer verknüpften Liste in Python mit allen in diesem Artikel beschriebenen Methoden.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")

Fazit

In diesem Artikel haben wir die Datenstruktur der verknüpften Liste und ihre Implementierung in Python besprochen. Wir haben auch die Methoden für verschiedene Operationen in einer verknüpften Liste implementiert.

In diesem Artikel haben wir alle Operationen mithilfe von Methoden implementiert. Sie können jede Operation auch mit Funktionen implementieren, die den Head der verknüpften Liste als Eingabe nehmen und den Kopf nach Ausführung der erforderlichen Operationen zurückgeben.

Dies erfordert jedoch während der Ausführung mehr Ressourcen. Daher schlage ich vor, dass Sie den in diesem Artikel verwendeten Ansatz verwenden.

Autor: Aditya Raj
Aditya Raj avatar Aditya Raj avatar

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub

Verwandter Artikel - Python Data Structure