Array
Una serie de elementos guardados uno tras otro en memoria y accesibles por su posición.
Al ser contiguo, calcular dónde está el elemento n es una simple multiplicación, de modo que el acceso cuesta lo mismo sea cual sea la posición. Esa contigüidad también favorece a la caché del procesador: recorrer un array de principio a fin es de las operaciones más rápidas que existen.
El precio es la rigidez. Insertar en medio obliga a desplazar todo lo que sigue, y crecer suele requerir reservar un bloque nuevo y copiarlo entero. Casi todos los lenguajes empiezan a contar en cero, porque el índice es realmente un desplazamiento desde el inicio.