Structures de données linéaires pour le Frontend
Les structures de données linéaires organisent les éléments en une séquence. Chaque élément possède un prédécesseur et un successeur unique.
Arrays Les tableaux (Arrays) sont l'outil principal en JavaScript. Ils utilisent une mémoire contiguë. Cela vous permet d'accéder instantanément à n'importe quel élément par son index.
- push : Ajoute un élément à la fin.
- unshift : Ajoute un élément au début. C'est lent car tous les autres éléments doivent se déplacer d'une position vers la droite.
- splice : Ajoute ou supprime des éléments à n'importe quelle position. Cette méthode modifie le tableau d'origine. Ce n'est pas une fonction pure.
Note : Lorsqu'un tableau devient trop grand, JavaScript doit allouer un bloc de mémoire plus important et tout copier. Cela impacte les performances.
Stacks Une pile (Stack) suit la règle LIFO : Last In, First Out (Dernier entré, premier sorti). Imaginez une pile d'assiettes. Vous n'ajoutez ou ne retirez des éléments que par le haut.
- push : Ajoute au sommet.
- pop : Retire du sommet.
- peek : Consulte l'élément au sommet sans le retirer.
Queues Une file d'attente (Queue) suit la règle FIFO : First In, First Out (Premier entré, premier sorti). Imaginez une file d'attente dans un magasin.
- push : Ajoute à la fin.
- shift : Retire du début.
Warning : L'utilisation de shift sur un tableau est lente pour les grands ensembles de données. Chaque élément doit se déplacer vers la gauche pour combler le vide. Pour des données à haut volume, utilisez plutôt une liste chaînée.
Linked Lists Une liste chaînée (Linked List) est composée de nœuds. Chaque nœud contient des données et un pointeur vers le nœud suivant.
- Avantages : L'ajout ou la suppression de nœuds est rapide une fois l'emplacement trouvé. Vous ne changez que les pointeurs.
- Inconvénients : Vous ne pouvez pas sauter directement à un index. Vous devez partir de la tête et suivre les pointeurs un par un. C'est lent.
Comparison Summary:
- Arrays : Idéal pour les lectures fréquentes et les petites données. L'accès est en O(1).
- Linked Lists : Idéal pour les écritures fréquentes et les grandes données. L'insertion est en O(1) si vous possédez le nœud.
Pro Tips for JavaScript:
- Ne mélangez pas les types de données dans un tableau. Maintenir des types uniformes aide le moteur à utiliser une mémoire contiguë.
- Utilisez toujours une fonction de comparaison lors du tri de nombres.
[10, 2].sort()donne[10, 2]car il trie comme des chaînes de caractères. - N'oubliez pas que la plupart des méthodes natives de tableau modifient le tableau d'origine.