AnteriorPosterior

9.4. Listas enlazadas no ordenadas

  Curso: Programación en Pascal (v5), por Nacho Cabanes

9.4. Listas enlazadas no ordenadas

Las pilas y las colas son estructuras sencillas: fáciles de entender y (aun más interesante para un principiante) fáciles de implementar. Pero, a cambio, tampoco son demasiado útiles: en un caso general, eso de tener que obtener siempre los datos desde un único extremo es una limitación importante, y lo es más aún eso de que para ver el segundo dato sea necesario extraer (de forma destructiva) el primero.

Por eso vamos a ver una estructura de datos mas general, más versátil, pero también más difícil de manejar: las listas enlazadas.

En una "lista simple" habrá una serie de elementos, cada uno de los cuales estará enlazado al siguiente. Podremos acceder a cualquier elemento, a condición de recorrer todos los anteriores. Eso hará que algunas operaciones sean más lentas que en una implementación estática, como la lectura de elementos que están cerca del fila. A cambio, otras operaciones serán más rápidas, como la inserción y el borrado, ya que no habrá que "mover" el resto de elementos. Por supuesto, la gran ventaja es que ahora la capacidad estará limitada sólo por la memoria disponible en nuestro equipo.

Al igual que hicimos con las pilas y las colas, crearemos una lista estática como primer acercamiento. Esta lista se apoyará internamente en un array, de modo que su tamaño será limitado y desperdiciará espacio, pero sentará las bases para crear poco después una lista verdaderamente dinámica. Nuestra primera lista no estará ordenada; más adelante veremos cómo crear una lista en la que los nuevos elementos se ordenen automáticamente cuando son insertados.

Las operaciones que permitiremos en esta lista simple no ordenada serán: añadir un dato en una cierta posición, obtener un dato de una cierta posición, borrar un dato de una cierta posición. Cuando añadimos un dato en una posición, se moverán hacia "el final" los que ya existieran a partir de esa posición; de igual modo, cuando borremos un dato, los siguientes se desplazarán hacia el principio.

¿Qué deberemos hacer en los casos "incorrectos", por ejemplo cuando haya 3 datos y se nos pida añadir en la posición 5? Por ahora no vamos a comprobar esos tipos de errores, de modo que el programa fallará (igual que si intentamos guardar en la posición 100 de un array de 20 elementos, así que tampoco es algo especialmente desconcertante).

La versión estática podría ser así:

(* LISTA1.PAS, Ejemplo de lista estatica      *)
(* No incluye ninguna comprobacion de errores *)
(* Parte de CUPAS5, por Nacho Cabanes         *) 
 
program listaEstatica;
 
var
    datos: array[1..10] of integer;
    cantidad: integer;
 
procedure InicializarLista;
begin
    cantidad := 0;
end;
 
procedure Anadir(posicion: integer; nuevoDato: integer);
var 
    i: integer;
begin
    { Si la posicion no es la ultima, hay que desplazar todos }
    if posicion <= cantidad then
        for i := cantidad+1 downto posicion+1 do
            datos[i] := datos[i-1];
    { Y finalmente guardamos }
    datos[posicion] := nuevoDato;
    { Y tenemos un dato mas }
    cantidad := cantidad + 1;
end;    
 
 
function Obtener(posicion: integer): integer;
begin
    Obtener := datos[posicion];
end;
 
procedure Borrar(posicion: integer);
var 
    i: integer;
begin
    for i := posicion to cantidad do
        datos[i] := datos[i+1];
    cantidad := cantidad - 1;
end;
 
 
function CantidadDatos: integer;
begin
    CantidadDatos := cantidad;
end;
 
{ --- Programa de prueba --- }
 
var
    i, n: integer;
 
begin
    InicializarLista;
    WriteLn('Guardando 3 y 2...');
    Anadir(1, 3);
    Anadir(2, 2);
    WriteLn('Los datos por ahora son:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Ahora comenzamos con 5...');
    Anadir(1, 5);
    WriteLn('Los datos en orden eran:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('E incluimos un 6 en segunda posicion...');
    Anadir(2, 6);
    WriteLn('Y ahora son:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Y al reves:');
    for i := CantidadDatos downto 1 do
        WriteLn( Obtener(i) );
 
    WriteLn('Vamos a borrar el segundo dato...');
    Borrar(2);
    WriteLn('Ahora tenemos:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
 
    WriteLn('Ahora introduce nuevos datos, 0 para terminar...');
    repeat
        Write('Dato? ');
        ReadLn( n );
        if n <> 0 then
            Anadir(CantidadDatos+1, n);
    until n = 0;
 
    WriteLn('Ahora los datos en orden eran:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Y al reves:');
    for i := CantidadDatos downto 1 do
        WriteLn( Obtener(i) );
end.
 

La versión dinámica, reservando memoria en el momento en que sea necesario, es un poco más compleja:

  • Para obtener el elemento número "n", haremos "n-1" saltos a partir de la posición inicial.
  • Para borrar el elemento "n", deberemos enlazar el "n-1" con el "n+1" y finalmente liberar la memoria que ocupaba el nodo de la posición "n".
  • Para añadir en la posición "n", deberemos crear un nuevo nodo, enlazar el "n-1" con él, y enlazar el nuevo nodo con el "n+1".
  • Además, tanto el "borrar" como el "añadir" tienen un caso especial: si realizamos la operación sobre el primer elemento de la lista.

La implementación real podría ser algo como...

(* LISTA2.PAS, Ejemplo de lista dinamica      *)
(* No incluye ninguna comprobacion de errores *)
(* Parte de CUPAS5, por Nacho Cabanes         *) 
 
program listaDinamica;
 
type
    puntero = ^ nodo;
 
    nodo = record
        dato: integer;
        siguiente:  puntero
    end; 
 
var
    comienzoLista: puntero;
    contadorDeDatos: integer;
 
procedure InicializarLista;
begin
    comienzoLista := nil;
    contadorDeDatos := 0;
end;
 
 
procedure Anadir(posicion: integer; nuevoDato: integer);
var 
    punteroActual: puntero;
    nuevoNodo: puntero;
    siguienteNodo: puntero;
    i: integer;
begin
    { Reservamos espacio para el nuevo nodo }
    new(nuevoNodo);
    nuevoNodo^.dato := nuevoDato;
 
    { Caso facil, al principio }
    if posicion = 1 then
        begin
        nuevoNodo^.siguiente := comienzoLista;
        comienzoLista := nuevoNodo;
        end
    { Si es mas adelante, hay que recorrer }
    else
        begin
        punteroActual := comienzoLista;
        { "Saltamos" tantas veces como corresponda para llegar al anterior }
        for i := 1 to posicion-2 do
            punteroActual := punteroActual^.siguiente;
        { Memorizamos el enlace al siguiente }
        siguienteNodo := punteroActual^.siguiente;
        { Enlazamos el anterior con el nuevo }
        punteroActual^.siguiente := nuevoNodo;
        { Y el nuevo con el que antes era el siguiente }
        nuevoNodo^.siguiente := siguienteNodo;
        end;
    contadorDeDatos := contadorDeDatos + 1;
end;    
 
 
function Obtener(posicion: integer): integer;
var
    punteroActual: puntero;
    i: integer;
begin
    punteroActual := comienzoLista;
    { "Saltamos" tantas veces como corresponda }
    for i := 1 to posicion-1 do
        punteroActual := punteroActual^.siguiente;
    { Y devolvemos el valor de esa posición }
    Obtener := punteroActual^.dato;
end;
 
procedure Borrar(posicion: integer);
var 
    punteroActual: puntero;
    siguienteNodo: puntero;
    nodoABorrar: puntero;
    i: integer;
begin
    { Caso facil, al principio }
    if posicion = 1 then
        begin
        nodoABorrar := comienzoLista;
        comienzoLista := nodoABorrar;
        end
    { Si es mas adelante, hay que recorrer }
    else
        begin
        punteroActual := comienzoLista;
        { "Saltamos" tantas veces como corresponda para llegar al anterior }
        for i := 1 to posicion-2 do
            punteroActual := punteroActual^.siguiente;
        { Memorizamos el enlace al siguiente }
        siguienteNodo := punteroActual^.siguiente;
        { Enlazamos el anterior con el nuevo }
        punteroActual^.siguiente := siguienteNodo^.siguiente;
        { Y el nuevo con el que antes era el siguiente }
        nodoABorrar := siguienteNodo;
        end;
    contadorDeDatos := contadorDeDatos - 1;
    dispose(nodoABorrar);
end;
 
 
function CantidadDatos: integer;
begin
    CantidadDatos := contadorDeDatos;
end;
 
{ --- Programa de prueba --- }
 
var
    i, n: integer;
 
begin
    InicializarLista;
    WriteLn('Guardando 3 y 2...');
    Anadir(1, 3);
    Anadir(2, 2);
    WriteLn('Los datos por ahora son:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Ahora comenzamos con 5...');
    Anadir(1, 5);
    WriteLn('Los datos en orden eran:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('E incluimos un 6 en segunda posicion...');
    Anadir(2, 6);
    WriteLn('Y ahora son:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Y al reves:');
    for i := CantidadDatos downto 1 do
        WriteLn( Obtener(i) );
 
    WriteLn('Vamos a borrar el segundo dato...');
    Borrar(2);
    WriteLn('Ahora tenemos:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
 
    WriteLn('Ahora introduce nuevos datos, 0 para terminar...');
    repeat
        Write('Dato? ');
        ReadLn( n );
        if n <> 0 then
            Anadir(CantidadDatos+1, n);
    until n = 0;
 
    WriteLn('Ahora los datos en orden eran:');
    for i := 1 to CantidadDatos do
        WriteLn( Obtener(i) );
    WriteLn('Y al reves:');
    for i := CantidadDatos downto 1 do
        WriteLn( Obtener(i) );
end.
 

Ejercicio propuesto 9.4.1: Crea un programa que permita guardar una lista de números reales. El usuario introducirá tantos datos como desee (usando 99999 para terminar), y en ese momento se le mostrará la media de los valores, después todos los que están por encima de esa media (en una misma línea, separados por espacios en blanco) y finalmente todos los que están por debajo de esa media (en una nueva línea, también separados por espacios en blanco).
Ejercicio propuesto 9.4.2: Crea un programa que permita guardar una lista ilimitada de nombres (cadenas de texto). El usuario introducirá tantos datos como desee (hasta terminar con una cadena vacía). A continuación se le preguntará qué nombres quiere buscar, y se le dirá si esa frase aparece como una de las cadenas de texto originales o no. Esta fase de búsqueda acabará también cuando el usuario introduzca una cadena vacía.
Ejercicio propuesto 9.4.3: Crea una "lista de cadenas de texto". Utilízala para mostrar el contenido de un fichero de texto, permitiendo scroll vertical: aparecerán las primeras 24 líneas; si el usario pulsa Z, se avanzará una línea; si pulsa A, se retrocederá una línea. La ejecución terminará cuando pulse Q.

Actualizado el: 21-07-2014 17:20

AnteriorPosterior