Structures de données

Il existe de nombreuses structures de données qui permettent de résoudre les problèmes fréquemment rencontrés en programmation. En plus de stocker des données, elles permettent de les organiser et de les manipuler facilement.

Une structure de données est une implémentation d’un type de données abstrait. En général, plusieurs implémentations existent pour une même structure de données. Chaque implémentation possède ses forces et faiblesses.

Complexité algorithmique#

Avant de plonger dans les différentes structures de données, il est essentiel de comprendre le concept de complexité algorithmique et la notation Big O. Cela nous aide à analyser l'efficacité des algorithmes et à choisir les structures de données les plus adaptées en fonction des opérations que nous devons effectuer.

Notation Big O#

La notation Big O est une façon de décrire la complexité temporelle ou spatiale d'un algorithme en fonction de la taille de l'entrée. Elle exprime le pire cas possible en termes de performance, en omettant les constantes multiplicatives et les termes de moindre importance.

Par exemple :

• O(1) : Temps constant, l'opération prend le même temps quelle que soit la taille de l'entrée.
• O(log n) : Temps logarithmique, le temps d'exécution augmente logarithmiquement avec la taille de l'entrée.
• O(n) : Temps linéaire, le temps d'exécution augmente proportionnellement à la taille de l'entrée.
• O(n log n) : Temps quasi-linéaire, commun pour les algorithmes de tri efficaces.
• O(n²) : Temps quadratique, le temps d'exécution augmente proportionnellement au carré de la taille de l'entrée.

Calcul de la complexité#

Pour déterminer la complexité d'un algorithme, on analyse le nombre d'opérations élémentaires qu'il effectue en fonction de la taille de l'entrée.

Exemples#

1. Boucle simple

for ($i = 0; $i < $n; $i++) { 
    // opération en temps constant 
}

Cette boucle s'exécute n fois, et à chaque itération, elle effectue une opération en temps constant. La complexité est donc O(n).

2. Boucle imbriquée

for ($i = 0; $i < $n; $i++) { 
    for ($j = 0; $j < $n; $j++) { 
        // opération en temps constant 
    } 
}

Ici, la boucle interne s'exécute n fois pour chaque itération de la boucle externe, ce qui donne un total de n * n = n^2 opérations. La complexité est donc O(n²).

3. Recherche dichotomique

function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        if ($array[$mid] == $target) {
            return $mid;
        } elseif ($array[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    return -1;
}

La recherche dichotomique divise la taille du problème par deux à chaque itération. La complexité est donc O(log n).

Projet sur GitHub#

1. Forkez puis clonez le projet GitHub fourni pour réaliser les exercices. Le projet contient la structure des classes nécessaires ainsi qu'un dossier de tests. (Template à forker)

2. Installez le projet en exécutant la commande composer install dans le dossier que vous venez de cloner.

3. Implémentez les méthodes des classes pour passer les tests fournis.

Paire#

Une Paire est une structure de données simple qui regroupe deux éléments. Ces éléments peuvent être de n'importe quel type et ils n'ont pas besoin d'être du même type entre eux.

Utilisation#

Une Paire est souvent utilisée pour regrouper deux éléments qui sont étroitement liés. Par exemple, si vous voulez associer un nom à une valeur, vous pouvez utiliser une Paire.

Forces#

• Simplicité : Une Paire est une structure de données très simple qui ne nécessite pas de méthodes compliquées.

• Polyvalence : Les éléments d'une Paire peuvent être de n'importe quel type, ce qui rend cette structure de données très flexible.

Faiblesses#

• Limité à deux éléments : Une Paire ne peut contenir que deux éléments. Si vous avez besoin de regrouper plus de deux éléments, vous devrez utiliser une autre structure de données, comme une Liste ou un Tableau.

Set#

Un Set est une structure de données qui stocke des éléments uniques, c'est-à-dire sans doublons.

Utilisation#

Un Set est souvent utilisé lorsque vous voulez stocker une collection d'éléments, mais que vous ne voulez pas de doublons.

Forces#

• Pas de doublons : Un Set garantit qu'il n'y a pas de doublons, ce qui peut simplifier beaucoup de problèmes.

• Opérations efficaces : Les opérations comme l'ajout, la suppression et la recherche d'éléments dans un Set sont généralement très efficaces, mais leur performance dépend de l'implémentation du Set. Par exemple, un Set implémenté avec une table de hachage offre des opérations en temps O(1) en moyenne, tandis qu'un Set implémenté avec un arbre binaire de recherche offre des opérations en temps O(log n).

Faiblesses#

• Pas d'ordre : Les éléments dans un Set ne sont généralement pas ordonnés. Si vous avez besoin d'un ordre spécifique, vous devrez utiliser une autre structure de données.

Complexité#

Opération	Complexité en temps (Table de hachage)	Complexité en temps (Arbre binaire)
Ajout	O(1) en moyenne	O(log n)
Suppression	O(1) en moyenne	O(log n)
Recherche	O(1) en moyenne	O(log n)
Parcours	O(n)	O(n)

Listes#

Dans le monde de la programmation, une liste est une structure de données qui contient une série d'éléments. Les éléments d'une liste peuvent être de n'importe quel type : nombres, chaînes, objets, etc. Les listes sont très utiles pour stocker des données qui doivent être accédées de manière séquentielle ou qui doivent être organisées d'une certaine manière.

Dans ce chapitre, nous allons explorer différentes implémentations de listes : ArrayList, LinkedList et Collection. Pour chacune de ces structures de données, nous allons définir ce qu'elles sont, comment les utiliser, leurs points forts et leurs points faibles. De plus, vous aurez l'occasion de mettre en pratique ce que vous avez appris grâce à des exercices pratiques.

Avant de plonger dans les détails de chaque type de liste, examinons d'abord l'interface que vous allez implémenter.

<?php

declare(strict_types=1);

namespace Opmvpc\StructuresDonnees\Lists;

interface ListInterface
{
    public function __toString(): string;

    public function push(mixed $element): void;

    public function get(int $index): mixed;

    public function set(int $index, mixed $element): void;

    public function clear(): void;

    public function includes(mixed $element): bool;

    public function isEmpty(): bool;

    public function indexOf(mixed $element): int;

    public function remove(int $index): void;

    public function size(): int;

    public function toArray(): array;
}

Cette interface définit les méthodes que chaque type de liste doit implémenter.

ArrayList#

L'ArrayList est une implémentation de la liste qui utilise un tableau pour stocker les éléments. Un tableau est une structure de données qui stocke une collection d'éléments dans un emplacement de mémoire contigu. Chaque élément peut être identifié par un index, qui représente sa position dans le tableau.

Utilisation#

• Ajout d'un élément : Lorsqu'un élément est ajouté à une ArrayList, il est placé à la fin du tableau. Si le tableau est plein, il est redimensionné pour accueillir plus d'éléments.
• Suppression d'un élément : Lorsqu'un élément est supprimé, les éléments suivants sont décalés pour combler l'espace vide.

Forces#

• Accès rapide aux éléments : L'accès à un élément par son index se fait en temps constant O(1).
• Taille dynamique : La ArrayList peut croître dynamiquement en redimensionnant le tableau interne.

Faiblesses#

• Coût des insertions/suppressions au milieu : Les opérations d'insertion ou de suppression au milieu de la liste nécessitent le décalage des éléments, ce qui a une complexité en temps O(n).
• Coût du redimensionnement : Lors du redimensionnement, un nouveau tableau est créé et les éléments sont copiés, ce qui peut être coûteux en temps O(n).

Complexité#

Opération	Complexité en temps
Accès par index	O(1)
Ajout à la fin	O(1)*
Insertion/Suppression	O(n)
Recherche d'un élément	O(n)
Taille	O(1)

* O(1) en temps amorti. Le redimensionnement peut entraîner un coût O(n), mais il se produit rarement.

Exercice sur ArrayList#

Objectif : Implémentez une ArrayList en utilisant l'interface ListInterface fournie.

Instructions :

• Implémentez toutes les méthodes de l'interface.
• Gérez correctement le redimensionnement du tableau interne.
• Assurez-vous que votre implémentation passe tous les tests fournis.

LinkedList#

La LinkedList est une implémentation de la liste qui utilise des nœuds chaînés. Chaque nœud contient un élément et une référence au nœud suivant.

Utilisation#

• Ajout d'un élément : L'ajout au début de la liste est rapide (O(1)). Pour ajouter à une position spécifique, il faut parcourir la liste jusqu'à cette position.
• Suppression d'un élément : Similaire à l'ajout, la suppression au début est rapide, mais pour supprimer à une position spécifique, il faut parcourir la liste.

Forces#

• Insertion/Suppression efficaces en début de liste : Ces opérations se font en temps constant O(1).
• Pas de redimensionnement nécessaire : La liste peut croître dynamiquement sans redimensionnement.

Faiblesses#

• Accès lent aux éléments : L'accès à un élément par index nécessite de parcourir la liste (O(n)).
• Surcoût mémoire : Chaque nœud nécessite de la mémoire supplémentaire pour stocker la référence au nœud suivant.

Complexité#

Opération	Complexité en temps
Accès par index	O(n)
Ajout/Suppression en tête	O(1)
Insertion/Suppression	O(n)
Recherche d'un élément	O(n)
Taille	O(1)

Exercice sur LinkedList#

Objectif : Implémentez une LinkedList en utilisant l'interface ListInterface fournie.

Instructions :

• Implémentez toutes les méthodes de l'interface.
• Gérez correctement les nœuds lors des insertions et suppressions.
• Assurez-vous que votre implémentation passe tous les tests fournis.

Collection#

Une Collection étend les fonctionnalités d'une ArrayList en offrant des méthodes de manipulation avancées.

<?php

declare(strict_types=1);

namespace Opmvpc\StructuresDonnees\Lists;

interface CollectionInterface extends ListInterface
{
    public function map(callable $callback): CollectionInterface;

    public function filter(callable $callback): CollectionInterface;

    public function reduce(callable $callback, mixed $initial = null): mixed;

    public function forEach(callable $callback): void;

    public function some(callable $callback): bool;

    public function every(callable $callback): bool;

    public function find(callable $callback): mixed;

    public function join(string $separator = ','): string;

    public function reverse(): CollectionInterface;

    public function sort(callable $callback): CollectionInterface;

    public function concat(...$collections): CollectionInterface;

    public function fill(mixed $value = null, int $start = 0, int $end = null): CollectionInterface;
}

Utilisation#

• Manipulation fonctionnelle : Les méthodes comme map, filter, reduce permettent d'appliquer des transformations sur les éléments.

Forces#

• Flexibilité : Offre de puissantes méthodes pour manipuler les données de manière expressive.
• Chaînage : Les méthodes retournent souvent une nouvelle Collection, permettant le chaînage.

Faiblesses#

• Coût en performance : Certaines opérations peuvent être coûteuses en temps et en mémoire, surtout sur de grandes collections.

Complexité#

La complexité dépend de chaque méthode, mais la plupart des méthodes comme map, filter, reduce ont une complexité en temps O(n).

Exercice sur Collection#

Objectif : Implémentez une Collection qui étend votre ArrayList et implémente CollectionInterface.

Instructions :

• Implémentez toutes les méthodes de l'interface.
• Assurez-vous de respecter les spécifications de chaque méthode.
• Testez votre implémentation avec les tests fournis.

Stacks (Piles)#

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out).

<?php

namespace Opmvpc\StructuresDonnees\Stacks;

interface StackInterface
{
    public function __toString(): string;

    public function isEmpty(): bool;

    public function push(mixed $item): StackInterface;

    public function pop(): mixed;

    public function top(): mixed;

    public function clear(): void;

    public function toArray(): array;
}

ArrayStack#

Implémentation d'une pile utilisant un tableau.

Utilisation#

• push : Ajoute un élément au sommet de la pile.
• pop : Retire et renvoie l'élément au sommet.
• top : Renvoie l'élément au sommet sans le retirer.

Forces#

• Opérations rapides : push, pop, top en O(1) en moyenne.

• Utilisation efficace de la mémoire : Les données sont stockées de manière contiguë.

Faiblesses#

• Redimensionnement : Peut nécessiter un redimensionnement du tableau.

Complexité#

Opération	Complexité en temps
push	O(1)*
pop	O(1)
top	O(1)
isEmpty	O(1)

* O(1) en temps amorti.

LinkedStack#

Implémentation d'une pile utilisant une liste chaînée.

Forces#

• Opérations toujours en O(1) : Pas de redimensionnement nécessaire.

Faiblesses#

• Surcoût mémoire : Chaque élément nécessite de la mémoire supplémentaire.

Complexité#

Identique à l'ArrayStack.

Exercice sur les Stacks#

Objectif : Implémentez une ArrayStack et une LinkedStack selon StackInterface.

Instructions :

• Respectez le principe LIFO.
• Implémentez toutes les méthodes.
• Testez vos implémentations.

Files (Queues)#

Une file est une structure de données qui suit le principe FIFO (First In, First Out).

<?php

namespace Opmvpc\StructuresDonnees\Queues;

interface QueueInterface
{
    public function __toString(): string;

    public function isEmpty(): bool;

    public function enqueue(mixed $item): QueueInterface;

    public function dequeue(): mixed;

    public function front(): mixed;

    public function clear(): void;

    public function toArray(): array;
}

Utilisation#

• enqueue : Ajoute un élément à la fin de la file.
• dequeue : Retire et renvoie l'élément au début.
• front : Renvoie l'élément au début sans le retirer.

Forces#

• Opérations en O(1) : Avec une implémentation appropriée (liste chaînée ou tableau circulaire).

Faiblesses#

• Complexité de l'implémentation : Nécessite une gestion soignée pour maintenir les performances.

Exercice sur les Files#

Objectif : Implémentez une file respectant QueueInterface.

Instructions :

• Choisissez une implémentation efficace.
• Implémentez toutes les méthodes.
• Créez un jeu de tests.

Arbres binaires de recherche#

Un arbre binaire de recherche (ABR) est une structure de données hiérarchique.

<?php

declare(strict_types=1);

namespace Opmvpc\StructuresDonnees\Trees;

interface TreeInterface
{
    public function __toString(): string;

    public function isEmpty(): bool;

    public function insert(int|string $key, mixed $element): TreeInterface;

    public function search(int|string $key): mixed;

    public function min(): mixed;

    public function max(): mixed;

    public function toArray(): array;
}

Utilisation#

• Recherche efficace : En exploitant la propriété d'ordre de l'arbre.

Forces#

• Opérations en O(log n) : Pour un arbre équilibré.

Faiblesses#

• Risque de déséquilibre : Peut dégrader les performances à O(n).

Exercice sur les Arbres binaires de recherche#

Objectif : Implémentez un ABR respectant TreeInterface.

Instructions :

• Implémentez les méthodes d'insertion, de recherche, min, max.
• Gérez les cas où l'arbre est vide.
• Testez votre implémentation.

HashMap#

Une HashMap associe des clés à des valeurs pour un accès rapide.

Utilisation#

• Associations clés-valeurs : Permet un accès en temps constant O(1) en moyenne.

Forces#

• Accès rapide : Efficace pour de grandes quantités de données.

Faiblesses#

• Gestion des collisions : Les collisions peuvent affecter les performances.

• Dépendance à la fonction de hachage : Une mauvaise fonction peut entraîner une distribution inégale.

Complexité#

Opération	Complexité en temps
Insertion	O(1) en moyenne
Suppression	O(1) en moyenne
Recherche	O(1) en moyenne

Conclusion#

Les structures de données sont fondamentales en programmation et permettent de résoudre efficacement de nombreux problèmes. Comprendre leurs forces, faiblesses et complexités est essentiel pour faire les choix appropriés lors du développement d'applications.

Tableau récapitulatif des complexités#

Structure de données	Accès	Recherche	Insertion	Suppression
ArrayList	O(1)	O(n)	O(n)	O(n)
LinkedList	O(n)	O(n)	O(n)	O(n)
Stack	O(n)	O(n)	O(1)	O(1)
Queue	O(n)	O(n)	O(1)	O(1)
HashMap	N/A	O(1)	O(1)	O(1)
Arbre binaire	O(log n)	O(log n)	O(log n)	O(log n)