Listas lineales

En esta sección se mostrarán algunos algoritmos sobre listas lineales sin nodo de cabecera y con nodo de cabecera.

Una lista con nodo de cabecera es aquella en la que el primer nodo de la lista contendrá en su campo dato algún valor que lo diferencíe de los demás nodos (como : *, -, +, etc). Un ejemplo de lista con nodo de cabecera es el siguiente:

En el caso de utilizar listas con nodo de cabecera, usaremos el apuntador CAB para hacer referencia a la cabeza de la lista.

Para el caso de las listas sin nodo de cabecera, se usará la expresión TOP para referenciar al primer nodo de la lista, y TOP(dato), TOP(liga) para hacer referencia al dato almacenado y a la liga al siguiente nodo respectivamente.

Algoritmo de Creación

top<--NIL
repite
         new(p)
         leer(p(dato))
          si top=NIL entonces
        top<--p
          en caso contrario
        q(liga)<--p
           p(liga)<--NIL
           q<--p
           mensaje('otro nodo?')
            leer(respuesta)
hasta respuesta=no

Algoritmo para Recorrido

p<--top
mientras p<>NIL haz
        escribe(p(dato))
        p<--p(liga:)

Algoritmo para insertar al final

p<--top
mientras p(liga)<>NIL haz
        p<--p(liga)
new(q)
p(liga)<--q
q(liga)<--NIL

Algoritmo para insertar antes/después de ‘X’ información

p<--top
mensaje(antes/despues)
lee(respuesta)
si antes entonces
        mientras p<>NIL haz
                si p(dato)='x' entonces
                        new(q)
                        leer(q(dato))
                        q(liga)<--p
                        si p=top entonces
                                top<--q
                        en caso contrario
                                r(liga)<--q
                        p<--nil
                en caso contrario
                        r<--p
                        p<--p(link)
si despues entonces
        p<--top
        mientras p<>NIL haz
                si p(dato)='x' entonces
                        new(q)
                        leer(q(dato))
                        q(liga)<--p(liga)
                        p(liga)<--q
                        p<--NIL
                en caso contrario
                        p<--p(liga)
        p<--top
        mientras p(liga)<>NIL haz
                p<--p(liga)
        new(q)
        p(liga)<--q
        q(liga)<--NIL

Algoritmo para borrar un nodo

p<--top
leer(valor_a_borrar)
mientras p<>NIL haz
        si p(dato)=valor_a_borrar entonces
                si p=top entonces
                        si p(liga)=NIL entonces
                                top<--NIL
                        en caso contrario
                                top(liga)<--top(liga)
                en caso contrario
                        q(liga)<--p(liga)
                dispose(p)
                p<--NIL
        en caso contrario
                q<--p
                p<--p(liga)

Algoritmo de creación de una lista con nodo de cabecera

new(cab)
cab(dato)<--'*'
cab(liga)<--NIL
q<--cab
repite
          new(p)
          leer(p(dato))
          p(liga)<--NIL
          q<--p
          mensaje(otro nodo?)
           leer(respuesta)
hasta respuesta=no

Algoritmo de extracción en una lista con nodo de cabecera

leer(valor_a_borrar)
p<--cab
q<--cab(liga)
mientras q<>NIL haz
        si q(dato)=valor_a_borrar entonces
                p<--q(liga)
                dispose(q)
                q<--NIL
        en caso contrario
                p<--q
                q<--q(liga)

Fuente: Apunte de Estructura de Datos del Instituto tecnológico de la Paz