Listes liées en Python - Plato AiStream V2.1

Republié par Platon

Suiveurs: 0

Introduction

Une liste chaînée est une structure de données constituée d'une séquence de nœuds, chacun contenant une valeur et une référence au nœud suivant dans la séquence. Contrairement aux tableaux, les listes liées ne nécessitent pas d'allocation de mémoire contiguë, ce qui les rend plus flexibles et efficaces pour certaines opérations. Dans cet article, nous explorerons les avantages et les inconvénients des listes liées et comment les implémenter en Python.

Table des matières

Avantages et inconvénients des listes liées

Les listes liées offrent plusieurs avantages par rapport aux autres structures de données. Premièrement, ils permettent une insertion et une suppression efficaces d’éléments, car ils nécessitent uniquement la mise à jour des références des nœuds voisins. Cela rend les LinkedLists idéales pour les scénarios où des modifications fréquentes sont attendues. De plus, les LinkedLists peuvent augmenter ou diminuer dynamiquement leur taille, contrairement aux tableaux, qui ont une taille fixe.

Cependant, les listes chaînées présentent également certains inconvénients. Contrairement aux tableaux, les listes chaînées ne prennent pas en charge l'accès aléatoire aux éléments, ce qui signifie que l'accès à un élément à un index spécifique nécessite de parcourir la liste depuis le début. Cela peut entraîner un ralentissement des performances de certaines opérations. De plus, les listes liées nécessitent de la mémoire supplémentaire pour stocker les références aux nœuds suivants, ce qui peut s'avérer inefficace pour les petits ensembles de données.

Implémentation de listes liées en Python

Python fournit un moyen flexible et intuitif d'implémenter des listes liées. Il existe trois principaux types de listes chaînées : la liste chaînée simple, la liste chaînée double et la liste chaînée circulaire. Explorons chacun d'eux en détail.

Liste liée individuellement

Une liste à chaînage unique se compose de nœuds où chaque nœud contient une valeur et une référence au nœud suivant dans la séquence. Voici comment créer une liste à chaînage unique en Python :

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

class Linked List:
    def __init__(self):
        self.head = None

Création d'une liste à lien unique

Pour créer une liste à chaînage unique, nous devons définir une classe Node qui représente chaque nœud de la liste. Chaque nœud contient une valeur et une référence au nœud suivant. La classe Linked List sert de conteneur pour les nœuds, l'attribut head pointant vers le premier nœud de la liste.

Insertion de nœuds dans une liste à lien unique

L'insertion de nœuds dans une liste à chaînage unique implique la mise à jour des références des nœuds voisins. Voici un exemple d'insertion d'un nœud en début de liste :

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Suppression de nœuds d'une liste à lien unique

La suppression de nœuds d'une liste à chaînage unique nécessite la mise à jour des références des nœuds voisins. Voici un exemple de suppression d'un nœud avec une valeur spécifique :

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Recherche dans une liste à lien unique

La recherche d'une valeur spécifique dans une liste à lien unique implique de parcourir la liste jusqu'à ce que la valeur soit trouvée ou que la fin de la liste soit atteinte. Voici un exemple de recherche d'une valeur :

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Inverser une liste à lien unique

L'inversion d'une liste à chaînage unique nécessite la mise à jour des références de chaque nœud pour pointer vers le nœud précédent. Voici un exemple d'inversion d'une liste à lien unique :

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Liste doublement liée

Une liste doublement chaînée est similaire à une liste à chaînage unique, mais chaque nœud contient une référence à la fois au nœud suivant et au nœud précédent dans la séquence. Cela permet une traversée efficace dans les deux sens. Voici comment créer une liste doublement chaînée en Python :

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

Créer une liste doublement liée

Pour créer une liste doublement chaînée, nous définissons une classe Node qui contient une valeur, une référence au nœud suivant et une référence au nœud précédent. La classe DoublyLinked List sert de conteneur pour les nœuds, l'attribut head pointant vers le premier nœud de la liste.

Insertion de nœuds dans une liste doublement liée

L'insertion de nœuds dans une liste doublement chaînée implique la mise à jour des références des nœuds voisins. Voici un exemple d'insertion d'un nœud en début de liste :

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Suppression de nœuds d'une liste doublement liée

La suppression de nœuds d'une liste doublement chaînée nécessite la mise à jour des références des nœuds voisins. Voici un exemple de suppression d'un nœud avec une valeur spécifique :

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Recherche dans une liste doublement chaînée

La recherche d'une valeur spécifique dans une liste doublement chaînée implique de parcourir la liste dans les deux sens jusqu'à ce que la valeur soit trouvée ou que la fin de la liste soit atteinte. Voici un exemple de recherche d'une valeur :

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Inverser une liste doublement liée

Inverser une liste doublement chaînée nécessite de mettre à jour les références de chaque nœud pour échanger les pointeurs suivant et précédent. Voici un exemple d'inversion d'une liste doublement chaînée :

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Liste circulaire liée

Une liste chaînée circulaire est une variante d'une liste chaînée unique où le dernier nœud pointe vers le premier nœud, créant ainsi une structure circulaire. Cela permet un parcours efficace à partir de n’importe quel nœud de la liste. Voici comment créer une liste chaînée circulaire en Python :

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

class CircularLinked List:
    def __init__(self):
        self.head = None

Création d'une liste chaînée circulaire

Pour créer une liste chaînée circulaire, nous définissons une classe Node qui contient une valeur et une référence au nœud suivant. La classe CircularLinked List sert de conteneur pour les nœuds, l'attribut head pointant vers le premier nœud de la liste. De plus, la référence suivante du dernier nœud est définie sur la tête, créant ainsi une structure circulaire.

Insertion de nœuds dans une liste chaînée circulaire

L'insertion de nœuds dans une liste chaînée circulaire implique la mise à jour des références des nœuds voisins. Voici un exemple d'insertion d'un nœud en début de liste :

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Suppression de nœuds d'une liste circulaire liée

La suppression de nœuds d’une liste chaînée circulaire nécessite la mise à jour des références des nœuds voisins. Voici un exemple de suppression d'un nœud avec une valeur spécifique :

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Recherche dans une liste chaînée circulaire

La recherche d'une valeur spécifique dans une liste chaînée circulaire implique de parcourir la liste jusqu'à ce que la valeur soit trouvée ou que la liste entière soit parcourue. Voici un exemple de recherche d'une valeur :

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Inverser une liste chaînée circulaire

L'inversion d'une liste chaînée circulaire nécessite la mise à jour des références de chaque nœud pour inverser la structure circulaire. Voici un exemple d'inversion d'une liste chaînée circulaire :

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Opérations courantes sur les listes liées

Les listes liées prennent en charge diverses opérations courantes qui peuvent être effectuées sur les éléments. Explorons certaines de ces opérations :

Accéder aux éléments d'une liste chaînée

Pour accéder aux éléments d'une liste chaînée, nous pouvons parcourir la liste en commençant par le nœud principal et passer au nœud suivant jusqu'à atteindre la position souhaitée. Voici un exemple d'accès à un élément à un index spécifique :

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Modification d'éléments dans une liste liée

La modification d'éléments dans une liste chaînée implique de parcourir la liste pour trouver l'élément souhaité et de mettre à jour sa valeur. Voici un exemple de modification d'un élément à un index spécifique :

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Trouver la longueur d'une liste chaînée

Pour trouver la longueur d'une liste chaînée, nous pouvons parcourir la liste et compter le nombre de nœuds. Voici un exemple de recherche de la longueur d'une liste chaînée :

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Vérifier si une liste chaînée est vide

Pour vérifier si une liste chaînée est vide, nous pouvons simplement vérifier si le nœud principal est Aucun. Voici un exemple de vérification si une liste chaînée est vide :

def is_empty(self):
    return self.head is None

Concaténation de listes liées

Pour concaténer deux listes chaînées, nous pouvons parcourir la première liste pour trouver le dernier nœud et mettre à jour sa prochaine référence vers la tête de la deuxième liste. Voici un exemple de concaténation de deux listes liées :

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Liste chaînée vs tableau

Les listes liées et les tableaux sont tous deux des structures de données couramment utilisées, mais ils présentent des caractéristiques différentes qui les rendent adaptés à différents scénarios. Comparons les listes liées et les tableaux en termes d'efficacité de la mémoire, d'efficacité d'insertion et de suppression et d'efficacité d'accès aléatoire.

Efficacité de la mémoire

Les listes liées sont plus efficaces en termes de mémoire que les tableaux car elles ne nécessitent pas d'allocation de mémoire contiguë. Chaque nœud d'une liste chaînée doit uniquement stocker la valeur et une référence au nœud suivant, tandis que les tableaux doivent allouer de la mémoire à tous les éléments, même s'ils ne sont pas utilisés.

Efficacité d'insertion et de suppression

Les listes liées excellent dans les opérations d'insertion et de suppression, en particulier lorsque des éléments sont fréquemment ajoutés ou supprimés du milieu de la liste. L'insertion ou la suppression d'un élément dans une liste chaînée nécessite uniquement la mise à jour des références des nœuds voisins, tandis que les tableaux peuvent nécessiter le déplacement d'éléments pour s'adapter au changement.

Efficacité de l'accès aléatoire

Les tableaux fournissent un accès aléatoire efficace aux éléments en fonction de leurs indices, car ils permettent un adressage direct de la mémoire. En revanche, les listes liées nécessitent de parcourir la liste depuis le début pour accéder à un élément à un index spécifique, ce qui entraîne un ralentissement des performances pour les opérations d'accès aléatoire.

Choisir la bonne structure de données

Le choix entre les listes liées et les tableaux dépend des exigences spécifiques de l'application. Si des modifications fréquentes et un redimensionnement dynamique sont attendus, les listes liées sont un meilleur choix. En revanche, si l’accès aléatoire et l’efficacité de la mémoire sont cruciaux, les tableaux sont plus adaptés.

Applications de liste chaînée

Maintenant que nous comprenons bien les listes chaînées et leur fonctionnement, explorons quelques-unes des applications pratiques dans lesquelles les listes chaînées peuvent être utilisées efficacement.

Vous pouvez également vous inscrire à notre Cours gratuits Aujourd'hui!

Implémentation de piles et de files d'attente

L'une des applications les plus courantes des listes chaînées consiste à implémenter des piles et des files d'attente. Les piles et les files d'attente sont des types de données abstraits qui peuvent être facilement implémentés à l'aide de listes chaînées.

Une pile est une structure de données qui suit le principe Last-In-First-Out (LIFO). Les éléments sont ajoutés et supprimés à partir de la même extrémité, appelée sommet de la pile. Les listes chaînées offrent un moyen efficace d’implémenter des piles car nous pouvons facilement ajouter ou supprimer des éléments en tête de liste.

Voici un exemple d'implémentation d'une pile à l'aide d'une liste chaînée en Python :

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

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

Une file d'attente, quant à elle, suit le principe du premier entré, premier sorti (FIFO). Les éléments sont ajoutés à une extrémité, appelée arrière, et retirés de l'autre extrémité, appelée avant. Les listes chaînées peuvent également être utilisées pour implémenter efficacement des files d’attente.

Voici un exemple d'implémentation d'une file d'attente à l'aide d'une liste chaînée en Python :

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Gestion de grands ensembles de données

Les listes chaînées sont également utiles lorsqu’il s’agit de grands ensembles de données. Contrairement aux tableaux, les listes chaînées ne nécessitent pas d’allocation de mémoire contiguë. Cela signifie que les listes chaînées peuvent gérer efficacement des ensembles de données de différentes tailles sans avoir besoin de redimensionnement ou de réaffectation.

Par exemple, disons que nous avons un ensemble de données de millions d'enregistrements et que nous devons effectuer des opérations telles que l'insertion, la suppression ou le parcours. L'utilisation d'un tableau pour cette tâche peut s'avérer inefficace car elle nécessite le déplacement d'éléments lors de l'insertion ou de la suppression. Cependant, avec une liste chaînée, nous pouvons facilement insérer ou supprimer des éléments en mettant à jour les pointeurs, ce qui accélère les opérations.

Algorithmes de traversée de graphiques

Les algorithmes de traversée de graphiques, tels que la recherche en largeur d'abord (BFS) et la recherche en profondeur d'abord (DFS), peuvent également être implémentés à l'aide de listes chaînées. Dans le parcours de graphe, nous visitons chaque sommet ou nœud d'un graphe dans un ordre spécifique.

Les listes chaînées peuvent être utilisées pour représenter la liste de contiguïté d'un graphique, où chaque nœud de la liste chaînée représente un sommet et ses sommets adjacents sont stockés en tant que nœuds de liste chaînée. Cette représentation permet un parcours et une exploration efficaces du graphique.

Représentation polynomiale

Les listes chaînées peuvent être utilisées pour représenter efficacement les polynômes. En mathématiques, les polynômes sont des expressions constituées de variables et de coefficients. Chaque terme d'un polynôme peut être représenté comme un nœud dans une liste chaînée, où le coefficient et l'exposant sont stockés sous forme de données.

En utilisant des listes chaînées, nous pouvons facilement effectuer des opérations sur des polynômes, telles que l'addition, la soustraction et la multiplication. Les nœuds peuvent être manipulés pour effectuer ces opérations, ce qui donne une représentation concise et efficace des polynômes.

Listes de lecture de musique et de vidéo

Les listes chaînées sont couramment utilisées pour implémenter des listes de lecture dans les lecteurs de musique et vidéo. Chaque chanson ou vidéo peut être représentée sous forme de nœud dans une liste chaînée, où les données contiennent des informations sur le fichier multimédia et le pointeur pointe vers la chanson ou la vidéo suivante dans la liste de lecture.

L'utilisation de listes chaînées pour les listes de lecture permet une navigation facile entre les chansons ou les vidéos. Nous pouvons facilement ajouter ou supprimer des chansons de la liste de lecture en mettant à jour les pointeurs, offrant ainsi une expérience utilisateur transparente.

Conclusion

En conclusion, les listes chaînées sont des structures de données polyvalentes qui trouvent des applications dans divers domaines. Ils peuvent être utilisés pour implémenter des piles et des files d'attente, gérer de grands ensembles de données, effectuer un parcours graphique, représenter des polynômes et créer des listes de lecture. Les listes chaînées fournissent des solutions efficaces à ces problèmes en tirant parti de leur allocation dynamique de mémoire et de la manipulation aisée des nœuds.

En comprenant les applications des listes chaînées, nous pouvons prendre des décisions éclairées lors du choix des structures de données pour nos programmes. Qu'il s'agisse de gérer des données, de mettre en œuvre des algorithmes ou de créer des interfaces conviviales, les listes chaînées constituent un outil précieux dans la boîte à outils du programmeur.

Ainsi, la prochaine fois que vous rencontrerez un problème nécessitant une insertion, une suppression ou un parcours efficace, envisagez d'utiliser des listes chaînées pour simplifier votre solution et optimiser votre code.

Vous pouvez également lire plus d'articles liés aux listes Python ici :

Foire aux Questions

Q1 : Qu'est-ce qu'une liste chaînée ?

R : Une liste chaînée est une structure de données composée de nœuds, où chaque nœud contient une valeur et une référence (ou un lien) vers le nœud suivant dans la séquence.

Q2 : Quels sont les avantages de l’utilisation des listes liées ?

R : Les listes liées offrent des opérations d'insertion et de suppression efficaces, un redimensionnement dynamique et ne nécessitent pas d'allocation de mémoire contiguë.

Q3 : Quels sont les inconvénients des listes liées ?

R : Les listes liées n'ont pas d'accès aléatoire, ce qui nécessite une traversée pour accéder aux éléments. Ils consomment également de la mémoire supplémentaire pour stocker les références, ce qui peut s'avérer inefficace pour les petits ensembles de données.

Q4 : Quels sont les principaux types de listes liées en Python ?

R : Les principaux types de listes chaînées sont les listes à chaînage unique, les listes à chaînage double et les listes à chaînage circulaire.

Q5 : Dans quels scénarios les listes liées sont-elles plus économes en mémoire que les tableaux ?

R : Les listes liées sont plus efficaces en termes de mémoire que les tableaux lorsqu'il s'agit de redimensionnement dynamique et d'insertions ou de suppressions fréquentes, car elles ne nécessitent pas d'allocation de mémoire contiguë.