Estructuras de Datos Dinámicas y Estáticas: Listas Lineales Contiguas y Algoritmos Fundamentales

Estructuras Dinámicas de Datos

Las estructuras dinámicas de datos son aquellas que crecen o decrecen a medida que se ejecuta un programa. Una estructura dinámica de datos es una colección de elementos, llamados nodos, que normalmente son registros.

A diferencia de un array, que contiene espacio predefinido para un número fijo de elementos, las estructuras dinámicas se utilizan para el almacenamiento de datos del mundo real que cambian constantemente. Un ejemplo típico, que a menudo se gestiona como una estructura estática, es la lista de pasajeros de una línea aérea. Si esta lista se mantuviera en orden alfabético en un array, sería necesario hacer espacio para insertar un nuevo pasajero por orden alfabético. Esto requeriría utilizar un bucle para copiar los datos del registro de cada pasajero al siguiente elemento del array, lo cual es ineficiente.

Estructuras Estáticas de Datos

Una estructura estática de datos es aquella cuya estructura se especifica en el momento en que se escribe el programa y no puede ser modificada por este. Los valores de sus diferentes elementos pueden variar, pero no su estructura, ya que esta es fija.

En contraste, una estructura dinámica de datos puede modificar su estructura mediante el programa, pudiendo ampliar o limitar su tamaño mientras se ejecuta.

Listas Lineales

Una lista lineal es un conjunto de elementos de un tipo dado que pueden variar en número. En ella, cada elemento tiene un único predecesor y un único sucesor (o siguiente), excepto el primero y el último de la lista. Esta es una definición muy general que incluye, por ejemplo, los ficheros y los vectores.

Los elementos de una lista lineal se almacenan normalmente de forma contigua, un elemento detrás de otro, en posiciones consecutivas de la memoria. Cuando se almacenan en la memoria principal de una computadora, ocupan posiciones sucesivas; si se almacenan en cinta magnética, los elementos sucesivos se presentan en sucesión en la cinta.

Operaciones Comunes con Listas Lineales Contiguas

• Insertar, eliminar o localizar un elemento.
• Determinar el tamaño (número de elementos) de la lista.
• Recorrer la lista para localizar un determinado elemento.
• Clasificar los elementos de la lista en orden ascendente o descendente.
• Unir dos o más listas en una sola.
• Dividir una lista en varias sublistas.
• Copiar la lista.
• Borrar la lista completa.

Una lista lineal contigua se almacena en la memoria de la computadora en posiciones sucesivas y adyacentes, y se procesa como un array unidimensional.

Acceso a un Elemento en una Lista Contigua

Ejemplo: Leer el elemento j-ésimo de una lista P

El algoritmo requiere conocer el número de elementos de la lista (su longitud, L). Los pasos a seguir son:

1. Conocer la longitud de la lista (L).
2. Si L = 0, visualizar «Error: lista vacía».
3. Si no, comprobar si el elemento j-ésimo está dentro del rango permitido de elementos (1 <= j <= L).
   • En este caso, asignar el valor del elemento P[j] a una variable B.
   • Si el elemento j-ésimo no está dentro del rango, visualizar un mensaje de error «Elemento solicitado no existe en la lista».
4. Fin.

El pseudocódigo correspondiente sería:

Procedimiento acceso (E lista: p; S elementolista: B; E entero: L, J)
Inicio
    Si L = 0 entonces
        Escribir ("Lista vacía")
    Si_no
        Si (J >= 1) y (J <= L) entonces
            B <- P[J]
        Si_no
            Escribir ("Error: elemento no existente")
        Fin_si
    Fin_si
Fin

Eliminación de un Elemento en una Lista Contigua

Algoritmo para borrar un elemento j de la lista P

Variables:

• L: Longitud actual de la lista.
• J: Posición del elemento a borrar.
• I: Subíndice para recorrer el array P.
• P: La lista (array).

Las operaciones necesarias son:

1. Comprobar si la lista está vacía.
2. Comprobar si el valor de J está en el rango válido del subíndice de la lista (1 <= J <= L).
3. En caso de que J sea correcto, mover los elementos j+1, j+2, ..., L a las posiciones j, j+1, ..., L-1, respectivamente. Con esto, se habrá "borrado" el antiguo elemento en la posición j.
4. Decrementar en uno el valor de la variable L, ya que la lista contendrá ahora L-1 elementos.

El algoritmo correspondiente sería:

Inicio
    Si L = 0 entonces
        Escribir ('Lista vacía')
    Si_no
        Leer (J)
        Si (J >= 1) y (J <= L) entonces
            Desde I <- J hasta L-1 hacer
                P[I] <- P[I+1]
            Fin_desde
            L <- L-1
        Si_no
            Escribir ('Error: Elemento no existe')
        Fin_si
    Fin_si
Fin

Características de las Listas Contiguas

Una lista contigua es aquella en la que los elementos son adyacentes en la memoria o en un soporte direccionable. Este tipo de lista tiene unos límites izquierdo y derecho (o inferior/superior) que, en su implementación básica como array, no pueden ser fácilmente "rebajados" o expandidos más allá de su capacidad inicial sin una reasignación de memoria, lo que puede implicar copiar todos los elementos.