Estructuras dinamicas, estructura de datos Ingenieria en sistemas

Manual de Java

Capítulo 9. Estructuras dinámicas lineales

Capítulo 9. Estructuras dinámicas
lineales
A. J. Pérez

Listas
Las listas como TDA
Lista basada en array estático
Lista enlazada
Lista enlazada doble
API Java Collection
Iterable
Collection
List
ArrayList y Vector
Implementación basada en arrays
ArrayList en la memoria
Cuándo utilizar ArrayList
Ejemplo: Obtención de los números primos enun intervalo
Ejemplo: Unión e intersección de dos listas
Conversiones entre List y array
LinkedList
Cuándo utilizar LinkedList
Operaciones básicas con LinkedList
Stack
Pila implementada con un array
Pila implementada con una lista enlazada
Operaciones básicas de una pila
Ejemplo: Uso de una pila
Ejemplo: Chequeo de paréntesis en expresiones aritméticas
Queue
Cola implementada con un array
Colaimplementada con una lista enlazada
Operaciones básicas sobre colas
Ejemplo: Uso de una cola
Ejemplo: Secuencia N, N+1, 2*N
Clase Collections
Ejercicios
Fuentes y bibliografía

1

Manual de Java

Capítulo 9. Estructuras dinámicas lineales

Estructuras dinámicas lineales
Las estructuras dinámicas se caracterizan por tener un número de elementos que, sin ser
conocido a priori, no tiene máximo teóricodurante la ejecución de un programa.​ Las
estructuras dinámicas se contraponen a las estructuras estáticas -típicamente arrays- que sí
requieren conocer el número de elementos antes de poder usar la estructura.
Las estructuras de datos son lineales si en su organización cumplen la condición de que
después, o antes, de un elemento puede existir como máximo un solo elemento​. Hay que
destacar quelos arrays son estructuras lineales de naturaleza estática.
Para el tratamiento y almacenamiento de datos en estructuras lineales existen típicamente tres
tipos básicos:

❖ Listas
❖ Colas
❖ Pilas
Cada una de estas estructuras responden a unas características, necesidades y restricciones
específicas según un ​tipo de dato abstracto​ ​(TDA)​ estándar que es independiente de la manera
deimplementación utilizada.
En general, los ​TDA ​constituyen una definición del comportamiento de las estructuras
desde el punto de vista de las operaciones y propiedades permitidas, sin importar las
aplicaciones específicas, las alternativas de implementación y el rendimiento.​ Podrían por
ejemplo implementarse con características estáticas o dinámicas sin afectar esencialmente a su
funcionalidad.

Listas
Sonuna abstracción para representar y organizar colecciones de datos linealmente en
secuencias y series de elementos agrupados por algún criterio.
Se puede decir que una ​lista​ es una secuencia organizada de elementos para un fin concreto.
Por ejemplo la lista de la compra a realizar en una tienda; en la lista podemos leer cada uno de
los elementos (cosas o productos a adquirir), se pueden añadirnuevas cosas en la misma;
podemos eliminar (borrar) algo o se pueden clasificar u ordenar por algún criterio.

Las listas como TDA
Una ​lista ​es una estructura de datos lineal que contiene una serie de elementos. Una lista
tiene una longitud característica (número de elementos), y sus elementos están dispuestos de
forma secuencial.
Una ​lista permite añadir elementos en cualquier punto, eliminarcualquier elemento y
2

Manual de Java

Capítulo 9. Estructuras dinámicas lineales

realizar diferentes comprobaciones sobre la estructura. Como se mencionó anteriormente,
un ​TDA ​puede tener diferentes implementaciones.
Un ejemplo de ​TDA es la ​interfaz ​java.util.​List . Los interfaces en Java son un ​marco para
la implementación de clases​. Este ​framework es un conjunto de métodos ypropiedades que la
clase correspondiente tiene el compromiso de implementar.
La interfaz ​java.util.​List especifica los principales métodos para el funcionamiento
previsto de una lista:
void add(Object)

void add(int, Object)
índice.

void clear()

boolean contains(Object)
Object get(int)
índice.

int indexOf(Object)
boolean isEmpty()

boolean remove(Object)
Object remove(int)
int size()

- Añade un...