Dans cet article de blog, vous apprendrez à implémenter une liste chaînée en Python à partir de zéro. Nous comprendrons les caractéristiques internes des listes chaînées, la complexité de calcul de l'utilisation d'une liste chaînée et certains avantages et inconvénients de l'utilisation d'une liste chaînée sur un tableau.
Présentation
La liste chaînée est l'une des structures de données les plus fondamentales en programmation . Imaginez que vous construisez un répertoire de fichiers image et que chacun de ces fichiers est lié les uns aux autres. Comment modéliser ce problème ? Différentes structures de données sont à notre disposition pour résoudre ce problème. Vous pouvez utiliser un tableau pour stocker les fichiers dans un bloc de mémoire contigu. L'avantage d'utiliser un tableau est son temps d'accès rapide. Bien qu'un tableau nous aide à accéder aux fichiers en temps O (1), il existe certains inconvénients à utiliser un tableau si nous souhaitons insérer un nouveau fichier ou supprimer un nouveau fichier. Une liste liée nous aide à insérer et supprimer un élément en temps constant.
Une liste chaînée est représentée par une collection de nœuds et chaque nœud est lié à l'autre nœud à l'aide d'un pointeur. La figure 1 illustre le concept de liste chaînée.
Figure 1 : Liste chaînée
Comme vous pouvez le voir sur la figure 1, une liste chaînée est créée en connectant le pointeur suivant d'un nœud avec un autre nœud. Commençons maintenant en ouvrant notre éditeur et en construisant une liste à liens simples en Python.
Une liste liée comporte une collection de nœuds. Nous commençons donc par créer un Node. classe
class Node(object):
def __init__(self, value):
self.data = value
self.next = None
Le Node La classe a deux variables membres - les données et le pointeur appelé suivant qui pointe vers le nœud suivant. Chaque fois qu'un nouveau nœud est créé, le pointeur suivant sera défini sur un None valeur.
Commençons maintenant par construire la classe Linked List. La classe sera composée des fonctionnalités suivantes
- Insérer un élément au début de la liste liée
- Insérer un élément à l'arrière ou à la fin de la liste chaînée
- Suppression un élément à un index spécifié dans la liste liée
- Recherche la liste liée pour une valeur de données spécifiée
- Affichage la liste chaînée
Commençons par construire la liste chaînée et initialiser les variables membres
class LinkedList(object):
def __init__(self):
self.head = None Opérations sur une liste liée
Ensuite, vous découvrirez toutes les opérations de liste chaînée discutées et comment les implémenter en Python !
Insérer un élément au début de la liste liée
Afin d'insérer un nouveau nœud au début de la liste, nous devons d'abord vérifier si la liste est vide ou non. Nous le faisons en vérifiant la tête de la liste. Si la liste est vide, nous pouvons pointer la tête vers le nœud nouvellement créé. Si, toutefois, la liste n'est pas vide, nous pointerons la valeur suivante du nœud nouvellement créé vers l'en-tête de la liste chaînée, et nous réaffecterons le pointeur d'en-tête pour qu'il pointe vers le nœud nouvellement créé. L'extrait de code ci-dessous montre comment mettre en œuvre cette fonctionnalité.
class LinkedList(object):
def __init__(self):
self.head = None
def insert_front(self, node):
if self.head is not None:
node.next = self.head
self.head = node
else:
self.head = node Insérer un élément en fin de liste
Afin d'insérer un élément à la fin de la liste, nous devons parcourir la liste jusqu'à ce que nous atteignions la fin de la liste et dès que nous atteignons la fin de la liste, nous pointons le prochain pointeur de la queue vers le nœud nouvellement créé .
def insert_back(self, node):
if self.head is not None:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
else:
self.head = node Suppression d'un élément à un index spécifié dans la liste liée
Nous allons maintenant voir comment supprimer un élément de la liste liée en fonction d'une valeur d'index.
Il y a trois conditions nous devons vérifier si nous souhaitons supprimer un nœud d'une liste liée .
- Supprimer un nœud si la liste liée est vide : Nous allons d'abord vérifier si la liste chaînée est vide ou non. Si la liste est vide, nous imprimons un message indiquant que la liste liée est vide et retournons de la fonction.
- Suppression de l'en-tête de la liste liée : La deuxième condition survient lorsque nous souhaitons supprimer le premier nœud ou en d'autres termes la tête de la liste chaînée. Pour supprimer la tête de la liste chaînée, nous créons d'abord un nœud temporaire pour pointer vers la tête du nœud, puis réattribuons le pointeur de tête au nœud suivant de la tête d'origine. Nous supprimons ensuite le nœud temporaire.
- Suppression d'un nœud à une position arbitraire : Afin de supprimer un nœud à une position arbitraire, nous parcourons la liste chaînée et vérifions si la valeur que nous souhaitons supprimer correspond à celle du nœud actuel. Si une correspondance est trouvée, nous réaffectons le pointeur suivant du nœud précédent au nœud suivant du nœud actuel. Nous supprimons ensuite le nœud actuel.
def delete(self, value):
if self.head is None:
print('Linked List is empty')
return
if self.head.data == value:
node_to_delete = self.head
self.head = self.head.next
del node_to_delete
return
# deletion at arbitary position
current_node = self.head
while current_node is not None:
if current_node.next.data == value:
temp_node = current_node.next
current_node.next = temp_node.next
del temp_node
return
current_node = current_node.next
Recherche dans la liste liée pour une valeur spécifiée
Nous allons maintenant nous intéresser à la recherche d'une valeur donnée dans une liste chaînée. Pour ce faire, nous commençons à la tête de la liste chaînée et à chaque itération, nous vérifions la valeur du nœud. Si une correspondance est trouvée, nous imprimons l'emplacement de ce nœud en gardant une trace d'un counter variable que nous avons défini. Si aucune correspondance n'est trouvée, nous passons au nœud suivant et répétons les étapes pour rechercher une correspondance.
def search(self, value):
counter = 1
current_node = self.head
while current_node is not None:
if current_node.data == value:
print('Node with value {} found at location {}'.format(value, counter))
return
current_node = current_node.next
counter += 1
print('Node with value {} not found'.format(value))
Affichage de la liste liée
Nous allons créer une fonction appelée display pour parcourir la liste chaînée et imprimer la valeur de données du nœud. Une fois que nous avons imprimé la valeur, nous passons au nœud suivant en mettant à jour la valeur du nœud actuel.
def display(self,):
current_node = self.head
while current_node is not None:
if current_node.next is None:
print(current_node.data, end=' ', flush=True)
else:
print(current_node.data, end='-->', flush=True)
current_node = current_node.next
print('\n')
Démonstration
Voyons maintenant toutes les fonctionnalités en action. Nous commençons par créer quatre nœuds avec les valeurs suivantes
Nous créons ensuite une instance du LinkedList classe et insérez les nœuds ci-dessus à la fin de la liste liée.
node1 = Node(12) node2 = Node(13) node3 = Node(14) node4 = Node(15) ll = LinkedList() ll.insert_back(node1) ll.insert_back(node2) ll.insert_back(node3) ll.insert_back(node4) ll.display()
Nous pouvons voir la sortie comme suit
12-->13-->14-->15
Ensuite, nous allons insérer un nœud au début de la liste liée comme suit.
node5 = Node(1) ll.insert_front(node5) ll.display()
En appelant la fonction d'affichage, nous obtenons la sortie suivante
1-->12-->13-->14-->15
Nous allons maintenant examiner la fonctionnalité de recherche pour rechercher un nœud avec une valeur de données spécifique et obtenir la position de ce nœud dans la liste liée.
ll.search(12) ll.search(1) ll.search(5) ll.search(15)
Comme nous pouvons le voir dans la sortie ci-dessous, nous pouvons observer que le nœud avec la valeur 12 est à la position 2, le nœud avec la valeur 1 est à la première position, le nœud avec la valeur 5 n'est pas là dans la liste et le nœud avec la valeur 15 est situé à la position 5.
- Nœud avec la valeur 12 trouvé à l'emplacement 2
- Nœud avec la valeur 1 trouvé à l'emplacement 1
- Nœud avec la valeur 5 introuvable
- Nœud avec la valeur 15 trouvé à l'emplacement 5
Nous allons maintenant supprimer un nœud avec une valeur donnée
ll.delete(12) ll.display()
Comme nous pouvons le voir dans la sortie ci-dessous, nous avons pu supprimer le nœud avec la valeur 12 et mettre à jour son pointeur précédent, c'est-à-dire que le nœud avec la valeur 1 pointe maintenant vers le nœud avec la valeur 13.
1-->13-->14-->15
Dans une dernière étape, nous verrons ce qui se passe si nous insérons un nouveau nœud à l'emplacement spécifique. Dans l'exemple ci-dessous, nous allons essayer d'insérer un nœud avec la valeur 12 à la position 2, supprimer le nœud avec la valeur 15 et 1 et observer la sortie après chaque étape.
ll.insert(Node(12), 2) ll.display() ll.delete(15) ll.display() ll.delete(1) ll.display()
Nous obtenons la sortie suivante
1-->12-->13-->14-->15 1-->12-->13-->14 12-->13-->14
Vous pouvez voir le code entier ci-dessous
class Node(object):
def __init__(self, value):
self.data = value
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
def insert_front(self, node):
if self.head is not None:
node.next = self.head
self.head = node
else:
self.head = node
def insert_back(self, node):
if self.head is not None:
current_node = self.head
while current_node.next is not None:
current_node = current_node.next
current_node.next = node
else:
self.head = node
def insert(self, node, index):
if self.head is not None:
current_counter = 1
current_node = self.head
while current_node is not None:
if current_counter == (index - 1):
node.next = current_node.next
current_node.next = node
current_node = current_node.next
current_counter +=1
else:
print('List is empty')
self.insert_front(node)
def search(self, value):
counter = 1
current_node = self.head
while current_node is not None:
if current_node.data == value:
print('Node with value {} found at location {}'.format(value, counter))
return
current_node = current_node.next
counter += 1
print('Node with value {} not found'.format(value))
def delete(self, value):
if self.head is None:
print('Linked List is empty')
return
if self.head.data == value:
node_to_delete = self.head
self.head = self.head.next
del node_to_delete
return
# deletion at arbitary position
current_node = self.head
while current_node is not None:
if current_node.next.data == value:
temp_node = current_node.next
current_node.next = temp_node.next
del temp_node
return
current_node = current_node.next
def display(self,):
current_node = self.head
while current_node is not None:
if current_node.next is None:
print(current_node.data, end=' ', flush=True)
else:
print(current_node.data, end='-->', flush=True)
current_node = current_node.next
print('\n')
if __name__ == "__main__":
node1 = Node(12)
node2 = Node(13)
node3 = Node(14)
node4 = Node(15)
ll = LinkedList()
ll.insert_back(node1)
ll.insert_back(node2)
ll.insert_back(node3)
ll.insert_back(node4)
ll.display()
node5 = Node(1)
ll.insert_front(node5)
ll.display()
ll.search(12)
ll.search(1)
ll.search(5)
ll.search(15)
ll.delete(12)
ll.display()
ll.insert(Node(12), 2)
ll.display()
ll.delete(15)
ll.display()
ll.delete(1)
ll.display()
Conclusion
Dans ce didacticiel, nous avons vu comment implémenter une liste chaînée à partir de zéro. Nous avons ensuite vu comment effectuer certaines opérations courantes telles que l'insertion, la suppression, la recherche et le parcours dans une liste chaînée. Les listes liées ont un avantage lorsque nous souhaitons insérer ou supprimer un nœud de notre liste. Nous pouvons réaliser ces deux tâches en temps constant. Dans le prochain didacticiel, nous examinerons certains problèmes courants liés aux listes chaînées et comment les résoudre efficacement.
