Listas Secuenciales

Publicado por rogikato / en 11:32 / / 0 comentarios

En una lista secuencial, el sucesor de un elemento ocupa la posición física subsecuente de este elemento. Una de las formas más comunes de implementar una lista secuencial es utilizando ARRAY. En un array asociamos a cada elemento un índice (lo denominamos elemento a(i)). De esta forma, estamos almacenando el elemento a(i) e a(i+1) en las posiciones consecutivas i e i+1

Las principales ventajas de utilizar un array son:

1. Rápido acesso a los elementos.
2. Facilidad en modificar información.

Los elementos del array pueden ser accesados en tiempo constante, por ejemplo en C el elemento que está en la posición i de un array a pode ser recuperado utilizando a[i]. Las principales desventajas son:

1. Definición previa del tamaño de un array.
2. Dificultad para insertar (y eliminar) un elemento entre dos otros ya existentes.

En la definición de un array necesitamos especificar el número máximo de elementos que serán almacenados.

Suponga que querramos inserir un nuevo elemento x en una posición i ya ocupada de un vector
Para realizar esta tarea tendremos que mover los elementos a(i+1), a(i+2)...a(k)  para las posiciones i+1, i+2, i+3...,i+k+1 respectivamente. Note que en el peor de los casos (insertar en la primera posición) esta operación lleva un tiempo de O(n).