PDF de programación - Estructuras de datos y algoritmos 5. Implementación de listas, colas y pilas

Estructuras de datos y algoritmos
1. Introducción
2. Estructuras de datos lineales
3. Estructuras de datos jerárquicas
4. Grafos y caminos
5. Implementación de listas, colas y pilas
6. Implementación de mapas, árboles y grafos

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour

17/nov/09

1

UNIVERSIDAD
DE CANTABRIA

5. Implementación de listas, colas y pilas
• 5.1. Introducción
• 5.2. Pilas, colas y vectores implementados mediante arrays
• 5.3. Implementaciones con listas enlazadas simples
• 5.4. Listas enlazadas con cursores
• 5.5. Listas doblemente enlazadas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

2

5.1. Introducción
Motivos para crear estructuras de datos propias
• persistente: estructura de datos que reside en disco
• específicas de la aplicación: por ejemplo, mapa con elementos

UNIVERSIDAD
DE CANTABRIA

no modificables, adaptación a los datos concretos de la
aplicación

• optimizadas: en tiempo de ejecución o en espacio
• funcionalidad extra: por ejemplo ordenación especial, ...
• comodidad: por ejemplo dar implementaciones más simples o

en otros idiomas, ...

• adaptación de otras estructuras ya realizadas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

3

Implementación de estructuras de
datos propias para colecciones Java
En las colecciones java se definen implementaciones de clases
abstractas
• pensadas para facilitar la creación de estructuras de datos

UNIVERSIDAD
DE CANTABRIA

propias

• implementan parte de los métodos, para ahorrar trabajo
- estos métodos se pueden redefinir si se cree conveniente

Las clases abstractas que se proporcionan son
• AbstractCollection — una Colección que no es ni un
Conjunto ni una Lista
- como mínimo hay que proporcionar el iterador y el método size
• AbstractSet — un Conjunto;
- como mínimo hay que proporcionar el iterador y el método size

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

4

Implementación de estructuras de
datos propias para colecciones Java
• AbstractList — una lista en la que los elementos se guardan
en un array o similar
- como mínimo hay que proporcionar los métodos de acceso

posicional (get y opcionalmente set, remove y add) y el método
size
la clase ya proporciona el iterador de listas

UNIVERSIDAD
DE CANTABRIA

-

• AbstractSequentialList — una lista en la que los elementos
se guardan en una estructura de datos secuencial (por ejemplo
una lista enlazada)
- como mínimo hay que proporcionar el iterador de lista y el método

size
la clase abstracta proporciona los métodos posicionales

-

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

5

Implementación de estructuras de
datos propias para colecciones Java
• AbstractQueue — una cola

- como mínimo hay que proporcionar offer, peek, poll, y size y

UNIVERSIDAD
DE CANTABRIA

un iterador que soporte remove

• AbstractMap — un Mapa

- como mínimo hay que proporcionar la vista entrySet
- habitualmente esto se hace con la clase AbstractSet
- si el mapa es modificable, como mínimo hay que proporcionar el

método put

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

6

Proceso para escribir una
implementación propia
1. Elegir la clase abstracta apropiada
2. Proporcionar implementaciones para los métodos abstractos
3. Si la colección es modificable, será necesario redefinir también

UNIVERSIDAD
DE CANTABRIA

algunos métodos concretos
- El manual nos describe lo que hace cada uno

4. Codificar y probar la implementación

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

7

Relaciones entre datos
En muchas estructuras de datos es preciso establecer relaciones
o referencias entre diferentes datos
• ahorran espacio al no repetir datos
• evitan inconsistencias
Si los datos están en un array, se pueden utilizar cursores
• el cursor es un entero que indica el número de la casilla del array

UNIVERSIDAD
DE CANTABRIA

donde está el dato

Si la lista de alumnos no es un array deben utilizarse referencias o
punteros (si los soporta el lenguaje de programación)
• son datos especiales que sirven para apuntar o referirse a otros

datos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

8

Ejemplo: listas de alumnos de
asignaturas

UNIVERSIDAD
DE CANTABRIA

Asignatura 1

María Fdez.
Gral. Dávila, 23...

Jesús Pérez
Canalejas, 13...
Andrés Puente
c/Salamanca, 8...

Asignatura 2

María Fdez.
Gral. Dávila, 23...
Andrés Puente
c/Salamanca, 8...

Pepe Gómez
c/Cádiz, 3...

¡Hay datos
repetidos!

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

9

Alternativa: Referencias entre datos

UNIVERSIDAD
DE CANTABRIA

Asignatura 2

Asignatura 1

Alumnos

Pepe Gómez
c/Cádiz, 3...
María Fdez.
Gral. Dávila, 23...
Andrés Puente
c/Salamanca, 8...
Jesús Pérez
Canalejas, 13...

...

...

...

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

10

Punteros
Las referencias, también llamadas punteros o tipos acceso,
proporcionan acceso a otros objetos de datos
En Java, todos los objetos y arrays se usan a través de referencias
• las variables de los tipos primitivos no
- enteros, reales, caracteres, booleanos

UNIVERSIDAD
DE CANTABRIA

• pero tienen clases asociadas que permiten usar estos datos

como objetos
- ej., Integer, Double, Boolean, Character

Hay un valor predefinido, null, que es el valor por omisión, y no
se refiere a ningún dato

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

11

Estructuras de datos dinámicas
Las referencias son útiles cuando se usan para crear estructuras
de datos con relaciones entre objetos
Por ejemplo, una lista enlazada

UNIVERSIDAD
DE CANTABRIA

Contenido

Próximo

A1

Celda

A2

...

An

• cada elemento tiene un contenido y un puntero al próximo
• el último tiene un puntero próximo nulo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

12

Flexibilidad de la estructura de datos
dinámica
Se pueden insertar nuevos elementos en la posición deseada,
eficientemente:

UNIVERSIDAD
DE CANTABRIA

A1

A2

...

An

X

Diferencias con el array:
• los arrays tienen tamaño fijo: ocupan lo mismo, incluso medio

vacíos

• con estructuras de datos dinámicas se gasta sólo lo preciso
• pero se necesita espacio para guardar los punteros

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

13

5.2. Pilas, colas y vectores
implementados mediante arrays
La lista se representa mediante un array en el que cada casilla
almacena un elemento, y los elementos se ordenan según el índice
de la casilla

UNIVERSIDAD
DE CANTABRIA

ultimo

Elementos

0
1

Primer Elemento
Segundo Elemento

...

Último Elemento

Lista

...

Vacío

length-1

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

14

UNIVERSIDAD
DE CANTABRIA

Cambio dinámico de tamaño
Cuando la lista está llena y se intenta añadir un nuevo elemento
• lista acotada: indicar un error
• lista ilimitada: cambiar el tamaño del array
El cambio de tamaño directo no es posible en Java ni en la mayoría
de los lenguajes
• crear un nuevo array (por ejemplo del doble de tamaño)
• copiar todos los elementos en el nuevo array

- en el momento del cambio
- o poco a poco, en sucesivas operaciones (amortización)

• eliminar el array viejo (en Java esto es automático)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

15

UNIVERSIDAD
DE CANTABRIA

5.2.1. Implementación de las
operaciones de las listas
El acceso posicional es inmediato
• en el array tenemos acceso posicional de forma natural
La inserción al final es eficiente: O(1)
• incrementar el cursor ultimo
• meter el nuevo elemento en la casilla ultimo
La inserción en la posición i es O(n)
• hacer hueco

- mover las casillas en el rango [i,ultimo] una casilla hacia

adelante, yendo desde el final al principio
• meter el nuevo elemento en la casilla i
• incrementar el cursor ultimo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

16

UNIVERSIDAD
DE CANTABRIA

Implementación de las operaciones de
las listas (cont.)
La eliminación de la posición i es O(n)
• almacenar el elemento de la casilla i en una variable
• cerrar el hueco

- mover las casillas en el rango [i+1,ultimo] una casilla hacia

atrás, yendo del principio hacia el final

• decrementar el cursor ultimo
• retornar la variable con el elemento borrado
Iterador
• se implementa con un cursor que apunta al elemento próximo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

17

Ejemplo: implementación de una lista
acotada en Java
Queremos implementar algo similar al ArrayList, pero que no
cambie de tamaño si no cabe un elemento
• puede ser útil en sistemas con listas de tamaño limitado
• o en sistemas de tiempo de respuesta predecible

UNIVERSIDAD
DE CANTABRIA

- sistemas de tiempo real

• si se excede el tamaño es por un error: conviene indicarlo
En las colecciones Java disponemos de clases abstractas que
facilitan la implementación de las diferentes interfaces

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour

17/nov/09

18

UNIVERSIDAD
DE CANTABRIA

Código Java de la lista limitada
import java.util.*;
/**
* Clase con una lista implementada en un array
* Se limita el numero de elementos que pueden
* meterse
*/public class ListaArrayAcotada<E>
extends AbstractList<E>
{
public static int maxPorOmision=50;

// El array y el cursor ultimo
private E[] lista;
private int ultimo;

DEPARTAMENTO DE