Tableaux dynamiques

Énoncé

Comme nous l'avons vu dans un exercice précédent, les tableaux statiques n'existent pas en Python. En effet Python ne fournit que des tableaux dynamiques, appelés list dans le language, que nous avons utilisés comme des tableaux statiques jusqu'à présent.

Pour créer une list (donc un tableau dynamique) en Python il suffit d'utiliser des crochets :

>>> tab_dyn = [1, 2, 3]

Pour rappel, voici le lien vers le document résumant les différences entre tableaux, tableaux statiques et listes chaînées.

Lancez l'interpréteur interactif, et faites des petits tests pour :

• créer une list ;
• accéder à un élément à partir d'un index ;
• ajouter un élément à la fin ;
• ajouter un élément au début ;
• supprimer un élément à la fin ;
• supprimer un élément au début.

Pensez à utiliser la commande help fournie par l'interpréteur interactif. Par exemple help(list.append).

Enfin, quelle est la complexité en temps de chacun de ces tests ?. Autrement dit, quel est le nombre d'opérations nécessaires à chacune des opérations sur une list Python ? VOUS DEVEZ AVOIR COMPRIS ET CONNAÎTRE PAR CŒUR LA RÉPONSE À CETTE QUESTION !

Correction

Cliquez ici pour révéler la correction.

tableaux.py :

#!/usr/bin/env python3
"""Premiers tests avec des tableaux dynamiques python"""

# Une list (sans le E), c'est à dire un tableau dynamique.
tab_dyn = [1, "super", "tableau dynamique", "python"]
print(tab_dyn)

# Un accès indexé, sachant que ça commence à zéro.
# Ça ne coûte pas cher car le tableau est contigu
# en mémoire.
# Autrement dit, complexité en temps = O(1)
elem = tab_dyn[2]
print(elem)

# Ajout à la fin
# Ça ne coûte pas cher car on colle juste le nouvel
# élément dans une place libre à la fin.
# Autrement dit, complexité en temps = O(1)
tab_dyn.append(41)
print(tab_dyn)

# Ajout au début.
# Ça coûte cher, faut bouger tout le monde vers la droite.
# Autrement dit, complexité en temps = O(n) avec n qui est
# la taille du tableau dynamique.
tab_dyn.insert(0, "je me suis incrusté en tête du tableau")
print(tab_dyn)

# Suppression à la fin.
# Ça ne coûte pas cher, on enlève juste le dernier élément.
# Autrement dit, complexité en temps = O(1)
tab_dyn.pop()
print(tab_dyn)

# Suppression au début.
# Ça coûte cher, faut bouger tout le monde vers la gauche.
# Autrement dit, complexité en temps = O(n) avec n qui est
# la taille du tableau dynamique.
tab_dyn.pop(0)
print(tab_dyn)