Geekflare est soutenu par son public. Nous pouvons percevoir des commissions d'affiliation sur les liens d'achat présents sur ce site.
En Développement Dernière mise à jour : 25 septembre 2023
Partager sur :
Invicti Web Application Security Scanner - la seule solution qui offre une vérification automatique des vulnérabilités avec Proof-Based Scanning™.

Les structures de données jouent un rôle clé dans le monde de la programmation. Elles nous aident à organiser nos données de manière à pouvoir les utiliser efficacement.

Dans ce tutoriel, nous allons apprendre à connaître la liste simple et la liste double.

Une liste chaînée est une structure de données linéaire. Elle ne stocke pas les données dans des emplacements mémoire contigus comme les tableaux. Chaque élément d'une liste chaînée est appelé nœud et est connecté à l'aide de pointeurs. Le premier nœud de la liste chaînée est appelé tête.

La taille de la liste chaînée est dynamique. Nous pouvons donc avoir le nombre de nœuds que nous voulons, à moins que l'espace de stockage ne soit disponible dans le périphérique.

Il existe deux types de listes chaînées. Voyons le tutoriel détaillé sur ces deux types de listes, un par un.

#1. Liste liée simple

Une liste chaînée simple contient un seul pointeur connecté au nœud suivant de la liste chaînée. Nous devons stocker les données et le pointeur pour chaque nœud de la liste chaînée.

Le dernier nœud de la liste chaînée contient nul comme pointeur suivant pour représenter la fin de la liste chaînée.

Vous pouvez voir l'illustration d'une liste liée ci-dessous.

Nous comprenons à présent parfaitement ce qu'est une liste chaînée. Voyons les étapes pour l'implémenter en Python.

Implémentation d'une liste chaînée simple

1. La première étape consiste à créer le nœud de la liste chaînée.

Comment le créer ?

En Python, nous pouvons facilement créer le nœud en utilisant la classe. La classe contient des données et un pointeur pour le nœud suivant.

Regardez le code du nœud.

class Node :

def __init__(self, data) :
## données du noeud
self.data = data

## pointeur suivant
self.next = None

Nous pouvons créer un noeud avec n'importe quel type de données en utilisant la classe ci-dessus. Nous le verrons dans un instant.

Maintenant, nous avons le nœud avec nous. Ensuite, nous devons créer une liste chaînée avec plusieurs nœuds. Créons une autre classe pour une liste chaînée.

2. Créez une classe appelée Liste de liens avec head initialisé à Aucun. Voyez le code ci-dessous.

class LinkedList :

def __init__(self) :
## initialisation de la tête avec None
self.head = None

3. Nous disposons des classes Nœud et Liste de liens . Comment insérer un nouveau nœud dans la liste chaînée ? Une réponse simple pourrait être d'utiliser une méthode de la classe Liste de liens . Oui, ce serait bien. Écrivons une méthode pour insérer un nouveau nœud dans la liste chaînée.

Pour insérer un nouveau nœud dans la liste chaînée, nous devons suivre certaines étapes.

Voyons-les.

  • Vérifiez si la tête est vide ou non.
  • Si la tête est vide, assignez le nouveau nœud à la tête.
  • Si la tête n'est pas vide, récupérez le dernier nœud de la liste chaînée.
  • Attribuez le nouveau nœud au pointeur suivant du dernier nœud.

Voyons le code permettant d'insérer un nouveau nœud dans la liste chaînée.

class LinkedList :

####

def insert(self, new_node) :
## vérifier si la tête est vide ou non
if self.head :
## obtenir le dernier noeud
last_node = self.head
while last_node != None :
last_node = last_node.next

## assigner le nouveau nœud au pointeur suivant du dernier nœud
last_node.next = new_node

else :
## la tête est vide
## assigner le nœud à la tête
self.head = new_node

Nous avons terminé la méthode d'insertion d'un nouveau nœud dans la liste chaînée. Comment pouvons-nous accéder aux données du nœud à partir de la liste chaînée ?

Pour accéder aux données de la liste chaînée, nous devons itérer à travers la liste chaînée en utilisant le pointeur suivant, comme nous le faisons pour obtenir le dernier nœud dans la méthode d'insertion. Écrivons une méthode dans la classe Liste de liens pour imprimer toutes les données des nœuds de la liste chaînée.

4. Suivez les étapes ci-dessous pour imprimer les données de tous les nœuds de la liste chaînée.

  • Initialisez une variable avec tête.
  • Écrivez une boucle qui itère jusqu'à ce que vous atteigniez la fin de la liste chaînée.
    • Imprimez les données du nœud.
    • Déplacez le pointeur suivant

Voyons le code.

class LinkedList :

####

def display(self) :
## variable pour l'itération
temp_node = self.head

## itération jusqu'à ce que nous atteignions la fin de la liste chaînée
while temp_node != None :
## impression des données du noeud
print(temp_node.data, end='->')

## passage au noeud suivant
temp_node = temp_node.next

print('Null')

Nous avons terminé la création de la liste chaînée avec les méthodes nécessaires. Testons la liste chaînée en l'instanciant avec quelques données.

Nous pouvons créer le noeud avec le code Nœud(1 ). Voyons le code complet de l'implémentation de la liste chaînée ainsi que l'exemple d'utilisation.

class Node :

def __init__(self, data) :
## données du noeud
self.data = data

## pointeur suivant
self.next = None

class LinkedList :

def __init__(self) :
## initialisation de la tête avec None
self.head = None

def insert(self, new_node) :
## vérifier si la tête est vide ou non
if self.head :
## récupérer le dernier nœud
last_node = self.head
while last_node.next != None :
last_node = last_node.next

## assigner le nouveau nœud au pointeur suivant du dernier nœud
last_node.next = new_node

else :
## head is empty
## assigner le nœud à head
self.head = new_node

def display(self) :
## variable pour l'itération
temp_node = self.head

## itération jusqu'à la fin de la liste chaînée
while temp_node != None :
## impression des données du noeud
print(temp_node.data, end='->')

## passage au noeud suivant
temp_node = temp_node.next

print('Null')


if __name__ == '__main__' :
## instanciation de la liste chaînée
linked_list = LinkedList()

## insertion des données dans la liste chaînée
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))

## impression de la liste chaînée
linked_list.display()

Exécutez le programme ci-dessus pour obtenir le résultat suivant.

1->2->3->4->5->6->7->Null

C'est tout pour la liste chaînée. Vous savez maintenant comment implémenter une liste simple. Vous pouvez facilement implémenter la liste doublement liée avec la connaissance de la liste simple. Passons à la section suivante du tutoriel.

#2. Liste doublement liée

Une liste doublement liée contient deux pointeurs connectés au nœud précédent et au nœud suivant de la liste liée. Nous devons stocker les données et les deux pointeurs pour chaque nœud de la liste chaînée.

Le pointeur précédent du premier nœud est nul et le pointeur suivant du dernier nœud est nul pour représenter la fin de la liste chaînée des deux côtés.

Vous pouvez voir l'illustration d'une liste liée ci-dessous.

La liste doublement liée comporte également des étapes similaires à celles de la liste simple liée en termes de mise en œuvre. Encore une fois, il serait ennuyeux pour vous d'expliquer les mêmes choses. Parcourez le code de chaque étape et vous le comprendrez très rapidement. Allons-y.

Mise en œuvre de la liste doublement liée

1. Création d'un nœud pour la liste doublement liée avec le pointeur du nœud précédent, les données et le pointeur du nœud suivant.

class Node :

def __init__(self, data) :
## pointeur précédent
self.prev = None

## données du noeud
self.data = data

## pointeur suivant
self.next = None

2. Classe de liste doublement liée.

class LinkedList :

def __init__(self) :
## initialisation de la tête avec None
self.head = None

3. Méthode permettant d'insérer un nouveau nœud dans la liste doublement liée.

class LinkedList :

####

def insert(self, new_node) :
## vérifier si la tête est vide ou non
if self.head :
## récupérer le dernier noeud
last_node = self.head
while last_node.next != None :
last_node = last_node.next

## assigner le dernier noeud au pointeur précédent du nouveau noeud
new_node.prev = last_node

## assigner le nouveau noeud au pointeur suivant du dernier noeud
last_node.next = new_node

4. Une méthode pour afficher les données d'une liste doublement liée.

class LinkedList :

####

def display(self) :

## impression des données dans l'ordre normal
print("Normal Order : ", end='')

temp_node = self.head
while temp_node != None :
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()

## impression des données dans l'ordre inverse en utilisant le pointeur précédent
print("Ordre inverse : ", end='')

## obtention du dernier noeud
last_node = self.head
while last_node.next != None :
last_node = last_node.next

temp_node = last_node
while temp_node != None :
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()

Nous avons vu le code de la liste doublement liée. Et il n'y a pas de code pour l'utilisation de la classe de liste doublement liée. C'est à vous de jouer. Utilisez la classe de liste doublement liée de la même manière que la liste simple. Amusez-vous bien 🙂

Conclusion

Vous pouvez trouver de nombreux problèmes basés sur les listes chaînées. Mais vous devez connaître l'implémentation de base de la liste chaînée que vous avez apprise dans ce tutoriel. J'espère que vous avez passé un bon moment en apprenant ce nouveau concept.

Aussi, vérifiez comment utiliser la méthode index de python pour trouver l'index d'un élément dans une liste.

Bon codage 😀

  • Hafeezul Kareem Shaik
    Auteur
Merci à nos sponsors
D'autres lectures intéressantes sur le développement
Alimentez votre entreprise
Quelques outils et services pour aider votre entreprise à se développer.
  • Invicti utilise le Proof-Based Scanning™ pour vérifier automatiquement les vulnérabilités identifiées et générer des résultats exploitables en quelques heures seulement.
    Essayez Invicti
  • Web scraping, proxy résidentiel, proxy manager, web unlocker, search engine crawler, et tout ce dont vous avez besoin pour collecter des données web.
    Essayez Brightdata
  • Monday.com est un système d'exploitation tout-en-un qui vous aide à gérer vos projets, vos tâches, votre travail, vos ventes, votre CRM, vos opérations, vos flux de travail et bien plus encore.
    Essayez le lundi
  • Intruder est un scanner de vulnérabilité en ligne qui détecte les faiblesses de votre infrastructure en matière de cybersécurité, afin d'éviter des violations de données coûteuses.
    Essayer l'intrus