Estructura de Datos

Facultad de Ingeniería

Facultad de IngenieríaDepartamento de Ciencias de la

Información

Estructuras de DatosTema x: Listas Circulares

• Contenido de la presentación

Título

Listas CircularesLas listas circulares son listas en las cuales el último elemento se

enlaza con la cabeza de la lista.

A diferencia de las listas normales que terminan en elementos nulos,los nodos en las listas circulares siempre tienen un elementosiguiente.

Las listas circulares se pueden implementar usando listas simples,las cuales tienen una sola dirección de recorrerse y también sepueden implementar usando listas dobles las cuales se puedenrecorrer en las dos direcciones.

Listas CircularesCaracterísticas:

• Una lista vacía debe ser una lista circular.• Una lista con un elemento debe ser una lista circular.• Una lista con un elemento debe ser una lista circular.• Una lista con muchos elementos debe seguir siendo una lista

circular.

Listas CircularesDefinición:

Sobre una lista se pueden realizar múltiples operaciones como:

Insertar datos al inicio de la lista.Insertar datos al final de la lista.Insertar datos en algún lugar dentro de la lista.Eliminar datos al inicio de la listaEliminar datos al final de la listaEliminar datos en algún lugar dentro de la lista.Buscar un valor dentro de la lista.Obtener la lista invertida.Concatenar dos listas.Recorrer una lista.

Listas CircularesEjercicio:

Simulación de una ruleta.

Una ruleta está compuesta por un número definido de elementos(Los cuales se asignan como los valores de los nodos en unalista circular).

La ruleta tiene un indicador que muestra el número seleccionado.

La ruleta se hace girar y al detenerse, el indicador debe mostrar elnúmero ganador.

Listas CircularesEjercicio:

Una jugada consiste en tirar girar la ruleta en una dirección, hastaque esta se detenga (Para simular la rotación se debe generar unnúmero aleatorio y se avanza el elemento actual de la lista tantasveces como lo indique el número aleatorio).

Cada jugada se registra en una lista de números ganadores.

Listas CircularesProblemas:

Proponga el TAD Listas Circulares.

Implemente el juego de la ruleta usando listas circularessimplemente enlazadas.

Implemente el juego de la ruleta usando listas circulares doblementeenlazadas.