Solucionario

Estructura de datos

LISTA ENLAZADA

Fundamento teórico

Las estructuras de datos lineales de elementos homogéneos utilizaban

arreglos para implementar dichas estructuras, siendo los elementos

de tipos primitivos haciendo uso ineficiente de la memoria. Gracias a

la asignación dinámica la memoria física utilizada corresponde con el

número de elementos.

Lista enlazada es una colección de elementos(denominados nodos)

dispuestos uno a continuación del otro, cada uno de ellos conectados

por un “enlace”.

Representación de lista enlazada

Nodos: elementos

Campos: contiene información, valores heterogéneos

Enlace (Referencia): apunta al siguiente elemento de la lista.

null: Constante especial en Java

Se utiliza para cualquier valor de

referencia que no apunte a objeto alguno

Clasificación de las listas enlazadas

• Lista simplemente enlazadas: Cada nodo tiene un único enlace que lo

conecta al nodo siguiente.

• Listas doblemente enlazadas: Cada nodo contiene dos enlaces, uno

al nodos predecesor y otro a su nodo sucesor; Se puede recorrer en

dirección directa e inversa.

• Lista circular simplemente enlazada: El ultimo elemento (cola) se

enlaza al primer elemento (cabeza)

• Listas circular doble mente enlazada: El ultimo elemento se enlaza al

primer elemento y viceversa; Se puede recorrer en dirección directa e

inversa.

Operaciones en listas enlazadas

La implementación de <<Lista>> requiere en primer lugar declarar la clase

<<Nodo>> en la que se combinaran dos partes <<dato>> (entero, real,

doublé, carácter o referencias a objetos) y <<enlace>>

Operaciones:

Inicialización o creación

Insertar elementos en la lista

Eliminar elementos de la lista

Buscar elementos de la lista

Recorrer la lista enlazada

Comprobar si la lista está vácia

Declaración de un <<Nodo>>

En java se declara una clase para contener las dos partes del nodo:

dato y enlace

Variable referencia

Cabeza y cola

El primer nodo de la lista se llama <<cabeza>>

Una referencia al primer nodo se llama <<referencia cabeza>>

El ultimo nodo es la <<cola>> de la lista

Una referencia al ultimo nodo es la <<referencia a cola>>

Cada referencia de un nodo debe ser declarada como una variable referencia. Ejemplo:

De la clase Nodo:

Nodo cabeza;

Nodo cola;

Insertar un nuevo elemento en la cabeza

de la lista (I)

Resumen del algoritmo

Insertar un nuevo elemento en la cabeza

de la lista (II)

Insertar un nuevo elemento en la cabeza

de la lista (III)

Insertar un nuevo elemento en la cabeza

de la lista (IV)

Construcción de lista enlazada (I)

Es necesaria la clase:

• Nodo

Con sus respectivos atributos <<dato>> y <<enlace>>

Construcción de

lista enlazada (II)

• Lista

• Define el atributo <<cabeza>>

• Los métodos de la <<lista>> implementas las operaciones de una lista

enlazada

Construcción de lista enlazada (III)

Inserción al final de la lista

Una vez que la variable << ultimo >> apunta al final de la lista (cola), las

sentencias siguientes

Insertar entre dos nodos de la lista [I]

Insertar entre dos nodos de la lista [II]

Insertar entre dos nodos de la lista [III]

Insertar entre

...