Informatique et Calcul Scientifique

Cours 4

Author

Leonard Hardiman et Ghid Maatouk

Structures de données

Un programme informatique (en Python ou autre) manipule des données.

  • Une partie essentielle de la programmation et de l’algorithmique est de choisir les bonnes structures de données: la manière d’organiser les données et de les stocker en mémoire afin de permettre à certaines opérations de manipulation des données de se dérouler de manière efficace (on quantifiera “efficace” plus tard…)

  • Dans ce cours, on étudiera une des principales structures de données en Python: les listes.

Listes en Python

Une liste Python est une structure de données qui permet de regrouper diverses objets de manière ordonnée (comme un tuple).

  • L = ['a', 'b', 'c', 'd', 'e']

    L =

  • L = [21, 33, "abc", [1, 2, 3]]

    L =

Remarque. La représentation des listes ci-dessus est schématique et ne reflète pas ce qui se passe vraiment en mémoire - plus d’infos plus tard.

Opérations sur les listes

  • Comme pour un tuple, on peut créer une liste et effectuer des opérations de lecture dessus :
    • Accéder à un élément d’une liste
    • Copier une liste
    • Effectuer des calculs sur une liste: trouver la moyenne, le max, la longueur, …
  • À la différence d’un tuple, on peut effectuer des opérations d’écriture sur une liste :
    • Modifier un élément d’une liste
    • Ajouter ou enlever un élément de la fin d’une liste
    • Insérer ou enlever un élément à un index quelconque de la liste
    • Etendre une liste avec les éléments d’une autre liste

Les listes sont notre premier exemple d’un objet modifiable en Python, de tels objets sont dits mutables.

Créer une liste

On déclare une liste par des valeurs séparées par des virgules et le tout encadré par des crochets droits.

  • L’instruction L = [0, 2, 4, 6] crée une liste contenant les éléments 0, 2, 4 et 6 et l’affecte à la variable L.
  • On peut créer une liste vide: L = []
L = [1, 2, 3]
print('L =', L)
L = [1, 2, 3]
L = ['a', 'b', 'c']
print('L =', L)
L = ['a', 'b', 'c']
L = [1, 'a', 2, 'b', 3, 'c']
print('L =', L)
L = [1, 'a', 2, 'b', 3, 'c']
L = [[1, 2, 3], ['a', 'b', 'c']]
print('L =', L)
L = [[1, 2, 3], ['a', 'b', 'c']]

Remarque. Les éléments d’une liste n’ont pas besoin d’être du même type… mais une bonne pratique en Python est que, à la différence des tuple, les listes ne contiennent que des éléments du même type.

L’indexage et l’itération sur les listes

Comme les tuple et les str, les listes sont indexables (et donc itérables). Ça fonctionne exactement comme sur les tuple:

t = ('a', 'b', 'c', 'd')
print('t[0] =', t[0])
t[0] = a
L = ['a', 'b', 'c', 'd']
print('L[0] =', L[0])
L[0] = a

t = ('a', 'b', 'c', 'd')
for s in t:
    print(s, end='')
abcd
L = ('a', 'b', 'c', 'd')
for s in L:
    print(s, end='')
abcd

L’indexage et les indices négatifs

  • On peut utiliser les indices négatifs -1, -2, ..., -n pour accéder aux éléments de la liste (ou tuple) à partir de la fin:

L = [1, 3, 5]

print('L[-2] =', L[-2])
L[-2] = 3
L = [1, 3, 5]

# Erreur 
print(L[5])
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[11], line 4
      1 L = [1, 3, 5]
      3 # Erreur 
----> 4 print(L[5])

IndexError: list index out of range
L = [1, 3, 5]

# Erreur
print(L[-4])
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[12], line 4
      1 L = [1, 3, 5]
      3 # Erreur
----> 4 print(L[-4])

IndexError: list index out of range

Remarque. Si on essaie d’accéder à un index i trop grand ou trop petit, une erreur est générée.

L’indexage et les tranches de liste

On peut aussi utiliser l’indexabilité pour accéder à une sous-liste de la liste : c’est le slicing.

  • L[i:j] crée nouvelle liste avec les éléments de L entre les indices i (inclus) et j (exclus).
L = [10, 30, 50, 70, 90]

print('L[2:4] =', L[2:4])
L[2:4] = [50, 70]
  • Si i est omis, il est pris à 0 par défaut. Si j est omis, il est pris à len(L) par défaut. L[:] est donc une copie de la liste L.
L = [10, 30, 50, 70, 90]

print('L[2:] =', L[2:])
L[2:] = [50, 70, 90]
L = [10, 30, 50, 70, 90]

print('L[:] =', L[:])
L[:] = [10, 30, 50, 70, 90]
  • On peut aussi définir un pas pour le slicing: L[i:j:k] est une liste contenant les éléments de L d’indices i, i + k, i + 2k, ... jusqu’à j exclus. Attention, comme pour range(), le pas peut être négatif !
L = [10, 20, 30, 40, 50, 60, 70]

print('L[2:6:2] =', L[2:6:2])
L[2:6:2] = [30, 50]
L = [10, 20, 30, 40, 50, 60, 70]

print('L[6:1:-2] =', L[6:1:-2])
L[6:1:-2] = [70, 50, 30]
L = [10, 20, 30, 40, 50, 60, 70]

print('L[:2] =', L[:2])
L[:2] = [10, 20]

Remarque. Tout cela fonctionne de manière identique pour les tuple.

Remarque. Lors du slicing avec un pas négatif, les valeurs par défaut de i et j changent pour devenir respectivement les indices de la fin et du début de la liste.

L = [10, 20, 30, 40, 50, 60, 70]
print('L[3::-2] =', L[3::-2])
L[3::-2] = [40, 20]
L = [10, 20, 30, 40, 50, 60, 70]
print('L[::-2] =', L[::-2])
L[::-2] = [70, 50, 30, 10]

Remarque. Le slicing a une interaction surprenante avec les indices négatifs. En général, on s’attend à ce que le slicing se comporte comme quand on applique append à une nouvelle liste sur un range :

L1 = [10, 20, 30, 40, 50, 60, 70, 80, 90]
L2 = L1[3:8:2]

print('L2 =', L2)

# est équivalent à
L1 = [10, 20, 30, 40, 50, 60, 70, 80, 90]
L2 = []
for i in range(3, 8, 2):
    L2.append(L1[i])
    
print('L2 =', L2)
L2 = [40, 60, 80]
L2 = [40, 60, 80]

Cependant, cela ne fonctionne plus lorsque nous utilisons des indices négatifs :

L1 = [10, 20, 30, 40, 50, 60, 70, 80, 90]
L2 = L1[3:-2:-2]

print('L2 =', L2)

# n'est PAS équivalent à
L1 = [10, 20, 30, 40, 50, 60, 70, 80, 90]
L2 = []
for i in range(3, -2, -2):
    L2.append(L1[i])
    
print('L2 =', L2)
L2 = []
L2 = [40, 20, 90]

C’est parce que dès que Python voit un indice négatif, il le convertit en l’indice positif correspondant et travaille avec celui-ci. Ainsi, L1[3:-2:-2] est ce que vous obtiendriez en appliquant append(L1[i]) sur range(3, len(L) - 2, -2) (qui serait vide dans notre exemple).

Personne n’a dit que Python était parfait !

Appartenance

Comme avec les autres itérables, on peut vérifier l’appartenance d’un élément de valeur x à une liste L avec le mot-clé in qui nous permet d’exprimer la condition booléenne x in L.

  • De même, on peut formuler la condition booléenne x not in L.
L = [1, 3, 5, 7]

print('2 in L:', 2 in L)
print('3 in L:', 3 in L)
print('8 not in L:', 8 not in L)

if 3 in L:
    print('ouf')
2 in L: False
3 in L: True
8 not in L: True
ouf

Concaténation

  • Comme les str, on peut concaténer deux listes ou tuple avec les opérateurs + et *. Ces opérations créent une nouvel objet.
print([1, 2] + [3, 4])
print([3,5] * 3) 

t1 = ('L.', 32)
t2 = ('espion',)

print((t1 + t2) * 2)
[1, 2, 3, 4]
[3, 5, 3, 5, 3, 5]
('L.', 32, 'espion', 'L.', 32, 'espion')
  • On peut réaffecter le résultat d’une opération de concaténation à la même variable. Aucun objet n’est modifié par l’opération, mais une variable a été réaffectée.
t = (1, 2, 3)
t1 = t
t = t + (4, 5)
print(t, t1)
(1, 2, 3, 4, 5) (1, 2, 3)
L = [1, 2, 3]
L1 = L
L = L + [4, 5]
print(L, L1)
[1, 2, 3, 4, 5] [1, 2, 3]
s = '123'
s1 = s
s = s + '45'
print(s, s1)
12345 123

Mutabilité des listes

Jusqu’ici, nous avons vu des opérations qui fonctionnent sur tous les objets itérables : indexage, tranches, concaténation, appartenance, etc.

Les listes sont notre premier exemple d’objets mutables en Python, c’est-à-dire qu’on peut les modifier après leur création. À partir de maintenant, nous allons voir des opérations qui modifient directement une liste existante. Ces opérations :

  • N’existent que pour les objets mutables (listes)
  • N’ont pas d’équivalent pour les objets immutables (str, tuple, range)
  • Changent l’objet “sur place” au lieu de créer un nouvel objet

Remarque. Comme ces opérations modifient l’objet lui-même, ils peuvent avoir des conséquences inattendues si plusieurs variables font référence au même objet !

Modifier un élément d’une liste

  • On peut modifier l’élément d’indice i d’une liste L avec l’instruction L[i] = nouvelle_valeur.
L = [1, 3, 5, 7, 9, 11]
print("Avant :", L)

L[2] = 'A'
print("Après :", L)
Avant : [1, 3, 5, 7, 9, 11]
Après : [1, 3, 'A', 7, 9, 11]

  • Si l’élément à remplacer est une tranche de liste, donc un objet itérable même s’il ne contient qu’un seul élément, il doit être remplacé par un autre objet itérable (liste, str, tuple, …).

  • Les deux itérables n’ont pas besoin d’être de même taille!

L = [1, 3, 5, 7, 9, 11]
print("Avant :", L)

L[2:5] = ['B']
print("Après :", L)
Avant : [1, 3, 5, 7, 9, 11]
Après : [1, 3, 'B', 11]
L = [1, 3, 5, 7, 9, 11]
print("Avant :", L)

L[1:3] = 'ICS'
print("Après :", L)
Avant : [1, 3, 5, 7, 9, 11]
Après : [1, 'I', 'C', 'S', 7, 9, 11]

Remarque. Si on essaye de modifier de la même manière un élément d’un tuple, une erreur est générée.

Insérer un élément à la fin d’une liste

La méthode append() permet de rajouter un élément à la fin d’une liste.

  • S’agissant d’une méthode, son appel est différent des fonctions habituelles. Pour appliquer la méthode append sur une liste L, on utilise la syntaxe: L.append(valeur).
L = [0, 1]
print(L, 'est de longueur', len(L))
[0, 1] est de longueur 2
L = [0, 1]
L.append(10)
print(L, 'est de longueur', len(L))
[0, 1, 10] est de longueur 3
L = [0, 1]
L.append(10)
L.append(13)
print(L, 'est de longueur', len(L))
[0, 1, 10, 13] est de longueur 4

Insérer un élément en milieu de liste

La méthode insert(i, x) appliquée sur la liste L permet d’y insérer l’élément x à l’indice i : L.insert(i,x)

  • Tous les éléments après i sont décalés “vers la droite”. L’élément qui était à l’indice i est maintenant à l’indice i+1.
L = [1, 3, 5, 7]
print('Avant:', L)

L.insert(2, 'a')
print("Après insert(2, 'a'):", L)
Avant: [1, 3, 5, 7]
Après insert(2, 'a'): [1, 3, 'a', 5, 7]

Remarque. Si on appelle insert avec un index trop grand, Python insère l’élément à la fin de la liste. Pour insérer un élément en tête de liste, on utilise L.insert(0, val).

Enlever un élément de la fin d’une liste

La méthode pop() permet d’enlever un élément de la fin d’une liste:

L = [3, 6, 9]
print('Avant pop():', L)

L.pop()
print('Après pop():', L)
Avant pop(): [3, 6, 9]
Après pop(): [3, 6]

pop() modifie la liste L et retourne l’élément enlevé de la liste, qu’on peut par exemple sauvegarder dans une variable.

L = ['a', 'c', 'd', 'b']
print('L =', L)
x = L.pop()
print("On a pop l'objet", x)
print('L =', L)
L = ['a', 'c', 'd', 'b']
On a pop l'objet b
L = ['a', 'c', 'd']

Remarque. Si on essaie d’appliquer pop() à une liste vide, Python génère une erreur.

Enlever un élément du milieu d’une liste

La méthode pop() peut aussi prendre un indice comme argument optionnel.

  • Dans ce cas L.pop(i) enlève l’élément à l’indice i de la liste, et décale tous les éléments qui suivent “vers la gauche”:
L = [1, 3, 5, 7, 9]
x = L.pop(2)
print('on a pop l\'élément', x)
print(L)
on a pop l'élément 5
[1, 3, 7, 9]

Remarque. Si on appelle L.pop(i) avec i trop grand ou trop petit, Python génère une erreur.

Enlever un élément selon sa valeur

On peut enlever un élément de la liste selon sa valeur au lieu de son indice.

  • La méthode L.remove(x) enlève le premier élément de valeur x dans la liste L, si un tel élément existe. Elle retourne None.
L = [1, 3, 5, 7, 3]
print('Avant remove(3):', L)

L.remove(3)
print('Après remove(3):', L)

L.remove(3)
print('Après remove(3) encore:', L)
Avant remove(3): [1, 3, 5, 7, 3]
Après remove(3): [1, 5, 7, 3]
Après remove(3) encore: [1, 5, 7]

Remarque. Si on appelle remove avec une valeur qui n’est pas présente dans la liste, Python génère une erreur.

Étendre une liste

Pour des listes L1 et L2, L1.extend(L2) ajoute tous les éléments de L2 à la fin de L1. Elle modifie donc L1 et laisse L2 telle quelle.

L1 = [1, 3]
L2 = [2, 4]
print('Avant extend :')
print('\tL1 =', L1, '\n\tL2 =', L2)

L1.extend(L2)
print('\nAprès L1.extend(L2):')
print('\tL1 =', L1, '\n\tL2 =', L2)
Avant extend :
    L1 = [1, 3] 
    L2 = [2, 4]

Après L1.extend(L2):
    L1 = [1, 3, 2, 4] 
    L2 = [2, 4]

Remarque. Il ne faut pas confondre L1.extend(L2) avec L1 = L1 + L2. Quelle est la différence ?

Remarque. Étonnamment, L1 += L2 n’est pas équivalent à L1 = L1 + L2, mais fonctionne exactement comme L1.extend(L2). Dans le doute, n’utilisez pas += ou *= sur des objets mutables.

Calculs sur les séquences (objets indexables)

  • Pour toutes les séquences (str, tuple, listes, …):

    • La fonction len retourne la longueur (le nombre d’éléments),

      L = [6, 2, 10, 6, 4, 8]

print('Longueur:', len(L))
      Longueur: 6

    • max et min donnent le maximum et le minimum (s’il existe un ordre sur les valeurs de la séquence!),

      L = [6, 2, 10, 6, 4, 8]

m, M = min(L), max(L)
print('m =', m, ', M =', M)
      m = 2 , M = 10

    • t.count(x) retourne le nombre d’occurrences de la valeur x dans t,

      L = [6, 2, 10, 6, 4, 8]
print('Nombre de 6 dans L:', L.count(6))
print('Nombre de 1 dans L:', L.count(1))
      Nombre de 6 dans L: 2
Nombre de 1 dans L: 0

    • t.index(x) retourne le premier indice de t où x apparaît si un tel indice existe.

      L = [6, 2, 10, 6, 4, 8]

print('Index de 6:', L.index(6))
print('Index de 10:', L.index(10))
      Index de 6: 0
Index de 10: 2
  • Exclusivement pour les séquences mutables (listes)

    • L.sort() trie la liste L,

      L = [6, 2, 10, 6, 4, 8]
print('Liste originale:', L)

L.sort()
print('La liste triée:', L)
      Liste originale: [6, 2, 10, 6, 4, 8]
La liste triée: [2, 4, 6, 6, 8, 10]

    • L.reverse() inverse l’ordre des éléments de L.

      L = [6, 2, 10, 6, 4, 8]
print('Liste originale:', L)

L.reverse()
print('La liste inversée:', L)
      Liste originale: [6, 2, 10, 6, 4, 8]
La liste inversée: [8, 4, 6, 10, 2, 6]

Caster vers les listes / tuple

Vous pouvez caster n’importe quel objet indexable en liste ou tuple.

s = 'ics'
L = list(s)
print('String original:', s)
print('Liste créée:', L)

L[0] = 'I'
L.append('!')
print('Liste modifiée:', L)
L.reverse()
print('Liste inversée:', L)
String original: ics
Liste créée: ['i', 'c', 's']
Liste modifiée: ['I', 'c', 's', '!']
Liste inversée: ['!', 's', 'c', 'I']
r = range(5, 10, 2)
t = tuple(r)
print('Range original:', r)
print('Tuple créé:', t)

print(t, "n'est pas mutable...")
Range original: range(5, 10, 2)
Tuple créé: (5, 7, 9)
(5, 7, 9) n'est pas mutable...

Remarque. Convertir un objet itérable en tuple ne vous permettra pas d’exploiter la mutabilité.