Bonjour encore! En prévision du début du cours de développeur Python, nous avons préparé pour vous un petit matériel d'auteur sur des listes liées en Python.
Python est un langage très pratique et multiforme, mais par défaut, il n'a pas une telle structure de données comme une liste liée ou LinkedList. Aujourd'hui, je vais partager mes meilleures pratiques sur ce sujet et parler un peu de cette structure de données. Cet article sera intéressant pour ceux qui rencontrent pour la première fois le sujet des listes chaînées et veulent comprendre comment ils fonctionnent d'un point de vue algorithmique.
Qu'est-ce qu'une LinkedList?
Une LinkedList ou une liste liée est une structure de données. Une liste liée offre la possibilité de créer une file d'attente bidirectionnelle à partir de n'importe quel élément. Chaque élément d'une telle liste est considéré comme un nœud. En fait, un nœud a sa valeur, ainsi que deux liens vers les nœuds précédents et suivants. Autrement dit, la liste est «liée» par des nœuds qui permettent de monter ou de descendre dans la liste. En raison de ces fonctionnalités structurelles, vous pouvez organiser une pile, une file d'attente ou une double file d'attente à partir d'une liste liée.
Visualisons les définitions sèches. Maintenant, nous avons des chats assis dans des boîtes. Et sur chaque boîte, il est indiqué ce qu'il est en ordre et ce qu'il doit représenter.
Ce que nous ferons avec une liste chaînée:- Vérifiez si tel ou tel élément y est contenu;
- Ajoutez des nœuds à la fin;
- Obtenez la valeur d'un nœud par index;
- Supprimez les nœuds.
En fait, il existe beaucoup plus d'options pour travailler avec eux, mais nous nous attarderons sur la mise en œuvre de ces étapes de base. Ayant compris par quel principe ils sont construits, vous pouvez vous-même mettre en œuvre facilement vos propres méthodes.
Vous devrez commencer par créer deux classes:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
Dans le cas général, nous avons un nœud qui a une certaine valeur à l'intérieur - un chat et un lien vers le nœud suivant. Autrement dit, dans la classe Box, respectivement, il y a un chat et un lien vers la boîte suivante. Comme toute liste, le cohérent a aussi un début, à savoir la tête. Puisqu'il n'y a rien au départ, l'élément de départ est défini sur Aucun.
L'élément est-il dans la liste
Commençons par un simple. Pour vérifier s'il y a un chat particulier dans l'une des cases situées en série, vous devez parcourir toute la liste, en vérifiant la valeur existante avec les valeurs de l'élément dans la liste.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Ajouter un nœud à la fin de la liste
Vous devez d'abord créer une nouvelle boîte et y mettre déjà un nouveau chat. Après cela, vous devez vérifier, à partir du début de la liste liée, s'il existe un lien vers le suivant dans le nœud actuel et s'il y en a un, puis y accéder, sinon le nœud est le dernier, vous devez donc créer un lien vers le nœud suivant et y mettre la même nouvelle boîte, que nous avons créé.
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Obtenir un nœud par index
Pour l'index catIndex, nous voulons obtenir un nœud de boîte, mais comme les nœuds ne sont pas fournis avec un tel index, nous devons trouver une sorte de remplacement, à savoir une variable qui agira comme un index. Cette variable est boxIndex. Nous parcourons toute la liste et vérifions le "numéro de série" du nœud, et s'il correspond à l'index souhaité, nous produisons le résultat.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Supprimer le nœud
Nous considérons ici la suppression d'un élément non pas par index, mais par valeur, afin d'introduire au moins une certaine variété.
La recherche commence à partir du début de la liste, c'est-à-dire à partir de la première case consécutive, et continue jusqu'à ce que les cases soient épuisées, c'est-à-dire jusqu'à ce que le headcat devienne Aucun. Nous vérifions si la valeur stockée dans le nœud actuel correspond à celle que nous voulons supprimer. Sinon, nous allons simplement de l'avant. Cependant, s'il correspond, nous le supprimons et «re-lions» les liens, c'est-à-dire que nous supprimons la N-ème case, tandis que la N-1 fait maintenant référence à la N + 1.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
C'est tout, merci d'avoir lu le matériel! En fait, la structure LinkedList n'est pas compliquée et il est important de comprendre comment elle fonctionne de l'intérieur. Bien sûr, en Python, il aurait pu être implémenté dans des expressions lambda, il aurait pris beaucoup moins de place, mais ici j'ai cherché à expliquer sa structure et le principe de son fonctionnement en Python aussi détaillé que possible, plutôt que de rechercher l'optimisation.
Le code source peut être
trouvé ici .