Detaillierte Erläuterung der Verwendung verknüpfter Listendefinitionen von Python-Datenstrukturen und -Algorithmen

Dieser Artikel stellt hauptsächlich die Definition und Verwendung verknüpfter Listen in Python-Datenstrukturen und -Algorithmen vor. Er analysiert die Definitionen, Verwendungsmethoden und zugehörigen Vorsichtsmaßnahmen von einfach verknüpften Listen, zirkulär verknüpften Listen usw. anhand spezifischer Beispiele Bei Bedarf können Sie darauf verweisen.

Die Beispiele in diesem Artikel beschreiben die Definition und Verwendung verknüpfter Listen in Python-Datenstrukturen und -Algorithmen. Teilen Sie es wie folgt mit allen als Referenz:

Dieser Artikel erklärt Ihnen Folgendes:

(1) Verwenden Sie ausgehend von der Definition verknüpfter Listenknoten Klassenmethoden und objektorientierte Ideen zum Erstellen verknüpfter Listen Design

(2) Randbedingungen, die bei der Implementierung von Mitgliedsfunktionen wie Einfügen und Löschen verknüpfter Listenklassen berücksichtigt werden müssen,
prepend (Kopfeinfügung), Pop (Kopflöschung), append (Endeinfügung), pop_last (Endlöschung)

2.1 Einfügen:

Leere verknüpfte Liste
Die Länge der verknüpften Liste beträgt 1
Einfügen bis zum Ende

2.2 Löschen

Leere verknüpfte Liste
Die Länge der verknüpften Liste beträgt 1
Löschen Sie das Endelement

(3) Zahlreiche Variationen von einfach verknüpfter Liste zu einfach verknüpfter Liste:

Einfach verknüpfte Liste mit Endknoten
Zyklische einfach verknüpfte Liste
Doppelt verknüpfte Liste

1. Definition von verknüpften Listenknoten

class LNode:
 def __init__(self, elem, next_=None):
  self.elem = elem
  self.next = next_

2. Implementierung einer einfach verknüpften Liste

Konzentrieren Sie sich auf das Verständnis der Implementierung des Einfügens und Löschens und die Randbedingungen, die berücksichtigt werden müssen:

class LinkedListUnderflow(ValueError):
 pass
class LList:
 def __init__(self):
  self._head = None
 def is_empty(self):
  return self._head is None
 def prepend(self, elem):
  self._head = LNode(elem, self._head)
 def pop(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop')
  e = self._head.elem
  self._head = self._head.next
  return e
 def append(self, elem):
  if self._head is None:
   self._head = LNode(elem)
   return
  p = self._head
  while p.next is not None:
   p = p.next
  p.next = LNode(elem)
 def pop_last(self):
  if self._head is None:
   raise LinkedListUnderflow('in pop_last')
  p = self._head
  if p.next is None:
   e = p.elem
   self._head = None
   return e
  while p.next.next is not None:
   p = p.next
  e = p.next.elem
  p.next = None
  return e

Einfache Zusammenfassung:

(0) Voraussetzung für den Zugriff auf p.next.next ist, dass p.next nicht leer ist. (1) Tail-Einfügung: Wenn die verknüpfte Liste nicht leer ist, muss nur der Tail-Zeiger geändert werden Knoten;
(2) Löschen des Schwanzes. Wenn die Länge der verknüpften Liste nicht leer ist, muss nur der Zeiger des vorletzten Knotens geändert werden.

Einfache Variante der einfach verknüpften Liste: einfach verknüpfte Liste mit Endknoten

class LList1(LList):
 def __init__(self):
  LList.__init__(self)
  self._rear = None
 ...

Alles, was wir umschreiben müssen, ist:

Kopfeinfügung, Schwanzeinfügung, Schwanzlöschung

def prepend(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._head = LNode(elem, self._head)
def append(self, elem):
 if self._head is None:
  self._head = LNode(elem)
  self._rear = self._head
 else:
  self._rear.next = LNode(elem)
  self._rear = self._rear.next
def pop_last(self):
 if self._head is None:
  raise LinkedListUnderflow('in pop_last')
 p = self._head
 if p.next is None:
  e = p.elem
  self._head = None
  return e
 while p.next.next is not None:
  p = p.next
 e = p.next.elem
 self._rear = p
 p.next = None
 return e

Variation der einfach verknüpften Liste: zyklische einfach verknüpfte Liste

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Verwendung verknüpfter Listendefinitionen von Python-Datenstrukturen und -Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!