1-04. Structures de données linéaires

• Spécifier une structure de données par son interface.
• Distinguer interface et implémentation.

L’implémentation d’un type de données, c’est la manière dont ces données sont gérées et stockées en mémoire.
Par exemple, une liste peut être implémentée sous forme de liste chaînée ou de tableau. Dans Python, les listes sont implémentées sous forme de tableau dynamique.
Dans le premier langage qui a implémenté les listes (LISP, 1958), il s’agissait de listes chainées.
J’en dirai plus sur ces deux concepts (tableaux et listes chaînées) dans le prochain paragraphe.

L’interface d’un type de données, c’est l’ensemble des opérations qu’on peut réaliser dans un langage de programmation donné sur ce type de données.
En gardant toujours les listes comme exemple, dans Python, on dispose d’un ensemble de méthodes (pop, append, extend, remove…) associées aux listes.
Dans LISP, par contre, l’interface était plus réduite : on pouvait obtenir le premier élément de la liste (car), obtenir toute la liste sauf le premier élément (cdr) et construire une nouvelle liste à partir d’un élément et d’une autre liste – éventuellement vide (cons).

La même interface peut avoir différentes implémentations, et l’utilisateur n’a généralement pas besoin de connaître l’implémentation sous-jacente pour utiliser l’interface.

• Choisir une structure de données adaptée à la situation à modéliser
• Écrire plusieurs implémentations d’une même structure de données

Une liste est une suite d’éléments rangés dans un certain ordre. Par exemple, la séquence des nombres {14, 2, -5, 20} est une liste. Mais il existe plusieurs façons d’implémenter une liste en programmation.

Listes ou tableaux ?

Les listes et les tableaux sont des types abstraits de données linéaires qui permettent de stocker des éléments de façon ordonnée, mais qui diffèrent par leur mode d’accès et leurs opérations caractéristiques : accès direct pour les tableaux, séquentiel pour les listes.

Comparaison des opérations

* Une fois la position connue, sinon O(n) pour trouver la position

Implémentations des « vraies » listes

Même si on exclut les tableaux, il reste plusieurs manières possibles d’implémenter des listes (c’est-à-dire une suite de valeurs ordonnées réparties de manière non contigüe en mémoire).

Et d’autres variantes existent : liste circulaire, liste avec sentinelle…

Les listes Python ne sont pas des listes !

Bien que Python appelle cette structure « list », les listes Python ne sont pas des listes chaînées mais des tableaux dynamiques. Cette implémentation redimensionne automatiquement l’espace mémoire quand nécessaire.

Lorsqu’une liste Python atteint sa capacité maximale et qu’un nouvel élément est ajouté, Python alloue un nouveau tableau un peu plus grand en mémoire. Il copie ensuite tous les éléments existants dans le nouveau tableau, ajoute le nouvel élément et libère l’ancien espace mémoire.

Ce compromis entre mémoire et vitesse permet un bon équilibre pour la plupart des usages courants.

Mais pourquoi tant de listes ?

Quand on dispose de ressources de calculs ou de mémoire très restreintes, on doit optimiser son usage. Et donc il faut une implémentation adaptée.

En informatique embarquée ou en domotique (par exemple avec les arduinos), on peut se trouver dans ce cas de figure.

Dans ces environnements, le choix d'implémentation n'est pas une question d'élégance théorique mais de survie de la mission :

• Les listes chaînées peuvent être préférables quand la mémoire est très fragmentée
• Les tableaux sont privilégiés quand l'accès rapide aux données est critique
• Des structures hybrides peuvent être développées spécifiquement pour ces contraintes

Ces considérations, quoique moins critiques dans la programmation quotidienne, restent pertinentes aujourd'hui dans l'IoT, les systèmes embarqués et les applications temps réel.

			class Node:
				"""Représente un nœud dans une liste chaînée."""
				def __init__(self, data=None):
					self.data = data   # Donnée stockée
					self.next = None   # Nœud suivant (class Node ou None)
				
				def __str__(self):
					return str(self.data)

			class ChainList:
				"""Implémentation d'une liste chaînée en Python."""
				def __init__(self):
					self.head = None  # Premier élément = None à l’instantiation
					self.size = 0     # Nombre d'éléments dans la liste
				
				def is_empty(self):
					"""Vérifie si la liste est vide."""
					return self.head is None
				
				def _navigate_to(self, index):
					"""méthode "privée" renvoyant l’élément se trouvant à l’index spécifié"""
					if index < 0 or index > self.size-1:
						raise IndexError("Index hors limites")
					
					current = self.head # on part du 1er nœud
					for _ in range (index):
						current = current.next # on navigue jusqu’au nœud cible
					return current
				
				def append(self, data):
					"""Ajoute un élément à la fin de la liste."""
					new_node = Node(data)
					if self.is_empty():
						self.head = new_node
					else:
						last_node = self._navigate_to(self.size-1)
						last_node.next = new_node
					self.size += 1
				
				def prepend(self, data):
					"""Ajoute un élément au début de la liste."""
					new_node = Node(data)
					new_node.next = self.head
					self.head = new_node
					self.size += 1
				
				def insert_at(self, index, data):
					"""Insère un élément à une position donnée."""
					if index == 0:
						self.prepend(data)
					else:
						new_node = Node(data)
						node_before_insertion = self._navigate_to(index-1)
						new_node.next = node_before_insertion.next
						node_before_insertion.next = new_node
					self.size += 1
				
				def remove_at(self, index):
					"""Supprime l'élément à la position donnée."""
					# À compléter ... ☺️
				
				def get_at(self, index):
					target_node = self._navigate_to(index)
					return target_node.data
				
				def __len__(self):
					"""Retourne la taille de la liste."""
					return self.size
				
				def __str__(self):
					"""Retourne une représentation en string de la liste."""
					if self.is_empty():
						return "[]"
					result = []
					current = self.head
					while current:
						result.append(str(current.data))
						current = current.next
					return "[" + ", ".join(result) + "]"
		

				def remove_at(self, index):
						"""Supprime l'élément à la position donnée."""
						if index < 0 or index > self.size-1 or self.size == 0:
							raise IndexError("Index hors limites")
						if index == 0:
							self.head = self.head.next
						else:
							node_before_deletion = self._navigate_to(index-1)
							node_before_deletion.next = node_before_deletion.next.next
						self.size -= 1
			

• Distinguer des structures par le jeu des méthodes qui les caractérisent.

Pensez à une file à un guichet. C’est le premier de la file qui est reçu. Si une nouvelle personne arrive, elle doit (théoriquement) se placer à la fin de la file, et toutes les personnes devant seront servies par ordre d’arrivée.

Souvenez-vous, on s’est servi des files lorsqu’on a étudié le parcours en largeur d’un graphe.

En python, on ne va pas réinventer la roue. On va simplement utiliser la classe native list et se limiter aux méthodes pop(0) et append. Et bien sûr, on a toujours accès à la fonction len pour savoir combien d’éléments elle contient.

		file = [5, -2, 14, 20]
		first = file.pop(0)
		print(first) # 5
		print(file) # [-2, 14, 20]
		file.append(33)
		print(file) # [-2, 14, 20, 33]
	

Bien sûr, on pourrait créer une classe File dont les méthodes soient limitées aux méthodes autorisées, mais ça serait assez inutile.

Une pile, c’est également une liste, mais dont l’usage est légèrement différent. Il suit le principe de LIFO – Last In First Out.

On se limite donc aux méthodes append et pop (qui, par défaut, retire et renvoie le dernier élément d’une liste)

Pensez à quand vous remettez votre copie sur mon bureau. Vous la placez sur le dessus de la pile. Et vos copies seront corrigées dans l’ordre LIFO : je corrigerai en premier la dernière copie qui a été déposée. 😏

Là encore, on va utiliser les list de python.

		pile = [5, 2, -4, 13, 18]
		last = pile.pop()
		print(last) # 18
		print(pile) # [5, 2, -4, 13]
		pile.append(33)
		print(pile) # [5, 2, -4, 13, 33]
	

				def est_equilibre(expression):
					"""Vérifie si les parenthèses, crochets et accolades sont équilibrés"""
					pile = []
					correspondances = {')': '(', ']': '[', '}': '{'}
					
					for caractere in expression:
						if caractere in '([{':
							pile.append(caractere)
						elif caractere in ')]}':
							if not pile or pile.pop() != correspondances[caractere]:
								return False
					
					return len(pile) == 0