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 à 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 à 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
.
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
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
.
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.