Structures de données Python3

Dans ce chapitre, nous combinons principalement les points de connaissance appris précédemment pour présenter les structures de données Python.

Listes

En Python, les listes sont mutables, ce qui est la caractéristique la plus importante qui les distingue des chaînes de caractères et des tuples. En une phrase : les listes peuvent être modifiées, alors que les chaînes de caractères et les tuples ne le peuvent pas.

Voici les méthodes des listes en Python :

Méthode Description
list.append(x) Ajoute un élément à la fin de la liste, équivalent à a[len(a):] = [x].
list.extend(L) Étend la liste en ajoutant tous les éléments de la liste spécifiée, équivalent à a[len(a):] = L.
list.insert(i, x) Insère un élément à une position spécifiée. Le premier paramètre est l'indice de l'élément avant lequel insérer. Par exemple, a.insert(0, x) insère au début de la liste entière, et a.insert(len(a), x) équivaut à a.append(x).
list.remove(x) Supprime le premier élément de la liste dont la valeur est x. Si aucun élément de ce type n'existe, une erreur est renvoyée.
list.pop([i]) Supprime de la liste l'élément à la position spécifiée et le renvoie. Si aucun indice n'est spécifié, a.pop() renvoie le dernier élément. L'élément est immédiatement supprimé de la liste. (Les crochets autour de i dans la méthode indiquent que ce paramètre est facultatif, et non que vous devez taper une paire de crochets. Vous verrez souvent cette notation dans le manuel de référence de la bibliothèque Python.)
list.clear() Supprime tous les éléments de la liste, équivalent à del a[:].
list.index(x) Renvoie l'indice du premier élément de la liste dont la valeur est x. Si aucun élément correspondant n'est trouvé, une erreur est renvoyée.
list.count(x) Renvoie le nombre de fois où x apparaît dans la liste.
list.sort() Trie les éléments de la liste.
list.reverse() Inverse les éléments de la liste.
list.copy() Renvoie une copie superficielle de la liste, équivalente à a[:].

L'exemple suivant illustre la plupart des méthodes des listes :

Exemple

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print(a.count(333), a.count(66.25), a.count('x'))
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.supprimer(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.trier()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]

Remarque : Les méthodes comme insert, remove ou sort qui modifient les listes ne renvoient pas de valeur.

Utiliser les listes comme piles

En Python, vous pouvez utiliser une liste pour implémenter une pile. Une pile est une structure de données de type dernier entré, premier sorti (LIFO, Last-In-First-Out), ce qui signifie que le dernier élément ajouté est le premier retiré. Les listes fournissent certaines méthodes qui les rendent très adaptées aux opérations de pile, en particulierappend()etpop()méthodes.

Utilisez la méthode append() pour ajouter un élément au sommet de la pile, et utilisez la méthode pop() sans indice pour retirer un élément du sommet de la pile.

Opérations sur les piles

  • Empiler: Ajouter un élément au sommet de la pile.
  • Dépiler: Retirer et renvoyer l'élément au sommet de la pile.
  • Consulter/Sommet: Renvoyer l'élément au sommet de la pile sans le retirer.
  • Est vide: Vérifier si la pile est vide.
  • Taille: Obtenir le nombre d'éléments dans la pile.

Voici une explication détaillée de la manière d'implémenter ces opérations à l'aide de listes en Python :

1. Créer une pile vide

Exemple

stack = []

2. Opération d'empilement

Utilisez la méthode append() pour ajouter un élément au sommet de la pile :

Exemple

stack.append(1)
stack.append(2)
stack.append(3)
print(stack)  # Sortie : [1, 2, 3]

3. Opération de dépilement

Utilisez la méthode pop() pour supprimer et renvoyer l'élément au sommet de la pile :

Exemple

top_element = stack.pop()
print(top_element)  # Sortie : 3
print(stack)        # Sortie : [1, 2]

4. Afficher l'élément au sommet de la pile (Peek/Top)

Accédez directement au dernier élément de la liste (sans le supprimer) :

Exemple

top_element = stack[-1]
print(top_element)  # Sortie : 2

5. Vérifier si elle est vide (IsEmpty)

Vérifiez si la liste est vide :

Exemple

is_empty = len(stack) == 0
print(is_empty)  # Sortie : False

6. Obtenir la taille de la pile (Size)

Utilisez la fonction len() pour obtenir le nombre d'éléments dans la pile :

Exemple

size = len(stack)
print(size)  # Sortie : 2

Exemple

Voici un exemple complet montrant comment utiliser les opérations ci-dessus pour implémenter une pile simple :

Exemple

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("pop depuis une pile vide")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("peek depuis une pile vide")

    def is_empty(self):
        return len(self.stack) == 0

    def size(self):
        return len(self.stack)

# Exemple d'utilisation
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Élément au sommet :", stack.peek())  # Sortie : Élément au sommet : 3
print("Taille de la pile :", stack.size())    # Sortie : Taille de la pile : 3

print("Élément dépilé :", stack.pop())  # Sortie : Élément dépilé : 3
print("La pile est-elle vide :", stack.is_empty())  # Sortie : La pile est-elle vide : False
print("Stack size:", stack.size())    # Sortie : Stack size: 2

Dans le code ci-dessus, nous avons défini une classe Stack qui encapsule une liste comme structure de données sous-jacente et implémente les opérations de base d'une pile.

La sortie est la suivante :

栈顶元素: 3
栈大小: 3
弹出元素: 3
栈是否为空: False
栈大小: 2

Utilisation de listes comme files d'attente

En Python, une liste peut être utilisée comme une file d'attente, mais en raison des caractéristiques des listes, utiliser directement une liste pour implémenter une file d'attente n'est pas le choix optimal.

Une file d'attente est une structure de données de type premier entré, premier sorti (FIFO, First-In-First-Out), ce qui signifie que l'élément ajouté en premier est retiré en premier.

Lorsque vous utilisez une liste, si vous insérez ou supprimez fréquemment des éléments au début de la liste, les performances seront affectées car la complexité temporelle de ces opérations est O(n). Pour résoudre ce problème, Python fournit collections.deque, qui est une file d'attente à double extrémité permettant d'ajouter et de supprimer efficacement des éléments aux deux extrémités.

Implémentation d'une file d'attente avec collections.deque

collections.deque fait partie de la bibliothèque standard Python et est très adapté pour implémenter des files d'attente.

Voici un exemple d'implémentation d'une file d'attente avec deque :

Exemple

from collections import deque

# Créer une file d'attente vide
queue = deque()

# Ajouter des éléments à la fin de la file d'attente
queue.append('a')
queue.append('b')
queue.append('c')

print("État de la file :", queue)  # Sortie : État de la file : deque(['a', 'b', 'c'])

# Supprimer un élément en tête de la file
first_element = queue.popleft()
print("Élément supprimé :", first_element)  # Sortie : Élément supprimé : a
print("État de la file :", queue)            # Sortie : État de la file : deque(['b', 'c'])

# Afficher l'élément de tête (sans le retirer)
front_element = queue[0]
print("Élément de tête :", front_element)    # Sortie : Élément de tête : b

# Vérifier si la file est vide
is_empty = len(queue) == 0
print("La file est-elle vide :", is_empty)     # Sortie : La file est-elle vide : False

# Obtenir la taille de la file
size = len(queue)
print("Taille de la file :", size)            # Sortie : Taille de la file : 2
```

Implémentation d'une file avec des listes

Bien que deque soit plus efficace, si vous tenez à utiliser une liste pour implémenter une file, vous pouvez toujours le faire. Voici un exemple d'utilisation d'une liste pour implémenter une file :

1. Créer une file

Exemple

queue = []

2. Ajouter des éléments à la fin de la file

Utilisez la méthode append() pour ajouter des éléments à la fin de la file :

Exemple

queue.append('a')
queue.append('b')
queue.append('c')
print("État de la file :", queue)  # Sortie : État de la file : ['a', 'b', 'c']

3. Supprimer des éléments à l'avant de la file

Utilisez la méthode pop(0) pour supprimer des éléments à l'avant de la file :

Exemple

first_element = queue.pop(0)
print("Élément supprimé :", first_element)  # Sortie : Élément supprimé : a
print("État de la file :", queue)            # Sortie : État de la file : ['b', 'c']

4. Afficher l'élément de tête de la file (sans le retirer)

Accéder directement au premier élément de la liste :

Exemple

front_element = queue[0]
print("Front element:", front_element)    # Sortie : Front element: b

5. Vérifier si la file est vide

Vérifiez si la liste est vide :

Exemple

is_empty = len(queue) == 0
print("La file est-elle vide :", is_empty)     # Sortie : La file est-elle vide : False

6. Obtenir la taille de la file

Utiliser la fonction len() pour obtenir la taille de la file :

Exemple

size = len(queue)
print("Taille de la file :", size)            # Sortie : Taille de la file : 2

Exemple (implémentation d'une file avec des listes)

Exemple


class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("peek from empty queue")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

# Exemple d'utilisation
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')

print("Élément en tête :", queue.peek())    # Sortie : Élément en tête : a
print("Taille de la file :", queue.size())    # Sortie : Taille de la file : 3

print("Élément retiré :", queue.dequeue())  # Sortie : Élément retiré : a
print("La file est-elle vide :", queue.is_empty())  # Sortie : La file est-elle vide : False
print("Taille de la file :", queue.size())    # Sortie : Taille de la file : 2

Bien que vous puissiez utiliser une liste pour implémenter une file, utiliser collections.deque est plus efficace et concis. Il offre une complexité temporelle O(1) pour les opérations d'ajout et de suppression, ce qui le rend très adapté à une structure de données de file.

Compréhensions de listes

Les compréhensions de listes offrent un moyen concis de créer des listes à partir de séquences. Habituellement, une application applique certaines opérations à chaque élément d'une séquence, en utilisant les résultats comme éléments d'une nouvelle liste, ou crée des sous-séquences en fonction de conditions déterminées.

Une compréhension de liste consiste en une expression suivie d'une clause for, puis de zéro ou plusieurs clauses for ou if. Le résultat est une liste générée à partir de l'expression dans le contexte des clauses for et if suivantes. Si vous voulez que l'expression produise un tuple, vous devez utiliser des parenthèses.

Ici, nous multiplions chaque valeur de la liste par trois pour obtenir une nouvelle liste :

>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]

Maintenant, jouons avec quelques astuces :

>>> [[x, x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]

Ici, nous appelons une méthode sur chaque élément de la séquence un par un :

Exemple

>>> freshfruit = [' banana', ' loganberry ', 'passion fruit ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']

Nous pouvons utiliser une clause if comme filtre :

>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]

Voici quelques démonstrations de boucles et d'autres techniques :

>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Les compréhensions de listes peuvent utiliser des expressions complexes ou des fonctions imbriquées :

>>> [str(round(355/113, i)) for i in range(1, 6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']

Compréhensions de listes imbriquées

Les listes Python peuvent aussi être imbriquées.

L'exemple suivant présente une matrice 3X4 sous forme de liste :

>>> matrix = [
...     [1, 2, 3, 4],
...     [5, 6, 7, 8],
...     [9, 10, 11, 12],
... ]

L'exemple suivant convertit la matrice 3X4 sous forme de liste en une liste 4X3 :

>>> [[row[i] for row in matrix] for i in range(4)]
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

L'exemple ci-dessus peut aussi être implémenté en utilisant la méthode suivante :

>>> transposed = []
>>> for i in range(4):
...     transposed.append([row[i] for row in matrix])
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

Une autre méthode d'implémentation :

>>> transposed = []
>>> for i in range(4):
...     # les 3 lignes suivantes implémentent la compréhension de liste imbriquée
...     transposed_row = []
...     for row in matrix:
...         transposed_row.append(row[i])
...     transposed.append(transposed_row)
...
>>> transposed
[[1, 5, 9], [2, 6, 10], [3, 7, 11], [4, 8, 12]]

L'instruction del

L'instruction del peut être utilisée pour supprimer un élément d'une liste par indice plutôt que par valeur. Cela diffère de l'utilisation de pop(), qui renvoie une valeur. L'instruction del peut être utilisée pour supprimer une tranche d'une liste, ou pour vider entièrement la liste (la méthode que nous avons présentée plus tôt consiste à affecter une liste vide à cette tranche). Par exemple :

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

Vous pouvez également utiliser del pour supprimer des variables :

>>> del a

Tuples et séquences

Un tuple est constitué d'un certain nombre de valeurs séparées par des virgules, par exemple :

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Les tuples peuvent être imbriqués :
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

Comme vous pouvez le voir, les tuples sont toujours entourés de parenthèses dans la sortie afin que les structures imbriquées soient exprimées correctement. Ils peuvent être saisis avec ou sans parenthèses, bien que les parenthèses soient généralement nécessaires si le tuple fait partie d'une expression plus grande.

Ensembles

Un ensemble est une collection non ordonnée d'éléments uniques. Les fonctionnalités de base incluent le test d'appartenance et l'élimination des éléments en double.

Les ensembles peuvent être créés avec des accolades ({}). Remarque : pour créer un ensemble vide, vous devez utiliser set() à la place ; ce dernier crée un dictionnaire vide, une structure de données que nous présenterons dans la section suivante.

Ce qui suit est une démonstration simple :

>>> basket = {'apple', 'orange', 'apple', 'pear', 'orange', 'banana'}
>>> print(basket)                      # Supprimer les doublons
{'orange', 'banana', 'pear', 'apple'}
>>> 'orange' in basket                 # Vérifier l'appartenance
True
>>> 'crabgrass' in basket
False

>>> # Ce qui suit illustre les opérations sur deux ensembles
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # Lettres uniques dans a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b                              # Lettres dans a mais pas dans b
{'r', 'd', 'b'}
>>> a | b                              # Lettres dans a ou b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b                              # Lettres à la fois dans a et b
{'a', 'c'}
>>> a ^ b                              # Lettres dans a ou b mais pas dans les deux
{'r', 'd', 'b', 'm', 'z', 'l'}

Les ensembles prennent aussi en charge les compréhensions :

>>> a = {x for x in 'abracadabra' if x not in 'abc'}
>>> a
{'r', 'd'}

Dictionnaires

Un autre type de données intégré très utile en Python est le dictionnaire.

Les séquences sont indexées par des entiers consécutifs ; par contraste, les dictionnaires sont indexés par des clés, qui peuvent être de n'importe quel type immuable, généralement des chaînes de caractères ou des nombres.

La meilleure façon de comprendre un dictionnaire est de le voir comme une collection non ordonnée de paires clé=>valeur. Au sein d’un même dictionnaire, les clés doivent être distinctes les unes des autres.

Une paire d’accolades crée un dictionnaire vide : {}.

Voici un exemple simple d’utilisation d’un dictionnaire :

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> list(tel.keys())
['irv', 'guido', 'jack']
>>> sorted(tel.keys())
['guido', 'irv', 'jack']
>>> 'guido' in tel
True
>>> 'jack' not in tel
False

Le constructeur dict() construit des dictionnaires directement à partir d'une liste de paires clé-valeur. S'il existe un modèle fixe, les compréhensions de listes peuvent spécifier des paires clé-valeur particulières :

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}

De plus, les compréhensions de dictionnaires peuvent être utilisées pour créer des dictionnaires avec des expressions arbitraires de clé et de valeur :

>>> {x: x**2 for x in (2, 4, 6)}
{2: 4, 4: 16, 6: 36}

Si les clés sont des chaînes simples, il est parfois plus pratique de spécifier des paires clé-valeur à l'aide d'arguments nommés :

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}

Techniques de boucle

Lorsqu'on parcourt un dictionnaire, les clés et les valeurs correspondantes peuvent être récupérées en même temps à l'aide de la méthode items() :

>>> knights = {'gallahad': 'le pur', 'robin': 'le brave'}
>>> for k, v in knights.items():
...     print(k, v)
...
gallahad le pur
robin le brave

Lors d'une itération sur une séquence, la position d'index et la valeur correspondante peuvent être obtenues en même temps à l'aide de la fonction enumerate() :

>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print(i, v)
...
0 tic
1 tac
2 toe

Pour parcourir deux séquences ou plus en même temps, utilisez zip() pour les combiner :

>>> questions = ['nom', 'quête', 'couleur préférée']
>>> answers = ['lancelot', 'le Saint Graal', 'bleu']
>>> for q, a in zip(questions, answers):
...     print('Quel est votre {0} ? C'est {1}.'.format(q, a))
...
Quel est votre nom ? C' est lancel.
Quelle est votre quête ? C' est le Saint Graal.
Quelle est votre couleur préférée ? C' est bleu.

Pour parcourir une séquence en sens inverse, spécifiez d'abord la séquence, puis appelez la fonction reversed() :

>>> for i in reversed(range(1, 10, 2)):
...     print(i)
...
9
7
5
3
1

Pour parcourir une séquence dans l'ordre, utilisez la fonction sorted(), qui renvoie une séquence triée sans modifier l'original :

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print(f)
...
pomme
banane
orange
pear

Documentation de référence

Autres extensions