Python-Programm: Elemente an der ersten und letzten Position der verknüpften Liste hinzufügen

In Python ist eine verknüpfte Liste eine lineare Datenstruktur, die aus einer Folge von Knoten besteht, wobei jeder Knoten einen Wert und einen Verweis auf den nächsten Knoten in der verknüpften Liste enthält.

In diesem Artikel besprechen wir, wie man in Python Elemente an der ersten und letzten Position einer verknüpften Liste hinzufügt.

Verknüpfte Liste in Python

Eine verknüpfte Liste ist eine Referenzdatenstruktur, die zum Speichern einer Reihe von Elementen verwendet wird. In gewisser Weise ähnelt es einem Array, aber in einem Array werden die Daten an zusammenhängenden Speicherorten gespeichert, während in einer verknüpften Liste die Daten dieser Bedingung nicht unterliegen. Das bedeutet, dass die Daten nicht sequentiell, sondern zufällig im Speicher abgelegt werden.

Dies wirft eine Frage auf: Wie können wir auf die Elemente in einer verknüpften Liste zugreifen? Die Antwort ist ganz intuitiv: In einer verknüpften Liste zeigt ein Element bis zum Ende der Liste auf ein anderes.

Der Anfang und das Ende der Liste gelten als Sonderpositionen. Der Anfang der Liste wird Kopf genannt, er zeigt auf das erste Element und das letzte Element ist insofern etwas Besonderes, als es auf NULL zeigt.

Head -> data_1 -> data_2 -> … -> data_n -> NULL

Da wir nun wissen, wie man auf den Anfang und das Ende einer verknüpften Liste zugreift, sehen wir uns an, wie man über die Elemente iteriert und auf die Daten in der verknüpften Liste zugreift.

Das Durchlaufen einer verknüpften Liste ist sehr einfach. Wir beginnen einfach von vorne und besuchen den nächsten Knoten. Wir wiederholen diesen Vorgang, bis wir einen Knoten finden, dessen nächster Knoten NULL ist. Für den Zugriff auf Daten in einem Knoten verwenden wir den Pfeiloperator „->“.

Head->data

Jetzt haben wir das nötige Verständnis, um mit der Lösung dieses Problems zu beginnen.

Element am Anfang hinzufügen

Um die Daten am Anfang der verknüpften Liste hinzuzufügen, müssen wir den Kopf der verknüpften Liste berücksichtigen. Immer wenn wir einen Knoten am Anfang der verknüpften Liste hinzufügen, wird die verknüpfte Liste mit dem neu hinzugefügten Knoten geändert der erste Knoten/Kopf der Liste

Algorithmus

Schritt 1 – Erstellen Sie den neuen Knoten

Schritt 2 – Daten zum neu erstellten Knoten hinzufügen

Schritt 3 – Aktualisieren Sie den Link des neuen Knotens und verweisen Sie ihn auf den aktuellen Hauptknoten

Schritt 4 – Setzen Sie nun den Kopfzeiger auf den neu erstellten Knoten

HINWEIS – Die Reihenfolge dieser Schritte ist sehr wichtig, denn wenn Sie den neu erstellten Knoten zuerst als Hauptknoten festlegen, können wir den Link des neuen Knotens nicht aktualisieren, der idealerweise auf den vorherigen Hauptknoten verweisen sollte .

Beispiel

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print('')
   def addBeginList(self, data):
      tempNode = Node(data)
      tempNode.nextNode = self.headNode
      self.headNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before adding element : ")
newLinkedList.showList()
newLinkedList.addBeginList(10)
newLinkedList.addBeginList(25)
print("Printing the elements after adding at the beginning of the list")
newLinkedList.showList()

Ausgabe

Printing the list before adding any element :
\
Printing the elements after adding at the beginning of the list
25-10-\

Element am Ende hinzufügen

Das Hinzufügen von Elementen am Ende unterscheidet sich logisch vom Hinzufügen am Anfang der Liste. Dieses Mal müssen wir auf den letzten Knoten der Liste zugreifen, d. h. auf den Kopf

Das Problem besteht nun darin, zu prüfen, ob die Liste, zu der wir Elemente hinzufügen möchten, eine leere Liste ist oder ob sie bereits einige Elemente enthält.

Wenn die Liste leer ist, ist der neue Knoten der erste Knoten für die Liste, und im anderen Fall ist es der letzte Knoten. Dazu müssen wir prüfen, ob der Hauptknoten „Keine“ ist oder nicht „Leer behandelt“ ist „Keine“ und auch sonst nicht „leer“.

Algorithmus

Schritt 1 – Erstellen Sie einen neuen Knoten.

Schritt 2 – Daten zum Datenabschnitt des Knotens hinzufügen.

Schritt 3 – Stellen Sie sicher, dass der nächste Knoten des neu erstellten Knotens auf einen Keine- oder Nullzeiger zeigt.

Schritt 4 – Wenn die Liste leer ist, verwenden Sie den neu erstellten Knoten als Kopfknoten.

Schritt 5 – Ansonsten bis zum Ende der Liste, dem letzten Knoten, durchlaufen.

Schritt 6 – Setzen Sie den nächsten Knoten des letzten Knotens auf den neu erstellten Knoten.

Beispiel

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print("")
   def addEndList(self, data):
      tempNode = Node(data)
      if self.headNode is None:
         self.headNode = tempNode
      else:
         n = self.headNode
         while n.nextNode is not None:
            n = n.nextNode
            n.nextNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before insertion : ")
newLinkedList.showList()
newLinkedList.addEndList(25)
newLinkedList.addEndList(10)
print("Printing the list after adding elements at the end of the list : ")
newLinkedList.showList()

Ausgabe

Printing the list before insertion :
\
Printing the list after adding elements at the end of the list :
25-10-\

Fazit

In diesem Artikel haben wir besprochen, wie man Python-Klassen verwendet, um eine

verknüpfte Liste zu implementieren und wie man Elemente zu einer verknüpften Liste hinzufügt. Wir haben uns darauf konzentriert, Elemente am Anfang und Ende der Liste hinzuzufügen.

Das obige ist der detaillierte Inhalt vonPython-Programm: Elemente an der ersten und letzten Position der verknüpften Liste hinzufügen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!