Nachahmen einer Liste von Wörterbüchern mit einer verknüpften Liste in Python

Ich werde diesen Artikel mit meinem Denkprozess und meiner Visualisierung beginnen. Ein Experiment (Sie können es so nennen), das mir die Augen geöffnet hat, um mehr Klarheit darüber zu gewinnen, was verknüpfte Listen sind. Das hat mich dazu gebracht, es nicht mehr als abstrakt zu betrachten und mich an der klischeehaften Art und Weise (Daten und Weiter) zu orientieren, mit der es immer erklärt wird.

Denkprozess und Visualisierung

In letzter Zeit habe ich begonnen, Code aus einer eher physischen Perspektive zu betrachten (OOP, wie es normalerweise genannt wird). Allerdings geht meines über Klassen und Attribute hinaus; Ich habe vor jeder While- und For-Schleife angefangen, Schritte und Algorithmen aufzuschreiben. Ich habe es satt, mich nur um des Willens willen in Abstraktionen zu stürzen. Dies veranlasste mich dazu, noch ein paar weitere Dinge auszuprobieren, wodurch ich weitere Dinge lernte, die ich in diesem Artikel teilen werde.

Drei wichtige Fragen und Antworten, bevor wir näher darauf eingehen:

• Was macht eine verknüpfte Liste aus?
• Wie sehen Knoten aus?
• Wie sieht eine verknüpfte Liste am Anfang aus?

Um die erste Frage zu beantworten: Knoten bilden eine verknüpfte Liste.

Zur zweiten Frage; Stellen Sie sich einen Knoten in einer verknüpften Liste wie ein Auto vor, das ein anderes Auto zieht. Gehen Sie in diesem Szenario davon aus, dass beide Autos Güter enthalten. Der zweite Wagen ist mit einer Kette am Heck des ersten Wagens befestigt. Ein Knoten tut dies in einer verknüpften Liste, indem er Daten wie die Waren oder Passagiere in den Autos speichert. Dieser Datentyp kann einfach sein, wie eine Ganzzahl oder Zeichenfolge, oder eine komplexere Datenstruktur. Gleichzeitig verfügt jedes Auto über eine Verbindung (Kette), die es mit dem nächsten Auto auf der Straße verbindet. In einer verknüpften Liste ist dies das nächste Attribut, das auf die Speicheradresse des nächsten Knotens oder des Knotens davor (in einer doppelt verknüpften Liste) zeigt. Eine Liste ist keine verknüpfte Liste ohne das nächste Attribut.

Jedes Auto kennt nur das Auto direkt vor oder hinter ihm (abhängig von der Art der verknüpften Liste). Das letzte Auto hat keine Kette, weist also auf nichts hin. In einer verknüpften Liste wird dies oft durch None dargestellt.

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

Um die dritte Frage zu beantworten: Der Hauptknoten startet eine verknüpfte Liste, genau wie das erste Auto mit dem Abschleppen beginnt.

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

Bisher haben wir uns mit den Grundlagen einer verknüpften Liste befasst. Wir werden nun auf den Hauptgrund eingehen, warum ich diesen Artikel geschrieben habe.

Einführung

Die in Python integrierten Datenstrukturen wie Listen und Wörterbücher bieten flexible Möglichkeiten zum Speichern und Verwalten von Daten. Mithilfe von Listen können wir geordnete Sequenzen speichern, während Wörterbücher es uns ermöglichen, Schlüssel mit Werten zu koppeln, um den Zugriff zu erleichtern.

In diesem Artikel erfahren Sie, wie Sie mithilfe von Komposition eine wörterbuchähnliche verknüpfte Liste erstellen. Wir werden Unterschiede in der Speichernutzung zwischen unserer wörterbuchähnlichen verknüpften Liste und einer Liste von Wörterbüchern feststellen. Wir werden auch sehen, wie unser Knoten eine Vererbung von dict erhalten kann, um die Knoteninstanzen zu echten Wörterbüchern zu machen. All dies mit dem Ziel, mehr Perspektiven für unser Verständnis einer verknüpften Liste zu bieten.

Erstellen unserer verlinkten Liste

Wie bereits erläutert, besteht eine verknüpfte Liste aus Knoten. Diese Knoten haben jeweils ein Datensegment und ein Folgesegment. Die Daten können einfach wie eine Zeichenfolge oder Ganzzahl oder komplex sein.

Einfach:

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

Die Node-Klasse (dargestellt durch My_Int) hat Daten und Next als Attribute.

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

In diesem Artikel wird ein komplexer Fall behandelt:

Komplex:

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

Die Knotenklasse (dargestellt durch My_Dict) enthält mehrere Attribute: Benutzername, Teint und Weiter. **kwargs als Argument ermöglicht es Methoden, eine beliebige Anzahl von Schlüsselwortargumenten zu akzeptieren, ohne jedes einzelne explizit zu definieren.

Jeder Knoten speichert nicht nur ein einzelnes Datenelement, sondern kombiniert mehrere Teile (Benutzername und Teint) zu einem, was es komplexer macht als eine grundlegende Datenstruktur wie eine Ganzzahl oder eine Zeichenfolge.

Wir erstellen nun eine My_List-Klasse, die eine verknüpfte Liste von My_Dict-Instanzen verwaltet. Es benötigt ein Head-Attribut. Dieser Kopf ist normalerweise der erste Knoten, der eine verknüpfte Liste initialisiert.

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

Diese Klasse bietet auch eine Einfügemethode zum Hinzufügen neuer Knoteneinträge am Ende.
Wir erstellen hier auch eine Instanz von My_Dict (das ist ein Knoten). My_List fungiert als Container für My_Dict-Objekte in einer verknüpften Listenstruktur. Jede My_Dict-Instanz ist durch eine nächste Referenz verbunden, die es My_List ermöglicht, das Durchlaufen und Einfügen von My_Dict-Instanzen dynamisch zu verwalten. Dies ist im Grunde ein Beispiel für die Komposition.

Nach der Erstellung einer My_Dict-Instanz überprüfen wir, ob die Liste nicht leer ist, indem wir prüfen, ob der Kopf vorhanden ist. Wenn der Kopf nicht vorhanden ist, bedeutet dies, dass die Liste leer ist. Daher initialisieren wir self.head als neuen Knoten (der my_dict ist). Der Return beendet dann sofort die Funktion. Keine weitere Ausführung erforderlich.

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

Die Zeile nach return läuft, wenn zuvor ein Knoten in der Liste vorhanden war und wir einen neuen Knoten einfügen möchten. Wir initialisieren diesen Knoten last_dict als head und dieser wird verwendet, um den letzten Knoten (das Ende der Liste) zu finden, damit der neue Knoten dort angehängt werden kann. Die while-Schleife iteriert die Liste, bis sie den letzten Knoten erreicht. Solange last_dict.next nicht gleich None ist, wird zum nächsten Knoten verschoben, indem last_dict = lastdict.next gesetzt wird.

Schließlich hängt last_dict.next = my_dict my_dict an das Ende der Liste und vervollständigt die Einfügung. Sobald wir wissen, dass last_dict.next None ist (d. h. wir sind am letzten Knoten), hängen wir dort my_dict an.

Wir befassen uns nun mit der Polygonzugfunktion:

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

Die Traverse-Funktion durchläuft jeden Knoten in der verknüpften Liste und führt eine Aktion (in diesem Fall Drucken) auf jedem Knoten vom Kopf bis zum Ende aus. Die Methode bietet eine sequentielle Ansicht aller Knoten in der Liste.

Sehen Sie sich den vollständigen Code unten an:

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

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

Unsere obige Implementierung kann man sich als eine benutzerdefinierte verknüpfte Liste von wörterbuchähnlichen Objekten vorstellen, sie ist jedoch anders strukturiert als eine standardmäßige Python-typische Liste von Wörterbüchern. Hier sind Punkte zu beachten:

• My_Dict-Klasse: Jede Instanz fungiert als wörterbuchähnliches Objekt mit Attributen (Benutzername und Hautfarbe) und einem nächsten Zeiger, sodass sie mit einer anderen My_Dict-Instanz verknüpft werden kann.
• My_List-Klasse: Diese Klasse verwaltet eine verknüpfte Liste von My_Dict-Instanzen, behält den Kopf bei und stellt eine Einfügemethode bereit, um am Ende neue Einträge hinzuzufügen. Jeder Knoten ist über den nächsten Zeiger mit dem nächsten verbunden, wodurch eine verknüpfte Listenstruktur simuliert wird.

Der Algorithmus

Es ist immer gut, beim Schreiben von Code einen Algorithmus zu haben. Dies nennt man die durchgeführten Schritte. Vielleicht hätte ich sie vor dem obigen Code schreiben sollen. Aber ich wollte zunächst nur den Unterschied zwischen der alltäglichen Klischee-verknüpften Liste und einem komplexeren Typ zeigen. Nachfolgend finden Sie ohne weitere Umschweife die Schritte.

1. Erstellen Sie eine Klasse mit den Attributen einer Knotenstruktur.
2. Erstellen Sie eine weitere Klasse und nennen Sie sie LinkedList (oder was auch immer). Kopf als einziges Attribut hinzufügen. Machen Sie head=None.
3. So erstellen und fügen Sie einen Knoten ein:
   • Erstellen Sie eine Instanz von Node.
   • Wenn die Liste leer ist, sei die Knoteninstanz der Wert von head.
   • Wenn die Liste nicht leer ist, setzen Sie den vorherigen Knoten mit dem Wert als Kopf.
   • Mit Zustandsprüfung als; Wenn das nächste Attribut des vorherigen Knotens nicht None ist, durchlaufen Sie die Liste.
   • Stellen Sie abschließend den nächsten Knoten des vorherigen Knotens so ein, dass er auf den neuen Knoten zeigt.
4. Um die Liste zu durchlaufen:
   • Erstellen Sie einen temporären Knoten und legen Sie head als Startwert fest.
   • Schleife mit der Bedingung, dass der temporäre Knoten nicht „Keine“ ist.
   • Daten im temporären Knoten drucken.
   • Temporären Knoten zum nächsten verschieben
   • Am Ende kommt als nächstes None, also geben Sie None ein.
5. Erstellen Sie nach Bedarf Klasseninstanzen.

Vergleich mit einer Liste von Wörterbüchern

Wir werden nun das, was wir oben haben, mit einer Python-Liste von Wörterbüchern vergleichen, indem wir uns einige Punkte ansehen:

• Struktur und Lagerung:

Liste von Wörterbüchern: In Python speichert eine Liste von Wörterbüchern jedes Wörterbuch als Element in einer zusammenhängenden Listenstruktur, wodurch jedes Wörterbuch über einen Index zugänglich ist.

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

Verknüpfte Liste von Wörterbüchern: Unser Code verwendet eine verknüpfte Listenstruktur, bei der jeder Knoten (eine wörterbuchähnliche My_Dict-Instanz) einen Verweis auf den nächsten Knoten enthält, anstatt zusammenhängenden Speicher zu verwenden. Dies ist bei großen Listen speichereffizienter, wenn sich Elemente häufig ändern, ist jedoch langsamer für den Zugriff nach Position.

• Zugriff und Einfügung: Liste der Wörterbücher: In einer Standard-Python-Liste ist der Zugriff auf Elemente über den Index O(1) (konstante Zeit), da Python-Listen unter der Haube Arrays sind. Das Hinzufügen eines neuen Wörterbuchs am Ende ist normalerweise O(1), wird aber zu O(n), wenn eine Größenänderung erforderlich ist.

Verknüpfte Liste von Wörterbüchern: In unserer verknüpften Liste erfordert der Zugriff auf ein Element eine Durchquerung (O(n)-Zeit), da wir Knoten für Knoten iterieren müssen. Das Einfügen am Ende ist ebenfalls O(n), da wir jedes Mal den letzten Knoten finden müssen. Das Einfügen am Anfang kann jedoch O(1) sein, da wir den neuen Knoten als Kopf festlegen können.

• Speichernutzung:

Liste von Wörterbüchern: Eine Python-Liste benötigt mehr Speicher zum Speichern von Wörterbüchern in einem zusammenhängenden Block, da jedes Element nacheinander gespeichert wird. Der Speicher wird für Python-Listen dynamisch zugewiesen, wobei manchmal die Größe der Liste geändert und die Liste kopiert wird, wenn sie wächst. Wir können dies im Code mit dem sys-Modul beweisen:

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

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

Verknüpfte Liste von Wörterbüchern: Die verknüpfte Liste nutzt den Speicher für jeden Knoten effizient, da sie den Speicher nur nach Bedarf zuweist. Es erfordert jedoch zusätzlichen Platz für die nächste Referenz in jedem Knoten.

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

Aus dem Obigen können wir den Unterschied in Bytes erkennen; 776 und 192.

Technisch gesehen keine Wörterbücher

In unserem Code sind die My_Dict-Instanzen eher wörterbuchähnliche Objekte als echte Wörterbücher.

Hier sind einige Gründe dafür:

• Das nächste Attribut verknüpft My_Dict-Instanzen miteinander und macht sie eher zu Knoten in einer verknüpften Liste als zu eigenständigen Wörterbüchern. Dieses nächste Attribut ist keine Funktion, die wir in einem normalen Wörterbuch finden würden.

  • Methoden und Verhalten: Wörterbuchähnliche Objekte (wie My_Dict-Instanzen) können Methoden und Verhaltensweisen haben, die Wörterbüchern ähneln, aber technisch gesehen keine Wörterbücher sind. Ihnen fehlen Methoden wie .keys(), .values(), .items() und wörterbuchspezifische Operationen wie Hashing. Wenn wir wollten, dass sich My_Dict-Objekte eher wie Wörterbücher verhalten, könnten wir von Pythons integriertem Diktat für die Implementierung von Methoden erben, um ihnen Wörterbuchfunktionalität zu verleihen. Aber so wie es aussieht, sind diese Objekte wörterbuchähnlich, da sie Daten in einem Schlüsselwertstil speichern, aber nicht von Python-Wörterbüchern erben oder sich genau wie diese verhalten.

Unten sehen wir, wie wir von der Diktklasse erben können:

class My_List: #manager
    def __init__(self):
        self.head=None

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

Die erste Zeile importiert Dict aus dem Typisierungsmodul von Python. Dies weist darauf hin, dass My_Dict ein spezialisiertes Wörterbuch ist.

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

Die Klasse My_Dict erbt von dict, was bedeutet, dass sie die Eigenschaften eines Wörterbuchs hat, aber angepasst werden kann.

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

Lassen Sie uns einen Blick auf den Konstruktor werfen:

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

__init__ initialisiert eine Instanz von My_Dict mit den Attributen Benutzername und Teint. super().__init_() ruft den Konstruktor der übergeordneten Dict-Klasse auf. self['username'] = username und self['complexion'] = complexion speichern Benutzername und complexion als Wörterbucheinträge, sodass auf My_Dict-Instanzen wie auf ein Wörterbuch zugegriffen werden kann (z. B. new_dict['username']). Es gibt auch ein
Das nächste Attribut wird als „Keine“ initialisiert und richtet eine verknüpfte Listenstruktur ein, indem jede My_Dict-Instanz mit einer anderen verknüpft werden kann.

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

Die obige Methode überschreibt die Methode „keys“ von dict und ermöglicht so die Rückgabe aller Schlüssel in „My_Dict“. Mit super().keys() wird das übergeordnete Element
aufgerufen Die Methode „keys()“ stellt das Standardverhalten des Wörterbuchs sicher.

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

In der Einfügemethode der MyList-Klasse können wir sehen, wie wir dafür sorgen, dass die erstellte Instanz unseres Wörterbuchs Wörterbuchverhalten zeigt. Wir verketten die Methode „keys()“ damit und bewerten damit auch den Benutzernamenschlüssel. Dies machen wir in den if- und else-Blöcken. Im if-Block werden die Schlüssel des Hauptknotens und der Benutzername gedruckt. Im else-Block werden die Schlüssel der anderen Knoten und der Benutzername der anderen Knoten gedruckt.

class My_List: #manager
    def __init__(self):
        self.head=None

In der obigen Traverse-Methode innerhalb des Wörterbuchverständnisses:

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

Wir erstellen ein Wörterbuch mit jedem Schlüssel-Wert-Paar aus current_dict. current_dict = getattr(current_dict, 'next', None) geht zum nächsten Knoten und fährt fort, bis current_dict zu None wird.

Hinweis: Wenn es um die Speichernutzung geht, bedeutet die Tatsache, dass unsere Klasse von dict erbt, eine höhere Speichernutzung. Im Gegensatz zur verknüpften Liste wörterbuchähnlicher Knoten, die wir zuvor erstellt haben.

Abschluss

Das Ziel dieses Artikels ist es, mehr Perspektiven und Einblicke in verlinkte Listen zu bieten, als ich es normalerweise als Erklärung verstehe. Ich war nicht innovativ. Ich habe nur mit Code experimentiert und versucht, denjenigen, die ihn vielleicht für zu abstrakt halten, mehr Einblick zu geben. Ich würde jedoch gerne von erfahreneren Programmierern wissen, welche Nachteile es haben könnte, wenn es oder in der Vergangenheit verwendet wird.

Das obige ist der detaillierte Inhalt vonNachahmen einer Liste von Wörterbüchern mit einer verknüpften Liste in Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!