Séquences

Une séquence est un conteneur dont les éléments sont organisés sous forme de suite. Il existe deux grandes catégories de séquences : les listes et les vecteurs. Il y a deux différences principales entre les deux.

Premièrement, la liste permet une insertion ou une suppression d'un élément n'importe où dans la liste en $O(1)$ à condition qu'un pointeur existe sur l'élément précédent. Ceci n'est pas le cas d'un vecteur.

Deuxièmement, le vecteur permet un accès direct en $O(1)$ à n'importe quel élément dont on connaît la position. Ce n'est pas le cas d'une liste, qui nécessite un parcours total depuis le début (ou la fin si la liste est doublement chaînée), ce qui nécessite un temps $O(n)$.

Si un vecteur est utilisé pour stocker des éléments ordonnés, il est possible de trouver un élément avec une clé donnée en $O(\texttt{log} n)$ avec une technique appelée recherche par dichotomie (en Anglais : binary search). Cette technique n'est pas possible avec une liste, car elle nécessite un accès direct à tous les éléments de la séquence. Pour trouver un élément dans une liste, il faut en général parcourir la liste entière, ce qui nécessite $O(n)$.

Un vecteur est plus économique en mémoire. Il nécessite uniquement l'espace d'un pointeur pour chaque élément, plus l'en-tête du vecteur proprement dit, alors qu'une liste nécessite pour chaque cellule le pointeur sur l'élément et le pointeur sur l'élément suivant, plus éventuellement un en-tête contenant des informations de taille et de type.