Imiter une liste de dictionnaires avec une liste chaînée en Python

Je commencerai cet article par mon processus de réflexion et ma visualisation. Une expérience (vous pouvez choisir de l'appeler ainsi) qui m'a ouvert les yeux pour mieux comprendre ce que sont les listes chaînées. Cela m'a fait arrêter de le considérer comme abstrait, en suivant le cliché (données et suivant) avec lequel il est toujours expliqué.

Processus de pensée et visualisation

Dernièrement, j'ai commencé à regarder le code d'un point de vue plus physique (POO comme on l'appelle habituellement). Cependant, le mien va au-delà des classes et des attributs ; J'ai commencé à écrire des étapes et des algorithmes avant chaque boucle while et for. J’en ai marre de me lancer dans des abstractions juste pour le plaisir. Cela m'a amené à essayer quelques choses supplémentaires, ce qui m'a appris quelques choses supplémentaires que je partagerai dans cet article.

Trois questions et réponses clés avant d'approfondir :

• Qu'est-ce qui constitue une liste chaînée ?
• À quoi ressemblent les nœuds ?
• À quoi ressemble une liste chaînée au début ?

Pour répondre à la première ; les nœuds constituent une liste chaînée.

Pour la deuxième question ; pensez à un nœud dans une liste chaînée comme une voiture tirant une autre voiture. Dans ce scénario, supposons que les deux voitures contiennent des marchandises. La deuxième voiture est attachée à l’arrière de la première voiture avec une chaîne. Un nœud fait cela dans une liste chaînée en conservant des données comme les marchandises ou les passagers dans les voitures. Ce type de données peut être simple comme un entier ou une chaîne ou une structure de données plus complexe. En même temps, chaque voiture dispose d'un connecteur (chaîne) la reliant à la prochaine voiture sur la route. Dans une liste chaînée, il s'agit de l'attribut suivant qui pointe vers l'adresse mémoire du nœud suivant ou du nœud avant (dans une liste doublement chaînée). Une liste n'est pas une liste chaînée sans l'attribut suivant.

Chaque voiture ne connaît que la voiture directement devant ou derrière elle (selon le type de liste chaînée). La dernière voiture n’a pas de chaîne, ce qui signifie qu’elle ne pointe vers rien. Dans une liste chaînée, cela est souvent représenté par Aucun.

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

Pour répondre à la troisième question ; le nœud principal démarre une liste chaînée au moment même où la première voiture démarre le remorquage.

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

Jusqu'à présent, nous avons examiné les bases d'une liste chaînée. Nous allons maintenant aborder la principale raison pour laquelle j'ai écrit cet article.

Introduction

Les structures de données intégrées de Python, telles que les listes et les dictionnaires, offrent des moyens flexibles de stocker et de gérer les données. Les listes nous permettent de stocker des séquences ordonnées, tandis que les dictionnaires nous permettent d'associer des clés à des valeurs pour un accès facile.

Dans cet article, nous explorerons comment créer une liste chaînée de type dictionnaire en utilisant la composition. Nous verrons des disparités dans l'utilisation de la mémoire entre notre liste chaînée de type dictionnaire et une liste de dictionnaires. Nous verrons également comment notre nœud peut obtenir un héritage de dict pour faire des instances de nœud de véritables dictionnaires. Tout cela dans le but de fournir plus de perspectives pour notre compréhension d'une liste chaînée.

Créer notre liste chaînée

Comme examiné précédemment, une liste chaînée est composée de nœuds. Ces nœuds ont chacun un segment de données et un segment suivant. Les données peuvent être simples comme une chaîne ou un entier, ou complexes.

Simple :

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

La classe Node (représentée par My_Int) a data et next comme attributs.

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

Je vais traiter d'un cas complexe dans cet article :

Complexe :

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

La classe de nœuds (représentée par My_Dict) contient plusieurs attributs : nom d'utilisateur, teint et suivant. **kwargs comme argument, permet aux méthodes d'accepter n'importe quel nombre d'arguments de mots-clés sans définir explicitement chacun d'entre eux.

Chaque nœud ne stocke pas seulement un seul élément de données, mais combine plusieurs éléments (nom d'utilisateur et teint) en un seul, ce qui le rend plus complexe qu'une structure de données de base comme un entier ou une chaîne.

Nous allons maintenant créer une classe My_List qui gérera une liste chaînée d'instances My_Dict. Il faut un attribut head. Cette tête est généralement le premier nœud qui initialise une liste chaînée.

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()

Cette classe fournit également une méthode d'insertion pour ajouter de nouvelles entrées de nœud à la fin.
Nous créons également ici une instance de My_Dict (qui est un nœud). My_List agira comme un conteneur pour les objets My_Dict dans une structure de liste chaînée. Chaque instance My_Dict est connectée par une référence suivante qui permet à My_List de gérer dynamiquement le parcours et l'insertion des instances My_Dict. Cela illustre fondamentalement la composition.

Après la création d'une instance My_Dict, on vérifie que la liste n'est pas vide en vérifiant la présence de la tête. Si le head n'est pas présent, cela signifie que la liste est vide, nous initialisons donc self.head comme nouveau nœud (qui est my_dict). Le return quitte alors immédiatement la fonction. Pas besoin d'exécuter davantage.

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

La ligne après le retour s'exécute lorsqu'il y avait un nœud auparavant dans la liste et que nous voulons insérer un nouveau nœud. Nous initialisons ce nœud last_dict en tant que head et celui-ci sera utilisé pour trouver le dernier nœud (la fin de la liste) afin que le nouveau nœud puisse y être ajouté. La boucle while parcourt la liste jusqu'à ce qu'elle atteigne le dernier nœud. Tant que last_dict.next n'est pas égal à None, il passe au nœud suivant en définissant last_dict = lastdict.next.

Enfin last_dict.next = my_dict ajoute my_dict à la fin de la liste pour terminer l'insertion. Une fois que nous savons que last_dict.next vaut None (c'est-à-dire que nous sommes au dernier nœud), nous y attachons my_dict.

Nous abordons maintenant la fonction traversée :

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

La fonction traverse parcourt chaque nœud de la liste chaînée et effectue une action (dans ce cas, l'impression) sur chaque nœud, de la tête à la fin. La méthode fournit une vue séquentielle de tous les nœuds de la liste.

Regardez le code complet ci-dessous :

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

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

Notre implémentation ci-dessus peut être considérée comme une liste chaînée personnalisée d'objets de type dictionnaire, mais elle est structurée différemment d'une liste typique de dictionnaires Python standard. Voici les points à noter :

• Classe My_Dict : chaque instance agit comme un objet de type dictionnaire avec des attributs (nom d'utilisateur et teint) et un pointeur suivant, lui permettant d'être lié à une autre instance My_Dict.
• Classe My_List : cette classe gère une liste chaînée d'instances My_Dict, en conservant l'en-tête et en fournissant une méthode d'insertion pour ajouter de nouvelles entrées à la fin. Chaque nœud est connecté au suivant via le pointeur suivant, simulant une structure de liste chaînée.

L'algorithme

Il est toujours bon d'avoir un algorithme lors de l'écriture du code. C’est ce qu’on appelle les mesures prises. J'aurais peut-être dû les écrire avant le code ci-dessus. Mais je voulais juste montrer d’abord la différence entre la liste chaînée clichée de tous les jours et un type plus complexe. Sans plus tarder, voici les étapes.

1. Créez une classe avec les attributs d'une structure de nœuds.
2. Créez une autre classe, appelez-la LinkedList (ou autre). Ajoutez la tête comme seul attribut. Faire head=Aucun.
3. Pour créer et insérer un nœud :
   • créez une instance de Node.
   • Si la liste est vide, laissez l'instance de nœud être la valeur de head.
   • Si la liste n'est pas vide, définissez le nœud précédent avec la valeur comme tête.
   • Avec vérification de l'état comme ; si l'attribut suivant du nœud précédent n'est pas Aucun, parcourez la liste.
   • Enfin, définissez le prochain nœud précédent pour qu'il pointe vers le nouveau nœud.
4. Pour parcourir la liste :
   • Créez un nœud temporaire et définissez head comme valeur de départ.
   • Boucle avec une condition si le nœud temporaire n'est pas Aucun.
   • Imprimer les données dans le nœud temporaire.
   • Déplacer le nœud temporaire vers le suivant
   • Enfin, à la fin, le suivant est Aucun, alors imprimez Aucun.
5. Créez des instances de classe selon vos besoins.

Comparaison avec une liste de dictionnaires

Nous allons maintenant comparer ce que nous avons ci-dessus avec une liste de dictionnaires Python en examinant quelques points :

• Structure et stockage :

Liste des dictionnaires : en Python, une liste de dictionnaires stocke chaque dictionnaire en tant qu'élément dans une structure de liste contiguë, rendant chaque dictionnaire accessible via un index.

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

Liste liée de dictionnaires : notre code utilise une structure de liste chaînée, où chaque nœud (instance My_Dict de type dictionnaire) contient une référence au nœud suivant plutôt que d'utiliser un stockage en mémoire contiguë. Ceci est plus efficace en mémoire pour les grandes listes si les éléments changent fréquemment, mais c'est plus lent pour l'accès par position.

• Accès et insertion : Liste de dictionnaires : dans une liste Python standard, l'accès aux éléments par index est O(1) (temps constant) car les listes Python sont des tableaux sous le capot. L'ajout d'un nouveau dictionnaire à la fin est généralement O(1) mais devient O(n) si un redimensionnement est requis.

Liste chaînée de dictionnaires : dans notre liste chaînée, l'accès à un élément nécessite un parcours (temps O(n)), car nous devons itérer nœud par nœud. L'insertion à la fin est également O(n) car nous devons trouver le dernier nœud à chaque fois. Cependant, l'insertion au début peut être O(1) puisque nous pouvons définir le nouveau nœud comme tête.

• Utilisation de la mémoire :

Liste de dictionnaires : une liste Python utilise plus de mémoire pour stocker les dictionnaires dans un bloc contigu, car chaque élément est stocké séquentiellement. La mémoire est allouée dynamiquement pour les listes Python, redimensionnant et copiant parfois la liste lorsqu'elle s'agrandit. Nous pouvons le prouver dans le code en utilisant le module sys :

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

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

Liste chaînée de dictionnaires : la liste chaînée utilise efficacement la mémoire pour chaque nœud car elle n'alloue de la mémoire que si nécessaire. Cependant, cela nécessite un espace supplémentaire pour la référence suivante dans chaque nœud.

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

D'après ce qui précède, nous pouvons voir la différence en octets ; 776 et 192.

Techniquement, ce ne sont pas des dictionnaires

Dans notre code, les instances My_Dict sont des objets de type dictionnaire plutôt que de véritables dictionnaires.

Voici quelques raisons :

• L'attribut suivant relie les instances My_Dict entre elles, les faisant davantage ressembler à des nœuds dans une liste chaînée qu'à des dictionnaires autonomes. Cet attribut suivant n'est pas une fonctionnalité que nous trouverions dans un dictionnaire classique.

  • Méthodes et comportement : Les objets de type dictionnaire (comme les instances My_Dict) peuvent avoir des méthodes et des comportements qui ressemblent à des dictionnaires mais ne sont techniquement pas des dictionnaires. Il leur manque des méthodes telles que .keys(), .values(), .items() et des opérations spécifiques au dictionnaire telles que le hachage. Si nous voulions que les objets My_Dict se comportent davantage comme des dictionnaires, nous pourrions hériter du dict intégré de Python pour implémenter des méthodes afin de leur donner des fonctionnalités de dictionnaire. Mais dans l’état actuel des choses, ces objets ressemblent à des dictionnaires, car ils stockent les données dans un style clé-valeur mais n’héritent pas et ne se comportent pas exactement comme les dictionnaires Python.

Vous trouverez ci-dessous un aperçu de la manière dont nous pouvons hériter de la classe dict :

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       

La première ligne importe Dict depuis le module de saisie de Python. Cela indique que My_Dict est un dictionnaire spécialisé.

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

La classe My_Dict hérite de dict, ce qui signifie qu'elle aura les propriétés d'un dictionnaire mais pourra être personnalisée.

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

Jetons un œil au constructeur :

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

__init__ initialise une instance de My_Dict avec les attributs de nom d'utilisateur et de teint. super().__init_() appelle le constructeur de la classe parent Dict. self['username'] = username et self['complexion'] = complexion stockent le nom d'utilisateur et le complexion sous forme d'entrées de dictionnaire, permettant d'accéder aux instances My_Dict comme un dictionnaire (par exemple, new_dict['username']). Il y a aussi un
attribut suivant initialisé sur Aucun, établissant une structure de liste chaînée en permettant à chaque instance My_Dict de se lier à une autre.

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()

La méthode ci-dessus remplace la méthode des clés de dict, lui permettant de renvoyer toutes les clés dans My_Dict. Utiliser super().keys() appelle le parent
Keys(), garantissant un comportement standard du dictionnaire.

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

Dans la méthode d'insertion de classe MyList, nous pouvons voir comment nous faisons en sorte que l'instance créée de notre dictionnaire présente le comportement du dictionnaire. Nous y enchaînons la méthode keys() et nous évaluons également la clé du nom d'utilisateur avec elle. Nous faisons cela dans les blocs if et else. Dans le bloc if, il imprime les clés du nœud principal et le nom d'utilisateur. Dans le bloc else, il imprime les clés des autres nœuds et le nom d'utilisateur des autres nœuds.

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

Dans la méthode traversée ci-dessus dans la compréhension du dictionnaire :

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       

Nous construisons un dictionnaire avec chaque paire clé-valeur de current_dict. current_dict = getattr(current_dict, 'next', None) passe au nœud suivant, en continuant jusqu'à ce que current_dict devienne None.

Remarque : en ce qui concerne l'utilisation de la mémoire, faire en sorte que notre classe hérite de dict signifie plus d'utilisation de la mémoire. Contrairement à la liste chaînée de nœuds de type dictionnaire que nous avons créée précédemment.

Conclusion

Le but de cet article est de fournir plus de perspectives et d'informations sur ce que sont les listes chaînées, au-delà de ce que je vois habituellement comme expliqué. Je n’étais pas innovant. J'expérimentais simplement le code, essayant de fournir plus d'informations à ceux qui pourraient le considérer comme trop abstrait. Cependant, j'aimerais savoir de la part de programmeurs plus expérimentés, quels pourraient être les inconvénients s'ils étaient utilisés ou lorsqu'ils étaient utilisés dans le passé.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!