INSERCION Y ELIMINACION EN UNA LISTA ENLAZADA

INSERCIÓN EN UNA LISTA ENLAZADA

Sea LISTA una lista enlazada en la que los nodos A y B ocupan posiciones sucesivas en el orden impuesto en la lista. Supongamos que queremos insertar en ella un nodo N que debe ocupar un lugar entre A y B. Después de la operación el nodo A apuntara al nodo N y este apuntara al nodo B, es decir, el nodo al que apuntaba antes A.

Algoritmo de inserción

Tres son las situaciones mas comunes que nos encontraremos cuando insertamos nodos en una lista. Primero cuando queremos insertar un nodo al principio de la lista, segundo cuando queramos insertar un nodo detrás de un determinado, y tercero, cuando insertamos un nodo en una lista previamente ordenada. Suponiendo los algoritmos que llevan a cabo estas tareas que la lista esta almacenada en memoria en la forma LISTA(INFO, ENLACE, COMIENZO, DISP) y que la variable ELEMENTO contiene la información que debe incorporarse a la lista.

Puesto que nuestros algoritmos de inserción utilizaran nodos de la lista de nodos disponibles, todos ellos deben incluir los siguientes pasos:

  • Estudiar si existe espacio libre en la lista de espacio disponible. Si no es así, es decir, si DISPONIBLE = NULO, el algoritmo debe imprimir el mensaje OVERFLOW.

  • Extraer el primer nodo de la lista de disponible. Si utilizamos la variable Nuevo, esta operación puede realizarse mediante dos asignaciones (en este orden) NUEVO: = DISP. DISP: = ENLACE[DISP].

  • Incorporar la información a insertar en el nodo recién obtenido, es decir: INFO[NUEVO] = ELEMENTO.

Inserción al principio de una lista

Supongamos que nuestra lista no esta ordenada ni existe ninguna razón por la cual cualquier nodo que insertemos deba ocupar una determinada posición. En este caso lo mas sencillo sera insertar el nuevo nodo al comienzo de la misma. Un algoritmo que realiza esta operación es el siguiente.

Algoritmo: INSPRIN(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo coloca ELEMENTO como primer componente de la lista.

  1. [Overflow] si DISP = NULO, entonces: Escribir: OVERFLOW y salir.

  2. [extrae el primer nodo de la lista DISP].

  3. NUEVO: = DISP y DISP: = ENLACE[DISP].

  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo].

  5. ENLACE[NUEVO]: = COMIENZO. [el nuevo nodo apunta ahora al que ocupa antes la primera posición].

  6. COMIENZO: = NUEVO. [COMIENZO apunta ahora al elemento que ocupa la primera posición de la lista].

  7. Salir.

Inserción a continuación de un nodo determinado

Supongamos en este caso que se nos da un valor LUG que o bien representa la localización de un nodo A determinado o bien LUG = NULO. El algoritmo siguiente inserta ELEMENTO en la lista a continuación de A o bien coloca ELEMENTO como primer componente de la lista si LUG = NULO.

Sea N el nuevo nodo (cuya posición es NUEVO). Si LUG = NULO, entonces el nodo se coloca al comienzo de la lista. En otro caso hacemos que N apunte al nodo B (que originalmente seguía a A). El proceso implica las siguientes operaciones:

ENLACE[NUEVO]: = ENLACE[LUG]

después del cual N apunta a B y

ENLACE[LUG]: = NUEVO

tras el cual A apunta al nodo N.

Algoritmo: INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)

El algoritmo inserta ELEMENTO a continuación del nodo que ocupa la posición LUG o coloca ELEMENTO como primer nodo si LUG=NULO

  1. [Overflow] Si DISP = NULO, entonces: escribir: OVERFLOW y salir.

  2. [Extrae el primer nodo de la lista de disponibles]

  3. NUEVO: = DISP y DISP: = ENLACE[DISP].

  4. INFO[NUEVO]: = ELEMENTO. [copia el dato en el nodo obtenido].

  5. Si LUG = NULO, entonces [Lo inserta como primer nodo].

  6. ENLACE[NUEVO]: = COMIENZO y COMIENZO: = NUEVO.

  7. Si no: [Inserta detrás del nodo de posición LUG].

  8. ENLACE[NUEVO]: = ENLACE[LUG] y ENLACE[LUG]: = NUEVO.

  9. [Final de la estructura condicional]

  10. Salir.

Inserción de una lista enlazada y ordenada

Supongamos que queremos insertar ELEMENTO en una lista enlazada y ordenada y que ELEMENTO cumple que INFO(a)<ELEMENTO⇐INFO ( b ). Por tanto ELEMENTO debe insertarse en un nuevo nodo entre A y B. El procedimiento siguiente calcula la posición LUG que ocupa el nodo A, es decir, la posición del nodo que precederá a ELEMENTO en la lista.

Para ello utiliza dos punteros PTR y AUX. Con PTR recorre la lista y va comparando ELEMENTO con INFO[PTR] para todos los nodos que visita. Después de cada comparación actualiza el valor de ambos punteros, de tal forma que AUX:= PTR y posteriormente PTR:= ENLACE[PTR]. Con este mecanismo garantizamos que AUX siempre apunta al nodo que precede al que esta siendo apuntado por PTR. El recorrido de la lista continua hasta que INFO[PTR] > ELEMENTO, o en otras palabras, la búsqueda finaliza cuando ELEMENTO ⇐ INFO[PTR].

Una representación formal del procedimiento es el siguiente. En dicho procedimiento se contemplan por separado los casos en que la lista esta vacía o bien cuando

ELEMENTO < INFO[COMIENZO] debido a que no precisan el uso de la variable AUX.

Procedimiento: ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

El procedimiento encuentra la posición LUG del ultimo nodo para el que INFO[LUG] < ELEMENTO o hace LUG = NULO.

  1. [¿Lista vacía?] Si COMIENZO = NULO, entonces: LUG = NULO y retornar.

  2. [¿caso especial?] Si ELEMENTO < INFO[COMIENZO]. entonces: LUG: = NULO y retornar.

  3. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros].

  4. Repetir pasos 5 y 6 mientras PTR != NULO.

  5. Si ELEMENTO < INFO[PTR]. entonces:

  6. LUG: = AUX y retornar.

  7. [Final de la estructura condicional].

  8. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualiza los punteros].

  9. LUG: = AUX.

  10. Salir.

Después de esto ya tenemos las herramientas necesarias para diseñar un algoritmo que nos inserte ELEMENTO en una lista enlazada.

Algoritmo: INSERT(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo inserta ELEMENTO en una lista enlazada ordenada.

  1. [Utilizamos el procedimiento 6 para encontrar la posición del nodo que precederá a ELEMENTO.]

  2. Llamar ENCA (INFO, ENLACE, COMIENZO, ELEMENTO, LUG)

  3. [Utilizaremos el algoritmo 5 para insertar ELEMENTO a continuación del nodo que ocupa la posición LUG.]

  4. Llamar INSLUG(INFO, ENLACE, COMIENZO, DISP, LUG, ELEMENTO)

  5. Salir.

ELIMINACION DE UN ELEMENTO

DE UNA LISTA ENLAZADA.

Sea lista una lista enlazada en la cual el nodo N se encuentra entre los nodos A y B. Supongamos que queremos eliminar el nodo N de la lista. La eliminación se produce tan pronto como el puntero de enlace siguiente del nodo A apunte al nodo B. (por ello cuando realizamos eliminaciones debemos almacenar de alguna forma la dirección del nodo que precede al que vamos a borrar.)

Supongamos que la lista enlazada se mantiene en memoria en la forma siguiente:

LISTA(INFO, ENLACE, COMIENZO, DISP)

Cuando eliminamos el nodo N de la lista debemos devolverlo inmediatamente a la lista de espacio disponible. Por facilidad en el proceso esta devolución se realiza insertando el nodo devuelto al principio de la lista DISP. Obsérvese que esta operación implica cambiar tres punteros de la forma siguiente:

  • El puntero siguiente del nodo A debe cambiarse para apuntar al nodo B, al que apuntaba previamente N.

  • El puntero del nodo N se cambia y se le hace apuntar al primer nodo de la lista de nodos disponibles.

  • El puntero DISP se cambia y pasa de apuntar al antiguo primer nodo de la lista de disponibles para apuntar a N que sera el nuevo primer nodo.

Existen dos casos especiales que implican actuaciones distintas. Si el nodo N que eliminamos es el primero de la lista, el puntero COMIENZO deberá cambiarse para apuntar al nodo B. En cambio, si N es el ultimo de la lista, entonces el puntero A deberá ponerse a NULO.

Algoritmos de eliminación

Los algoritmos que eliminan nodos de una lista son utilizados en distintas situaciones. En este epígrafe discutiremos dos de ellas. La primera situación es la que implica borrar el nodo siguiente a uno dado. La segunda situación implica borrar un nodo que contiene un determinado elemento. En todos los algoritmos suponemos que la lista enlazada se almacena en memoria de la forma

LISTA (INFO, ENLACE, COMIENZO, DISP).

También en todos ellos devolvemos el nodo eliminado a la lista de nodos disponibles, insertándolos al principio de esta. Por ello nuestros algoritmos incluirán las siguientes asignaciones, donde LUG es la posición del nodo N borrado: ENLACE[LUG]: = DISP y DISP: = LUG.

Algunos de nuestros algoritmos pueden borrar o bien el primer elemento de la lista o bien el ultimo. Cualquier algoritmo que haga esto debe analizar primero si existe algún elemento en la lista. Si no existe ningún, si COMIENZO = NULO, el algoritmo imprimirá el mensaje UNDERFLOW.

Eliminación del nodo sucesor de uno determinado

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de LISTA el nodo N que ocupa el lugar LUG y que conocemos el lugar LUGP del nodo que precede a N en la lista o bien si el nodo N es el primer LUG = NULO. El algoritmo siguiente elimina N de la lista.

Algoritmo: BOR (INFO, ENLACE, COMIENZO, DISP, LUG, LUGP)

El algoritmo elimina de la lista el nodo N que ocupa la posición LUG, siendo LUGP la posición del nodo que precede a N o bien LUGP = 0 si N es el primero de la lista.

  1. si LUGP = NULO. Entonces:

  2. COMIENZO: = ENLACE[COMIENZO]. [Elimina el primer nodo].

  3. Si no:

  4. ENLACE[LUGP]: = ENLACE[LUG]. [Elimina el nodo N].

  5. [Final de la estructura condicional].

  6. [Devolvemos el nodo a la lista DISP].

  7. ENLACE[LUG]: = DISP Y DISP: = LUG.

  8. Salir.

Eliminación de un nodo que contiene un determinado elemento de información

Sea LISTA una lista enlazada almacenada en memoria. Supongamos que queremos eliminar de la lista el primer nodo N que contenga la información ELEMENTO. (Si ELEMENTO es un valor de clave, solo puede contenerlo un único nodo.) Recuérdese que antes de borrar el nodo N que contiene a ELEMENTO debemos conocer que nodo precede a N en la lista. Por ello veremos previamente un procedimiento que localiza la posición LUG del nodo N que contiene a ELEMENTO y la posición LUGP del nodo que precede a N. En el caso de que N sea el primer nodo de la lista, el procedimiento devuelve LUGP = NULO y en caso de que ELEMENTO no se encuentre en la lista devolverá LUG = NULO. (Como puede verse el procedimiento es similar al procedimiento)

Procedimiento: ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP)

El procedimiento encuentra la posición LUG del primer nodo N que contiene a ELEMENTO y la posición LUGP del nodo anterior a N. Si ELEMENTO no se encuentra en la lista, el procedimiento devuelve LUG = NULO y si ELEMENTO se encuentra en el primer nodo, entonces hace LUGP = NULO.

  1. [¿Lista vacía?] Si COMIENZO: = NULO, entonces:

  2. LUG: = NULO Y LUGP: = NULO y Retornar.

  3. [Final de la estructura condicional].

  4. [¿Se encuentra ELEMENTO en el primer nodo?]

  5. Si INFO[COMIENZO] = ELEMENTO, entonces

  6. LUG: = COMIENZO y LUGP = NULO y Retornar.

  7. [Final de la estructura condicional].

  8. AUX: = COMIENZO y PTR: = ENLACE[COMIENZO]. [Inicializamos los punteros].

  9. Repetir mientras PTR != NULO.

  10. Si INFO[PTR] = ELEMENTO, entonces:

  11. LUG: = PTR y LUGP: = AUX y Retornar.

  12. [Final de la estructura condicional].

  13. AUX: = PTR y PTR: = ENLACE[PTR]. [Actualizamos los punteros]:

  14. [Final del ciclo].

  15. LUG: = NULO [Búsqueda fallida].

  16. Retornar.

El procedimiento recorre la lista utilizando dos punteros PTR y AUX. Con PTR recorremos la lista y comparamos sucesivamente ELEMENTO con INFO[PTR]. En cada momento AUX apunta al nodo anterior al apuntado por PTR. Por ello después de cada fallida actualizamos ambas de la siguiente forma:

AUX: = PTR y PTR: = ENLACE[PTR]

El recorrido de la lista continua mientras que INFO[PTR] != ELEMENTO o, en otras palabras, la búsqueda terminara cuando INFO[PTR]=ELEMENTO. En este momento PTR = LUG o dirección del nodo N buscado y AUX apuntara al nodo anterior.

La formalización de este procedimiento se establece a continuación. En ella se puede observar que se tratan por separado los casos en que la lista esta vacía y el caso en que N es el primer nodo. Esto se hace así debido a que ambos casos no precisan la utilización de la variable AUX.

Después de desarrollar este procedimiento estamos en condiciones de diseñar un algoritmo muy sencillo que elimina de una lista enlazada aquel nodo N en el que aparece por primera vez la información ELEMENTO. La simplicidad de este algoritmo escriba en que la localización de N y de su predecesor pueda realizarse utilizando el procedimiento anterior.

Algoritmo: ELIMINAR(INFO, ENLACE, COMIENZO, DISP, ELEMENTO)

El algoritmo elimina de la lista enlazada el primer nodo N que contiene la información ELEMENTO.

  1. [Utilizamos el procedimiento anterior para encontrar la posición de N y su predecesor en la lista.]

  2. Llamar ENCB(INFO, ENLACE, COMIENZO, ELEMENTO, LUG, LUGP).

  3. Si LUG: = NULO, entonces: Escribir: ELEMENTO no se encuentra en la lista y salir.

  4. [Eliminamos el nodo].

  5. Si LUGP = NULO, entonces:

  6. COMIENZO: = ENLACE[COMIENZO]. [Eliminamos el primer nodo].

  7. Si no:

  8. ENLACE[LUGP]: = ENLACE[LUG].

  9. [Final de la estructura condicional].

  10. [Devolvemos el nodo eliminado a la lista de nodos disponibles].

  11. ENLACE[LUG]: = DISP y DISP: = LUG.

  12. Salir.

Un comentario el “INSERCION Y ELIMINACION EN UNA LISTA ENLAZADA

Deja un comentario o(‧'.'‧)o

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s