10 structures de données Python [Explained With Examples]

Vous cherchez à ajouter des structures de données à votre boîte à outils de programmation ? Faites vos premiers pas dès aujourd’hui en découvrant les structures de données en Python.

Lorsque vous apprenez un nouveau langage de programmation, il est important de comprendre les types de données de base et les structures de données intégrées prises en charge par le langage. Dans ce guide sur les structures de données en Python, nous aborderons les points suivants :

• avantages des structures de données
• structures de données intégrées en Python, telles que des listes, des tuples, des dictionnaires et des ensembles
• implémentations de types de données abstraits tels que les piles et les files d’attente.

Commençons!

Pourquoi les structures de données sont-elles utiles ?

Avant de passer en revue les différentes structures de données, voyons comment l’utilisation de structures de données peut être utile :

• Traitement efficace des données: Choisir la bonne structure de données permet de traiter les données plus efficacement. Par exemple, si vous devez stocker une collection d’éléments du même type de données (avec des temps de recherche constants et un couplage étroit), vous pouvez choisir un tableau.
• Meilleure gestion de la mémoire: Dans les grands projets, pour stocker les mêmes données, une structure de données peut être plus efficace en mémoire qu’une autre. Par exemple, en Python, les listes et les tuples peuvent être utilisés pour stocker des collections de données de types de données identiques ou différents. Cependant, si vous savez que vous n’avez pas à modifier la collection, vous pouvez choisir un tuple qui occupe relativement moins de mémoire qu’une liste.
• Code plus organisé: L’utilisation de la bonne structure de données pour une fonctionnalité particulière rend votre code plus organisé. Les autres développeurs qui liront votre code s’attendront à ce que vous utilisiez des structures de données spécifiques en fonction du comportement souhaité. Par exemple : si vous avez besoin d’un mappage clé-valeur avec des temps de recherche et d’insertion constants, vous pouvez stocker les données dans un dictionnaire.

Listes

Lorsque nous devons créer des tableaux dynamiques en Python, des entretiens de codage aux cas d’utilisation courants, les listes sont les structures de données incontournables.

Les listes Python sont des types de données de conteneur modifiables et dynamiques, vous pouvez donc ajouter et supprimer des éléments d’une liste en place, sans avoir à créer une copie.

Lors de l’utilisation de listes Python :

• L’indexation dans la liste et l’accès à un élément à un index spécifique est une opération à temps constant.
• L’ajout d’un élément à la fin de la liste est une opération à temps constant.
• L’insertion d’un élément à un index spécifique est une opération temporelle linéaire.

Il existe un ensemble de méthodes de liste qui nous aident à effectuer efficacement les tâches courantes. L’extrait de code ci-dessous montre comment effectuer ces opérations sur un exemple de liste :

>>> nums = [5,4,3,2]

>>> nums.append(7)
>>> nums
[5, 4, 3, 2, 7]

>>> nums.pop()
7
>>> nums
[5, 4, 3, 2]

>>> nums.insert(0,9)
>>> nums
[9, 5, 4, 3, 2]

Les listes Python prennent également en charge le découpage en tranches et les tests d’appartenance à l’aide de la in Opérateur:

>>> nums[1:4]
[5, 4, 3]

>>> 3 in nums
True

La structure de données de la liste est non seulement flexible et simple, mais nous permet également de stocker des éléments de différents types de données. Python a également une structure de données de tableau dédiée pour des éléments de stockage efficaces du même type de données. Nous en apprendrons plus tard dans ce guide.

Tuples

En Python, les tuples sont une autre structure de données intégrée populaire. Ils sont comme des listes Python en ce sens que vous pouvez les indexer en temps constant et les découper. Mais ils sont immuable, vous ne pouvez donc pas les modifier sur place. L’extrait de code suivant explique ce qui précède avec un exemple nums tuple :

>>> nums = (5,4,3,2)

>>> nums[0]
5

>>> nums[0:2]
(5, 4)

>>> 5 in nums
True

>>> nums[0] = 7 # not a valid operation!
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Ainsi, lorsque vous souhaitez créer une collection immuable et pouvoir la traiter efficacement, vous devez envisager d’utiliser un tuple. Si vous souhaitez que la collection soit modifiable, préférez utiliser une liste à la place.

📋 En savoir plus sur les similitudes et les différences entre les listes Python et les tuples.

Tableaux

Les tableaux sont des structures de données moins connues en Python. Elles sont similaires aux listes Python en termes d’opérations qu’elles prennent en charge, telles que l’indexation en temps constant et l’insertion d’un élément à un index spécifique en temps linéaire.

Cependant, la principale différence entre les listes et les tableaux est que les tableaux stockent les éléments d’un type de données unique. Par conséquent, ils sont étroitement couplés et économes en mémoire.

Pour créer un tableau, nous pouvons utiliser le array() constructeur de l’intégré array module. Le array() Le constructeur prend une chaîne spécifiant le type de données des éléments et les éléments. Ici, nous créons nums_fun tableau de nombres à virgule flottante :

>>> from array import array
>>> nums_f = array('f',[1.5,4.5,7.5,2.5])
>>> nums_f
array('f', [1.5, 4.5, 7.5, 2.5])

Vous pouvez indexer dans un tableau (similaire aux listes Python):

>>> nums_f[0]
1.5

Les tableaux sont modifiables, vous pouvez donc les modifier :

>>> nums_f[0]=3.5
>>> nums_f
array('f', [3.5, 4.5, 7.5, 2.5])

Mais vous ne pouvez pas modifier un élément pour qu’il soit d’un différent Type de données:

>>> nums_f[0]='zero'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: must be real number, not str

Cordes

En Python, les chaînes sont immuable collections de caractères Unicode. Contrairement aux langages de programmation comme C, Python n’a pas de type de données caractère dédié. Un caractère est donc aussi une chaîne de longueur un.

Comme mentionné, la chaîne est immuable :

>>> str_1 = 'python'
>>> str_1[0] = 'c'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Les chaînes Python prennent en charge le découpage de chaînes et un ensemble de méthodes pour les formater. Voici quelques exemples:

>>> str_1[1:4]
'yth'
>>> str_1.title()
'Python'
>>> str_1.upper()
'PYTHON'
>>> str_1.swapcase()
'PYTHON'

⚠ N’oubliez pas que toutes les opérations ci-dessus renvoient une copie de la chaîne et ne modifient pas la chaîne d’origine. Si vous êtes intéressé, consultez le guide sur les programmes Python sur les opérations de chaîne.

Ensembles

En Python, les ensembles sont des collections d’éléments uniques et hachables. Vous pouvez effectuer les opérations d’ensemble communes telles que l’union, l’intersection et la différence :

>>> set_1 = {3,4,5,7}
>>> set_2 = {4,6,7}

>>> set_1.union(set_2)
{3, 4, 5, 6, 7}

>>> set_1.intersection(set_2)
{4, 7}

>>> set_1.difference(set_2)
{3, 5}

Les ensembles sont modifiables par défaut, vous pouvez donc ajouter de nouveaux éléments et les modifier :

>>> set_1.add(10)
>>> set_1
{3, 4, 5, 7, 10}

📚 Ensembles de lecture en Python : un guide complet avec des exemples de code

FrozenSets

Si vous voulez un ensemble immuable, vous pouvez utiliser un ensemble figé. Vous pouvez créer un ensemble figé à partir d’ensembles existants ou d’autres itérables.

>>> frozenset_1 = frozenset(set_1)
>>> frozenset_1
frozenset({3, 4, 5, 7, 10, 11})

Parce que frozenset_1 est un ensemble gelé, nous rencontrons des erreurs si nous essayons d’ajouter des éléments (ou de le modifier autrement) :

>>> frozenset_1.add(15)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

Dictionnaires

Un dictionnaire Python est fonctionnellement similaire à une carte de hachage. Les dictionnaires sont utilisés pour stocker des paires clé-valeur. Les clés du dictionnaire doivent être hachables. Cela signifie que la valeur de hachage de l’objet ne change pas.

Vous pouvez accéder aux valeurs à l’aide de clés, insérer de nouveaux éléments et supprimer des éléments existants en temps constant. Il existe des méthodes de dictionnaire pour effectuer ces opérations.

>>> favorites = {'book':'Orlando'}
>>> favorites
{'book': 'Orlando'}

>>> favorites['author']='Virginia Woolf'
>>> favorites
{'book': 'Orlando', 'author': 'Virginia Woolf'}

>>> favorites.pop('author')
'Virginia Woolf'
>>> favorites
{'book': 'Orlando'}

OrderedDict

Bien qu’un dictionnaire Python fournisse un mappage clé-valeur, il s’agit par nature d’une structure de données non ordonnée. Depuis Python 3.7, l’ordre d’insertion des éléments est conservé. Mais vous pouvez rendre cela plus explicite en utilisant OrderedDict depuis le module de recouvrement.

Comme indiqué, un OrderedDict conserve l’ordre des touches :

>>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first']='one'
>>> od['second']='two'
>>> od['third']='three'
>>> od
OrderedDict([('first', 'one'), ('second', 'two'), ('third', 'three')])
>>> od.keys()
odict_keys(['first', 'second', 'third'])

Defaultdict

Les erreurs de clé sont assez courantes lorsque vous travaillez avec des dictionnaires Python. Chaque fois que vous essayez d’accéder à une clé qui n’a pas été ajoutée au dictionnaire, vous rencontrez une exception KeyError.

Mais en utilisant defaultdict du module collections, vous pouvez gérer ce cas de manière native. Lorsque nous essayons d’accéder à une clé qui n’est pas présente dans le dictionnaire, la clé est ajoutée et initialisée avec les valeurs par défaut spécifiées par la fabrique par défaut.

>>> from collections import defaultdict
>>> prices = defaultdict(int)
>>> prices['carrots']
0

Piles

La pile est une dernier entré, premier sorti (LIFO) Structure de données. Nous pouvons effectuer les opérations suivantes sur une pile :

• Ajoutez des éléments en haut de la pile : pousser opération
• Supprimez les éléments du haut de la pile : populaire opération

Un exemple pour illustrer le fonctionnement des opérations push et pop de la pile :

Comment implémenter une pile à l’aide d’une liste

En Python, nous pouvons implémenter la structure de données de la pile à l’aide d’une liste Python.

Opération sur pile	Opération de liste équivalente
Pousser pour empiler le dessus	Ajouter à la fin de la liste à l’aide de la append() méthode
Sortez du haut de la pile	Supprimer et retourner le dernier élément à l’aide de la pop() méthode

L’extrait de code ci-dessous montre comment émuler le comportement d’une pile à l’aide d’une liste Python :

>>> l_stk = []
>>> l_stk.append(4)
>>> l_stk.append(3)
>>> l_stk.append(7)
>>> l_stk.append(2)
>>> l_stk.append(9)
>>> l_stk
[4, 3, 7, 2, 9]
>>> l_stk.pop()
9

Comment implémenter une pile à l’aide d’un Deque

Une autre méthode pour implémenter une pile consiste à utiliser déque depuis le module de recouvrement. Deque signifie file d’attente à double extrémité et prend en charge l’ajout et la suppression d’éléments des deux extrémités.

Pour émuler la pile, nous pouvons :

• ajouter à la fin de la deque en utilisant append()et
• supprimer le dernier élément ajouté en utilisant pop().

>>> from collections import deque
>>> stk = deque()
>>> stk.append(4)
>>> stk.append(3)
>>> stk.append(7)
>>> stk.append(2)
>>> stk.append(9)
>>> stk
deque([4, 3, 7, 2,9])
>>> stk.pop()
9

Files d’attente

La file d’attente est une premier entré, premier sorti (FIFO) Structure de données. Les éléments sont ajoutés à la fin de la file d’attente et sont supprimés du début de la file d’attente (tête de file d’attente) comme indiqué :

Nous pouvons implémenter la structure de données de la file d’attente à l’aide d’un deque :

• ajouter des éléments à la fin de la file d’attente en utilisant append()
• Utilisez le popleft() méthode pour supprimer un élément du début de la file d’attente

>>> from collections import deque
>>> q = deque()
>>> q.append(4)
>>> q.append(3)
>>> q.append(7)
>>> q.append(2)
>>> q.append(9)
>>> q.popleft()
4

Tas

Dans cette section, nous aborderons les tas binaires. Nous nous concentrerons sur les tas min.

Un tas min est un arbre binaire complet. Décomposons ce que signifie un arbre binaire complet :

• UN arbre binaire est une structure de données arborescente où chaque nœud a au plus deux nœuds enfants de sorte que chaque nœud est inférieur à son enfant.
• Le terme complet signifie que l’arborescence est complètement remplie, à l’exception peut-être du dernier niveau. Si le dernier niveau est partiellement rempli, il est rempli de gauche à droite.

Parce que chaque nœud a au plus deux nœuds enfants. Et satisfait également la propriété qu’il est inférieur à son enfant, le racine est le élément minimal dans un tas min.

Voici un exemple de tas min :

En Python, le tasq module nous aide à construire des tas et à effectuer des opérations sur le tas. Importons les fonctions requises à partir de heapq:

>>> from heapq import heapify, heappush, heappop

Si vous avez une liste ou un autre itérable, vous pouvez en construire un tas en appelant heapify():

>>> nums = [11,8,12,3,7,9,10]
>>> heapify(nums)

Vous pouvez indexer le premier élément pour vérifier qu’il s’agit de l’élément minimum :

>>> nums[0]
3

Maintenant, si vous insérez un élément dans le tas, les nœuds seront réarrangés de manière à satisfaire la propriété de tas min.

>>> heappush(nums,1)

Comme nous insérons 1 (1 < 3), nous voyons que nums[0] renvoie 1 qui est maintenant l’élément minimum (et le nœud racine).

>>> nums[0]
1

Vous pouvez supprimer des éléments du tas min en appelant le heappop() fonction comme indiqué :

>>> while nums:
...     print(heappop(nums))
...

# Output
1
3
7
8
9
10
11
12

Tas maximum en Python

Maintenant que vous connaissez les tas min, pouvez-vous deviner comment nous pouvons implémenter un tas max ?

Eh bien, nous pouvons convertir une implémentation de tas min en un tas max en multipliant chaque nombre par -1. Les nombres négatifs disposés dans un tas min sont équivalents aux nombres originaux disposés dans un tas max.

Dans l’implémentation Python, nous pouvons multiplier les éléments par -1 lors de l’ajout d’un élément au tas en utilisant heappush():

>>> maxHeap = []
>>> heappush(maxHeap,-2)
>>> heappush(maxHeap,-5)
>>> heappush(maxHeap,-7)

Le nœud racine, multiplié par -1, sera l’élément maximum.

>>> -1*maxHeap[0]
7

Lorsque vous supprimez les éléments du tas, utilisez heappop() et multipliez par -1 pour récupérer la valeur d’origine :

>>> while maxHeap:
...     print(-1*heappop(maxHeap))
...

# Output
7
5
2

Files d’attente prioritaires

Terminons la discussion en découvrant la structure de données de la file d’attente prioritaire en Python.

Nous savons : Dans une file d’attente, les éléments sont supprimés dans le même ordre dans lequel ils entrent dans la file d’attente. Mais un priorité file d’attente sert les éléments par priorité, ce qui est très utile pour des applications telles que la planification. Ainsi, à tout moment, l’élément avec la priorité la plus élevée est renvoyé.

Nous pouvons utiliser des clés pour définir la priorité. Ici, nous utiliserons des poids numériques pour les clés.

Comment implémenter des files d’attente prioritaires à l’aide de Heapq

Voici la mise en œuvre de la file d’attente prioritaire à l’aide heapq et liste Python :

>>> from heapq import heappush,heappop
>>> pq = []
>>> heappush(pq,(2,'write'))
>>> heappush(pq,(1,'read'))
>>> heappush(pq,(3,'code'))
>>> while pq:
...     print(heappop(pq))
...

Lors de la suppression d’éléments, la file d’attente sert l’élément ayant la priorité la plus élevée (1,'read') d’abord, suivi de (2,'write') et puis (3,'code').

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Comment implémenter des files d’attente prioritaires à l’aide de PriorityQueue

Pour implémenter une file d’attente prioritaire, nous pouvons également utiliser le PriorityQueue classe de la file d’attente module. Cela utilise également le tas en interne.

Voici l’implémentation équivalente de la file d’attente prioritaire en utilisant PriorityQueue:

>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>> pq.put((2,'write'))
>>> pq.put((1,'read'))
>>> pq.put((3,'code'))
>>> pq
<queue.PriorityQueue object at 0x00BDE730>
>>> while not pq.empty():
...     print(pq.get())
...

# Output
(1, 'read')
(2, 'write')
(3, 'code')

Résumé

Dans ce didacticiel, vous avez découvert les différentes structures de données intégrées à Python. Nous avons également passé en revue les différentes opérations prises en charge par ces structures de données et les méthodes intégrées pour faire de même.

Ensuite, nous avons passé en revue d’autres structures de données telles que les piles, les files d’attente et les files d’attente prioritaires, ainsi que leur implémentation Python à l’aide des fonctionnalités du module collections.

Ensuite, consultez la liste des projets Python adaptés aux débutants.