Aller au contenu principal

Tableaux et listes

Les tableaux et listes sont des structures de données fondamentales en informatique. Elles permettent de stocker et manipuler des objets en introduisant un ordre entre les éléments. Conceptuellement, les deux sont des séquences d'éléments, mais les tableaux et les listes diffèrent par leur implémentation et leur performance.

Dans cette section, nous allons voir quatre structures de données :

  • Tableau statique (Array)
  • Tableau dynamique (ArrayList)
  • Liste simplement chaînée (Singly Linked List)
  • Liste doublement chaînée (Doubly Linked List)

Tableau statique (Array)

Définition

Un tableau statique est une séquence contiguë de taille fixe.

  • Taille définie à la création → pas de redimensionnement
  • Accès par indice en temps constant O(1)
  • Insertion/suppression au milieu nécessite la création d'un nouveau tableau ou le décalage des éléments O(n)
  • Utilisé pour des données de taille connue à l'avance

Implémentation

En python, il n'existe pas de tableau statique natif, mais on peut le simuler avec une classe qui limite la modification de la taille. Voici une implémentation simplifiée d'un tableau statique :

from dataclasses import dataclass, field

@dataclass
class Array:
capacity: int
data: list = field(init=False)

def __post_init__(self):
self.data = [None] * self.capacity # None indique case vide

def get(self, index: int):
if 0 <= index < self.capacity:
return self.data[index]
raise IndexError("Index hors bornes")

def set(self, index: int, value):
if 0 <= index < self.capacity:
self.data[index] = value
else:
raise IndexError("Index hors bornes")

Ceci n'est pas très intéressant en Python, aussi bien utiliser directement le type list qui est un tableau dynamique. Cependant, dans d'autres languages comme C ou Java, les tableaux statiques sont natifs et peuvent être créés directement avec une taille fixe. En C, par exemple :

int tableau[10]; // Tableau de 10 entiers

ou en Java :

int[] tableau = new int[10]; // Tableau de 10 entiers

Dans ces langages, les tableaux statiques sont homogènes (tous les éléments du même type) et la taille est fixe à la création. Cela permet une allocation mémoire contiguë et un accès rapide aux éléments par indice. De plus, l'aspect homogène permet une gestion efficace de la mémoire et des performances optimales pour les opérations d'accès et de modification.

Complexités

OpérationAccès aléatoireInsertion têteInsertion finInsertion milieuSuppression têteSuppression finSuppression milieuMémoire
Tableau statiqueO(1)O(n)O(n)O(n)O(n)O(n)O(n)Faible

Quand l’utiliser ?

  • Taille connue et fixe
  • Besoin d’accès aléatoire rapide
  • Pas ou très peu d’insertion/suppression en cours de vie

Tableau dynamique (ArrayList)

Définition

Un tableau dynamique est un tableau redimensionnable automatiquement. Il porte souvent le nom de ArrayList, Vector ou List dépendant du langage. En Python, c'est le type list, en C# c'est List<T>, en Java c'est ArrayList et en C++ c'est std::vector.

La principale différence avec un tableau statique est que sa taille peut augmenter ou diminuer dynamiquement. Lorsque le tableau est plein, il est redimensionné pour doubler sa capacité, ce qui permet d'ajouter de nouveaux éléments sans avoir à créer manuellement un nouveau tableau à chaque fois.

Cela permet d'avoir un tableau qui peut croître ou rétrécir selon les besoins, tout en conservant un accès rapide aux éléments par indice. L'ajout d'un élément à la fin du tableau est généralement une opération amortie en O(1), car la redimension est rare.

Complexités

OpérationAccès aléatoireInsertion têteInsertion finInsertion milieuSuppression têteSuppression finSuppression milieuMémoire
Tableau dynamiqueO(1)O(n)O(1)*O(n)O(n)O(1)*O(n)Moyen (+ redim.)

*Insertion fin et suppression fin sont O(1) en moyenne (amorti), mais peuvent être O(n) lors d'un redimensionnement.

Quand l’utiliser ?

  • Taille variable, non connue à l’avance
  • Besoin fréquent d’ajouter à la fin
  • Accès indexé rapide nécessaire

Visualiser le redimensionnement

Le code Python suivant permet de visualiser la croissance de la capacité d'une liste dynamique en fonction du nombre d'éléments ajoutés. Il utilise sys.getsizeof() pour mesurer la taille mémoire allouée et matplotlib pour afficher un graphique de la croissance de la capacité.

import sys
import matplotlib.pyplot as plt

def plot_list_capacity(max_n: int = 2000):
"""
Mesure et affiche la croissance de la capacité mémoire d'une liste Python
jusqu'à max_n éléments.
"""
lengths = [] # nombre d'éléments dans la liste
sizes = [] # taille allouée par sys.getsizeof()
lst = []

for i in range(max_n):
lst.append(i)
lengths.append(i + 1)
sizes.append(sys.getsizeof(lst))

# Création du graphique
plt.figure(figsize=(10, 6))
plt.plot(lengths, sizes, drawstyle='steps-post')
plt.xlabel("Nombre d'éléments dans la liste")
plt.ylabel("Taille allouée (octets)")
plt.title("Croissance amortie de la capacité d'une liste Python")
plt.grid(True, linestyle='--', alpha=0.5)
plt.tight_layout()
plt.show()

if __name__ == "__main__":
plot_list_capacity(max_n=2000)

Le code ci-haut devrait donner un graphique montrant comment la taille mémoire comme celui-ci Graphique de la croissance de la capacité d&#39;une liste Python.

Liste simplement chaînée (Singly Linked List)

Définition

Une liste simplement chaînée (Singly Linked List) est une suite de nœuds reliés par un pointeur next. Cela permet de stocker des éléments de manière dynamique, sans taille fixe. L'insertion et la suppression sont rapides en tête de liste. Par contre, l'accès par position est lent car il faut parcourir la liste depuis le début.

Implémentation

Voici une implémentation simple d'une liste simplement chaînée en Python :

from dataclasses import dataclass
from typing import Optional

@dataclass
class Node:
value: any
next: Optional['Node'] = None

@dataclass
class SinglyLinkedList:
head: Optional[Node] = None

def insert_front(self, value) -> None:
self.head = Node(value, self.head)

def get(self, index: int) -> Optional[Node]:
curr = self.head
# La présence de cette boucle indique que l'accès par index est O(n)
for _ in range(index):
if curr is None:
raise IndexError("Index hors bornes")
curr = curr.next
return curr

def set(self, index: int, value) -> None:
node = self.get(index)
if node is not None:
node.value = value
else:
raise IndexError("Index hors bornes")

Complexités

OpérationAccès aléatoireInsertion têteInsertion finInsertion milieuSuppression têteSuppression finSuppression milieuMémoire
Liste simplement chaînéeO(n)O(1)O(n)*O(n)O(1)O(n)*O(n)Pointeur simple

*Insertion/suppression en fin est O(1) si on possède déjà le dernier nœud (par exemple si on maintient un pointeur tail), sinon O(n) car il faut parcourir la liste.

Quand l’utiliser ?

  • Lorsque les noeuds sont très coûteux à recopier en mémoire
  • Beaucoup d’insertion/suppression en tête
  • Pas de besoin d’accès aléatoire

Liste doublement chaînée (Doubly Linked List)

Définition

Une liste doublement chaînée possède, pour chaque nœud, un pointeur next et un pointeur prev. Elle possède les caractéristiques suivantes :

  • Insertion/suppression en O(1) en tête de liste.
  • Insertion/suppression en O(1) si noeud est connu.
  • Traversée avant et arrière
  • Accès indexé toujours O(n)

Implémentation

from dataclasses import dataclass
from typing import Optional

@dataclass
class DNode:
value: any
prev: Optional['DNode'] = None
next: Optional['DNode'] = None

@dataclass
class DoublyLinkedList:
head: Optional[DNode] = None
tail: Optional[DNode] = None

def append(self, value) -> None:
new = DNode(value, prev=self.tail)
if self.tail:
self.tail.next = new
else:
self.head = new
self.tail = new

def delete_node(self, node: DNode) -> None:
if node.prev:
node.prev.next = node.next
else:
self.head = node.next
if node.next:
node.next.prev = node.prev
else:
self.tail = node.prev

Complexités

OpérationAccès aléatoireInsertion têteInsertion finInsertion milieuSuppression têteSuppression finSuppression milieuMémoire
Liste doublement chaînéeO(n)O(1)O(1)*O(1)**O(1)O(1)*O(1)**Pointeur double

*Insertion/suppression en tête ou en fin est O(1) si on possède déjà le nœud (par exemple via un pointeur head ou tail). **Insertion/suppression en milieu est O(1) si on possède déjà le nœud à insérer ou à supprimer (sinon O(n) pour le trouver).

Quand l’utiliser ?

  • Lorsque les noeuds sont très coûteux à recopier en mémoire
  • Besoin de parcourir la liste dans les deux sens
  • Suppression fréquente de nœuds intérieurs en O(1)
  • Gestion de files / déques manuelles

Comparaison & Choix

StructureAccès aléatoireInsertion têteInsertion finInsertion milieuSuppression têteSuppression finSuppression milieuMémoireCas d’usage typiques
Tableau statique (Array)O(1)O(n)O(n)O(n)O(n)O(n)O(n)FaibleTableaux C, buffers fixes
Tableau dynamique (ArrayList)O(1)O(n)O(1)*O(n)O(n)O(1)*O(n)Moyen (+ redim.)Listes générales, pile, file
Liste simplement chaînée (Singly Linked)O(n)O(1)O(n)*O(n)O(1)O(n)*O(n)Pointeur simpleFile FIFO, pile LIFO (stack)
Liste doublement chaînée (Doubly Linked)O(n)O(1)O(1)*O(1)**O(1)O(1)*O(1)**Pointeur doubleDéque, navigation bidirectionnelle

*Insertion/suppression en fin est O(1) pour les listes chaînées si on possède déjà le dernier nœud, sinon O(n). **Insertion/suppression en milieu est O(1) pour les listes doublement chaînées si on possède déjà le nœud, sinon O(n).

En résumé :

  • Tableau statique (Array) : quand la taille est fixe et l’accès indexé critique.
  • Tableau dynamique (ArrayList) : usage général en Python (list), lorsque la taille varie mais que l’on veut un bon compromis accès/insertion.
  • Liste simplement chaînée (Singly Linked List) : pour insertions/suppressions rapides en tête, ou implémenter une file simple.
  • Liste doublement chaînée (Doubly Linked List) : pour parcours bidirectionnel ou suppression rapide de n’importe quel nœud connu.