Estructura de Datos y Algoritmos Página: 1
UNIVERSIDAD NACIONAL DE SAN AGUSTÍN
ESCUELA PROFESIONAL DE INGENIERÍA DE SISTEMAS
LABORATORIO 04:
LINKED LIST
OBJETIVOS
Implementar listas enlazadas simples
Implementar listas enlazadas simples ordenadas
Implementar listas enlazadas dobles
II
TEMAS A TRATAR
Definiciones generales
Operaciones
Actividades
Implementación de listas enlazadas definidas por el usuario
Implementación de listas enlazadas ordenadas
Implementación de listas enlazadas dobles
Ejercicio aplicativo
III
MARCO TEÓRICO
Definiciones generales
Una lista enlazada es una colección de componentes llamado nodos, donde cada uno de ellos
tiene dos partes: una almacena la información relevante (datos), y la otra guarda la dirección
del siguiente nodo de la lista. A este último se le llama link (enlace).
Todos excepto el último nodo, tienen una dirección en el campo link.
La dirección del primer nodo de la lista se guarda en una ubicación separada, llamada la cabeza
(head o first).
La diferencia principal de una lista enlazada con un arreglo, es que en un arreglo los elementos
deben de estar almacenados en posiciones continuas de la memoria, sin embargo, en una lista
no.
Operaciones
Las operaciones básicas de una lista enlazada son:
initializeList(): inicializa la lista enlazada en estado vacío
isEmpty(): verifica si la lista está vacía
Karim Guevara Puente de la Vega Lab 04
Estructura de Datos y Algoritmos Página: 2
length(): determina la cantidad (longitud) de elementos que hay en la lista
search(x): verifica si el elemento x está o no en la lista. Devuelve su posición en caso exista,
sino retorna -1.
insertFirst(x): inserta un nuevo elemento x al inicio de la lista
insertLast(x): inserta un nuevo elemento x al final de la lista
deleteNode(x): elimina el elemento x de la lista.
La siguiente operación no es parte de la interfaz. Se trata de una operación privada/protegida de la lista,
que da soporte o es utilizada por otras operaciones:
destroyList(): elimina los elementos de la lista dejándola vacía
IV
ACTIVIDADES
1. Implementación de Listas enlazadas definidas por el usuario
La clase LinkedList, implementa una lista enlazada como parte de TDA lista.
a) Cree un proyecto nuevo en java.
b) Cree la interfaz ListTDA en la que declare todos los métodos públicos del TDA lista
c) Cargue el archivo Node.java que se encuentra en la carpeta Ejercicio1.
d) Cargue el archivo LinkedList.java que se encuentra en la carpeta Ejercicio1.
e) Analice el contenido del código presentado parcialmente.
f) Complete los métodos cuyas implementaciones aún falten.
g) Escriba la clase testList.java que se encargue de verificar la implementación de una lista
de enteros y otra de caracteres.
2. Listas enlazadas simples ordenadas
Muchas veces es necesario mantener un cierto orden entre los elementos de una lista
enlazada. Si bien, la operación de búsqueda será mucho más eficiente en una lista enlazada
ordenada a una que no esté ordenada, la operación de inserción puede tornarse un poco
más lenta en vista que el elemento nuevo debe ser insertado en el lugar que le
corresponda.
Por ejemplo, el código del método de búsqueda de un elemento en una lista ordenada
puede ser el siguiente:
boolean search(Type item) {
Node<Type> current;
current = this.first;
while( current != null && current.getInfo().compareTo(item) < 0 ){
current = current.getNext();
}
if( current != null )
return current.getInfo().equals(item);
return false;
}
a) Al proyecto anterior, agregue la clase OrderLinkedList.java que derive de LinkedList.
b) Redefina los métodos de búsqueda y eliminación.
c) Implemente un método insertOrder que inserte un elemento en la lista ordenada.
Karim Guevara Puente de la Vega Lab 04
Estructura de Datos y Algoritmos Página: 3
d) Modifique el código del programa testList.java, de tal manera que pueda usted probar la
implementación de una lista de enteros y otra de caracteres pero ordenadas.
3. Listas doblemente enlazadas
Implemente una lista doblemente enlazada, para esto realice lo siguiente:
a) Cree un nuevo proyecto
b) Agregue al proyecto el archivo Node.java completado en el ejercicio 1.
c) Agregue al proyecto el archivo NodeDouble.java que tiene la definición e
implementación de la estructura de un nodo de una lista doblemente enlazada. Esta
clase deriva de la clase Node. Complete la implementación parcial presentada de
NodeDouble.
Realice las modificaciones que considere pertinentes para que la herencia entre ambas
clases de nodos funcione correctamente en la implementación de la lista doble.
d) Agregue al proyecto la clase LinkedDoubleList para implementar la lista doblemente
enlazada que tenga una referencia de tipo NodeDouble que tiene la dirección de uno
de los nodos de la lista doble a partir del cual se tiene acceso a los demás nodos. Use
como ejemplo el código parcialmente implementado del archivo LinkedDoubleList.java
e) Complete los métodos que aún no estén implementados de la clase LinkedDoubleList,
de tal forma que sea una lista ordenada ascendentemente.
f) Agregue la clase de testing y pruebe la funcionalidad de la lista doble.
EJERCICIO
Se sabe que, en una empresa de Seguros los clientes son atendidos por los agentes de la
aseguradora. El administrador está preocupado porque no tiene un sistema que le permita
gestionar de una manera rápida y segura los agentes y sus clientes. Por lo que, se pide le ayude
escribiendo un programa que cubra los siguientes requerimientos.
• Ingresar los datos de los agentes
• Ingrese los datos de un cliente que sea atendido por un determinado agente.
• Mostrar un listado detallado de todos los clientes de sean atendidos por un agente
determinado.
• Buscar un determinado cliente que sea atendido por un agente dado.
• Eliminar a un cliente determinado de la cartera de clientes de un agente.
• Eliminar a un agente determinado. Para eliminarlo no debe poseer clientes, en
caso los tenga, estos clientes deben ser migrados a la cartera de clientes del
agente con menos clientes.
Considerando la metodología de diseño orientada a objetos, la herencia y la generecidad,
diseñe e implemente una solución que responda a los requerimientos antes mencionados.
Además, considere que para la gestión de clientes se debe utilizar una lista enlazada simple del
tipo LinkedList, y para la cartera de clientes de cada agente se debe utilizar una lista
doblemente enlazada ordenada del tipo LinkedDoubleList, tal como se muestra en el esquema
de la figura 3.1.
También debe considerar el hecho que ya se tiene la clase Persona.java la misma que debe
derivar para implementar las clases de clientes y de agentes de la aseguradora.
Cada agente tiene los atributos Código, Nombre, Apellido y su cartera de clientes. Y cada
cliente cuenta con su Código del cliente, Nombre Apellidos y Dirección.
Karim Guevara Puente de la Vega Lab 04
Estructura de Datos y Algoritmos Página: 4
Figura 3.1. Esquema gráfico de las estructuras de datos a utilizar en la solución
Karim Guevara Puente de la Vega Lab 04
