ESTRUCTURAS DE

DATOS

IPC 1

ESTRUCTURAS

DINÁMICAS

Definicion Son las estructuras que su tamaño y forma es variable(o

puede serlo) a lo largo de un programa, por lo que se

crean y destruyen en tiempo de ejecución. Esto permite

dimensionar la estructura de una forma precisa.

Es decir seba asignando memoria en tipo de ejecución

según se va necesitando.

Tipos de Estructuras dinámicas

• Estas se pueden clasificar en 2 tipos:

Conceptos claves Apuntadores/puntero :Las variables de tipo puntero son las

que nos permiten referenciar datos dinámicos.

• Un apuntador es una variable que contiene la dirección en

memoria de otra variable.

• En Java los apuntadores se manejan como referencias.

Conceptos claves • Clase autoreferenciada: Una clase con al menos un campo cuyo

referencia es el nombre de la clase:

• Nodo: un objeto creado desde una clase autoreferenciada.

• Campo de enlace: un campo cuyo tipo de referencia es el nombre

de la clase.

• Enlace: la referencia a un campo de enlace.

TIPOS LINEALES

Pila (Stack)

Una pila es un conjunto ordenado de elementos. Estos

elementos solamente se pueden acceder por un lugar

único o extremo de la pila.

Las pilas utilizan la política de acceso tipo LIFO. (Last In

First Out).

Operaciones en una pila

• Poner (Push) : esta operación permite añadir un

elemento a la pila.

• Sacar(Pop) : esta operación permite sacar un elemento

de la pila.

• Cima(Top o peek): esta operación permite obtener el

elemento en la cima de la pila.

Cola (Queue)

Una cola es una estructura de datos que permite el

almacenamiento de elementos en una lista y que permite

acceder a los mismos por ambos extremos de la lista.

Las colas utilizan la política de acceso tipo FIFO. (First In

First Out).

• Encolar/Insertar: esta operación permite ingresar un

elemento en el extremo final de la cola.

• Desencolar/Extraer: esta operación permite sacar un

elemento en el extremo frontal de la cola.

• Frente/ver primero: esta operación permite consultar el

elemento en el frente de la cola.

Operaciones de una cola

• Una lista en su sentido amplio, es un conjunto de

elementos del mismo tipo donde cada elemento tiene un

único predecesor (excepto el primero) y un único sucesor

(excepto el último) y cuyo número de elementos es

variable.

Tipos de Lista:

1. Listas simples enlazadas

2. Listas doblemente enlazadas

3. Listas circulares simples enlazadas

4. Listas circulares doblemente enlazadas

5. Listas ortogonalmente enlazadas(Matriz ortogonal)

Lista

Operaciones en Listas

• Insertar: inserta un elemento final de la lista

• Insertar en posición: inserta un elemento en una

posición especificada, si existe.

• Buscar: busca un elemento dentro de la lista.

• Obtener: obtiene un elemento en la posición

especificada, si existe

• Borrar/eliminar: borra un elemento dentro de la lista.

Listas simples enlazadas

• Es una lista enlazada de nodos, donde cada nodo tiene

un único campo de enlace. Una variable referencia

contiene una referencia al primer nodo, cada nodo

(excepto el último) enlaza con el nodo siguiente, y el

enlace del último nodo contiene null para indicar el final

de la lista.

Listas doblemente enlazadas

• Una lista doblemente enlazada es una lista lineal en la

que cada nodo tiene dos enlaces, uno al nodo siguiente,

y otro al anterior.

• Las listas doblemente enlazadas no necesitan un nodo

especial para acceder a ellas, pueden recorrerse en

ambos sentidos a partir de cualquier nodo, esto es

porque a partir de cualquier nodo, siempre es posible

alcanzar cualquier nodo de la lista, hasta que se llega a

uno de los extremos.

Listas circulares

• La lista circular es una especie de lista enlazada simple o doblemente enlazada, pero que posee una característica adicional para el desplazamiento dentro de la lista, “ésta no tiene fin”

• Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el 1er elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas

• En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento.

Ejemplo

• Lista circular simple enlazada

• Lista circular simple enlazada

Matriz Ortogonal

• una matriz ortogonal es una estructura de datos utilizada

para implementa una tabla con memoria dinámica. Y la

cual puede buscar o recorrer por uno de los dos aspectos

de orden(Filas/Columnas).

• una matriz ortogonal tiene cuatro apuntadores "arriba"

"abajo" "Derecha" "Izquierda".

Ejemplo

• Gráficamente una matriz ortogonal se miraría de la

siguiente forma:

Listas

• Una lista es una ordenada colección (a veces llamada una secuencia). Las listas pueden contener elementos duplicados.

• List<E>: Elementos en una secuencia particular que mantienen un orden y permite duplicados. La lista puede ser recorrida en ambas direcciones con un ListIterator. Hay 3 tipos de constructores: 1. ArrayList<E>: Su ventaja es que el acceso a un elemento en particular es

ínfimo. Su desventaja es que para eliminar un elemento, se ha de mover toda la lista para eliminar ese “hueco”.

2. Vector<E>: Es igual que ArrayList, pero sincronizado. Es decir, que si usamos varios hilos, no tendremos de qué preocuparnos hasta cierto punto.

3. LinkedList<E>: En esta, los elementos están conectados con el anterior y el posterior. La ventaja es que es fácil mover/eliminar elementos de la lista, simplemente moviendo/eliminando sus referencias hacia otros elementos. La desventaja es que para usar el elemento N de la lista, debemos realizar N movimientos a través de la lista.

.