Tipos de Estructuras de Datos: Listas, Pilas, Colas y Árboles

Listas

Una lista es una estructura de datos dinámica formada por un conjunto de elementos del mismo tipo almacenados en la memoria principal siguiendo una secuencia lógica. Cada uno de los elementos de una lista se llama nodo.

Listas Enlazadas

Son aquellas cuyos elementos se encuentran almacenados en posiciones de memoria no contiguas. Cada nodo está formado por dos campos:

• Información: contiene el dato almacenado en cada nodo.
• Indicador: actúa de enlace con el siguiente o el anterior.

Listas Doblemente Enlazadas

Son las que pueden recorrerse en ambas direcciones gracias a que los nodos que forman la lista están formados por 3 campos:

• Información
• Puntero que señala al anterior
• Un segundo puntero que apunta al siguiente

Listas Circulares

Se caracterizan porque el campo del último nodo apunta al primer nodo o elemento de la lista. Su ventaja es permitir el acceso a un nodo a partir de cualquier nodo perteneciente a la lista.

Pilas

Una pila es una lista lineal o grupo ordenado de elementos homogéneos en la cual los elementos sólo pueden ser añadidos o eliminados por un extremo llamado cabecera.

Para añadirle un elemento se requiere:

1. Comprobar si está llena.
2. Si no lo está, incrementar en 1 el puntero de la pila.
3. Introducir el nuevo elemento en la posición que marca el puntero.

Para extraerlo se hace la inversa.

Colas

Una cola es una lista lineal o grupo ordenado de elementos del mismo tipo, en la que, a diferencia de las pilas, los elementos se añaden por un extremo y se quitan por el otro.

Árboles

Un árbol es una estructura de datos jerarquizada y no lineal constituida por un conjunto de elementos homogéneos. La jerarquía utilizada en este tipo de estructura de datos es:

• Raíz
• Nodo
• Nodo terminal
• Altura
• Antecesor
• Sucesor
• Rama
• Recorrido

Árbol Binario

Un árbol binario es una estructura de datos caracterizada porque cada uno de los nodos que forman la parte integrante del árbol pueden tener ninguno, uno o dos sucesores. Los árboles pueden implementarse mediante:

• Listas enlazadas
• Tablas
• Un solo vector

Árbol Binario de Búsqueda

Se caracteriza porque el valor de cualquier nodo debe ser superior al valor de cualquiera de los nodos del subárbol izquierdo e inferior al valor de cualquiera de los nodos del subárbol derecho.

Recorrido de un Árbol

El recorrido de un árbol es la operación que consiste en acceder a cada uno de los nodos del árbol, sin visitar dos veces al mismo elemento. Puede ser:

• Preorden
• Inorden
• Postorden