Classe Node et construction de listes
Définissez une dataclass Node, construisez des listes en reliant manuellement les nœuds et écrivez des fonctions auxiliaires d’insertion, de suppression et d’affichage pour visualiser les changements de pointeurs.
Classe Node et construction de listes est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’une liste chaînée ?
Une liste chaînée est une séquence de nœuds où chaque nœud stocke une valeur et un pointeur vers le nœud suivant. Contrairement aux tableaux, les nœuds sont dispersés en mémoire : il n’existe aucun accès en O(1) par index. En contrepartie, vous obtenez une insertion et une suppression en O(1) à toute position connue, sans déplacer les éléments.
En Python, nous représentons chaque nœud par une petite classe contenant val et next. Relier les nœuds forme la liste ; le next du dernier nœud vaut None pour signaler la fin.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Construire des listes à partir de tableaux
Lors des entretiens, on vous donnera souvent une liste et on vous demandera de construire son équivalent sous forme de liste chaînée, ou inversement. Les fonctions auxiliaires build et to_list méritent d’être mémorisées : build relie les nœuds d’un tableau, et to_list parcourt la liste pour rassembler les valeurs et faciliter la vérification.
Construire une liste chaînée à partir de n éléments prend un temps O(n) et un espace O(n). Utiliser un nœud de tête factice simplifie les cas limites où le premier nœud peut changer.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Insérer en tête et en queue
Insérer un nouveau nœud en tête se fait en O(1) : créez le nœud, faites pointer son next vers l’ancienne tête et renvoyez le nouveau nœud comme tête. Insérer en tail nécessite de parcourir la liste jusqu’au dernier nœud (O(n)), puis de relier le nouveau nœud.
Utiliser un nœud de tête factice élimine le cas particulier d’une liste vide pour les deux insertions, car dummy.next est toujours la véritable tête.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneSupprimer un nœud par sa valeur
Pour supprimer le premier nœud ayant une valeur donnée, maintenez un pointeur prev situé juste avant curr. Lorsque curr.val == target, définissez prev.next = curr.next pour contourner le nœud. Une tête factice est particulièrement utile ici, car elle élimine le cas particulier de la suppression de la véritable tête : prev peut toujours commencer au niveau du nœud factice.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Visualiser les changements de pointeurs
Une erreur courante consiste à perdre la trace d’un nœud lors de la mise à jour des pointeurs. Enregistrez toujours next avant de l’écraser : saved = curr.next, puis réaffectez-le. Dessinez la liste sous forme de cases reliées par des flèches et simulez chaque mise à jour de pointeur sur papier avant de coder. Cette approche visuelle évite les erreurs accidentelles de pointeur nul pendant les entretiens.
Souvenez-vous qu’en Python, réaffecter curr.next ne modifie pas curr lui-même, mais perdre la référence à curr.next avant de l’avoir enregistrée signifie que vous ne pouvez plus parcourir la liste vers l’avant.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Listes chaînées simples ou doubles
Une liste chaînée simple ne stocke qu’un pointeur next ; le parcours est unidirectionnel. Une liste doublement chaînée stocke à la fois prev et next, ce qui permet un parcours en arrière en O(1) et une suppression en O(1) lorsqu’on dispose d’une référence directe vers le nœud (la boucle de suivi du nœud précédent n’est pas nécessaire).
La structure collections.deque de Python est implémentée sous forme de liste doublement chaînée, ce qui explique qu’elle prenne en charge appendleft et popleft en O(1). Lors des entretiens, vous implémenterez des listes chaînées simples ; les listes doublement chaînées apparaissent dans la conception des caches LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Longueur, queue et fonctions d’affichage
Voici trois fonctions utilitaires que vous devriez avoir sous la main lors de tout entretien sur les listes chaînées : length(head) compte les nœuds en O(n), tail(head) renvoie le dernier nœud en O(n), et print_list(head) met la liste en forme pour le débogage. Les avoir prêtes vous permet de vous concentrer sur l’algorithme principal plutôt que de réécrire la logique auxiliaire.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Initialiser deux pointeurs sur les listes chaînées
La technique des deux pointeurs est aussi importante pour les listes chaînées que pour les tableaux, mais les pointeurs sont des nœuds de la liste plutôt que des index. Parmi les configurations courantes figurent un pointeur lent et un pointeur rapide (le pointeur rapide avance deux fois plus vite) pour trouver les milieux et détecter les cycles, ainsi qu’une paire prédécesseur et courant pour les suppressions et les inversions.
Initialisez toujours les deux pointeurs explicitement et vérifiez soigneusement la terminaison par valeur nulle : fast and fast.next évite les erreurs de pointeur nul lorsque le pointeur rapide approche de la fin.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Le modèle de la tête factice
Le modèle de la tête factice (nœud sentinelle) est l’une des astuces les plus utiles pour les problèmes de listes chaînées. En ajoutant en tête un nœud factice de valeur 0, vous n’avez jamais besoin de traiter séparément une liste vide ou un changement de la véritable tête. Votre résultat est toujours dummy.next. Ce modèle apparaît dans la fusion de listes triées, la suppression du n-ième nœud depuis la fin, le partitionnement d’une liste et bien d’autres problèmes.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Complexité temporelle et spatiale
La plupart des opérations sur les listes chaînées ont les complexités suivantes. Accès par index : O(n) — il faut parcourir la liste depuis la tête. Insertion ou suppression au niveau d’un nœud connu : O(1) — il suffit de réorganiser les pointeurs. Insertion ou suppression à la position k : O(k) — il faut d’abord parcourir la liste. Recherche : O(n) — dans le pire des cas, toute la liste. L’espace est de O(1) pour toutes les opérations effectuées sur place (sans compter les structures de données supplémentaires).
Comparez avec les tableaux : ils offrent un accès en O(1), mais l’insertion et la suppression prennent O(n) à cause des décalages. Les listes chaînées sont préférables lorsque les insertions et les suppressions à des positions arbitraires sont fréquentes.
Conseils d’entretien sur les listes chaînées
Avant d’écrire du code sur une liste chaînée, dessinez-la avec des cases et des flèches. Énoncez les cas limites à vérifier : liste vide, nœud unique, longueur paire ou impaire. Utilisez une tête factice pour simplifier les conditions aux limites. Vérifiez toujours rapidement if not head. Après avoir codé, simulez votre solution sur une liste de trois nœuds afin de détecter les erreurs de pointeurs avant que l’examinateur ne le fasse.
La plupart des erreurs dans les listes chaînées proviennent de l’une de trois sources : oublier d’enregistrer next avant de l’écraser, faire une erreur de décalage d’une unité dans la condition d’arrêt, ou ne pas gérer le cas limite où la tête change — le nœud factice élimine entièrement le troisième problème.
Vérification rapide
Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : les listes chaînées sont construites à partir d’objets nœud possédant des champs de valeur et de lien suivant, le modèle de la tête factice élimine les cas limites liés au changement de tête, et la configuration à deux pointeurs lent et rapide constitue la base de la recherche du milieu et de la détection des cycles. Nous allons maintenant aborder l’inversion d’une liste chaînée, l’un des problèmes de pointeurs les plus fréquemment posés.
Questions Fréquemment Posées
La leçon « Classe Node et construction de listes » est-elle gratuite ?
Oui — le texte complet de « Classe Node et construction de listes » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Classe Node et construction de listes » ?
Définissez une dataclass Node, construisez des listes en reliant manuellement les nœuds et écrivez des fonctions auxiliaires d’insertion, de suppression et d’affichage pour visualiser les changements… Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Classe Node et construction de listes » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Classe Node et construction de listes
- Inverser une liste chaînée
- Détection de cycles avec l’algorithme de Floyd
- Fusionner, scinder et trouver le n-ième élément depuis la fin