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)