Implémentation de liste à chaînage unique Python
Découvrez comment implémenter une liste à chaînage unique en Python. Explorez l'allocation dynamique de mémoire, les opérations de nœuds, l'insertion, le parcours et la suppression.
Aperçu
Une liste chaînée est une structure de données linéaire dans laquelle les éléments ne sont pas stockés dans des emplacements mémoire contigus. Au lieu de cela, chaque élément (appelé nœud) est un objet distinct qui contient une référence au nœud suivant dans la séquence.
Le principal avantage d'une liste chaînée par rapport à un tableau traditionnel est son dimensionnement dynamique et la possibilité d'insérer ou de supprimer des éléments en un temps O(1) constant au début. Cependant, l'accès aux éléments par index nécessite un parcours linéaire, ce qui prend un temps O(n).
En Python, nous implémentons une liste chaînée en définissant une classe Node pour stocker les données et le pointeur de référence, et une classe LinkedList pour gérer le nœud principal, les insertions en tête ou en queue et les suppressions.
Sortie de code et d'exécution
Implémentation de liste chaînée unique en Python, présentant la création de nœuds, l'ajout et le parcours de liste.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
def delete(self, key):
curr = self.head
if curr and curr.data == key:
self.head = curr.next
curr = None
return
prev = None
while curr and curr.data != key:
prev = curr
curr = curr.next
if not curr:
return
prev.next = curr.next
curr = None
def display(self):
elements = []
curr = self.head
while curr:
elements.append(str(curr.data))
curr = curr.next
print(" -> ".join(elements) + " -> None")
# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()
print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> NoneMise en œuvre étape par étape
- Implémentation de la fonctionnalité d'annulation-rétablissement dans les éditeurs de texte
- Création de structures de données complexes telles que des graphiques, des piles et des files d'attente
- Gérer des listes où les fréquences d'insertion et de suppression dépassent le nombre d'actions de recherche
Foire aux questions
Quelle est la différence entre les listes à chaînage simple et double ?
Dans une liste à chaînage unique, chaque nœud pointe uniquement vers le nœud suivant. Dans une liste doublement chaînée, chaque nœud contient des références au nœud suivant et au nœud précédent, permettant un parcours bidirectionnel au prix de mémoire supplémentaire.
Pourquoi Python n’a-t-il pas de classe LinkedList intégrée ?
Les tableaux (listes) Python sont implémentés sous forme de tableaux dynamiques. Grâce à la gestion de la mémoire de Python et aux optimisationsCPython, les listes standard sont extrêmement rapides et efficaces pour la plupart des tâches, réduisant ainsi le besoin pratique d'une liste chaînée intégrée.
Sujets connexes
Implémentez une pile LIFO en Python. Exécutez notre exemple de code de pile interactive pour maîtriser les limites de push, pop, peek et de capacité.
Tutoriel sur la structure des données de la file d'attente PythonMaîtrisez les opérations de file d’attente FIFO en Python. Exécutez et exécutez notre exemple de file d'attente interactive présentant les méthodes de mise en file d'attente et de retrait de la file d'attente.