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

Resumen

El documento describe los tipos de estructuras de datos más usados. Explica las listas, en sus variantes enlazada, doblemente enlazada y circular, y las pilas y colas, que añaden y quitan elementos por extremos distintos. También define los árboles, sus términos básicos, el árbol binario y los tres tipos de recorrido: preorden, inorden y postorden.

Puntos clave

Una lista es una estructura dinámica de elementos del mismo tipo, y cada elemento se llama nodo.
En una lista enlazada, cada nodo tiene un campo de información y un indicador que enlaza con el siguiente o el anterior.
En una lista doblemente enlazada, cada nodo tiene tres campos: información, un puntero al anterior y otro al siguiente.
En una lista circular, el campo del último nodo apunta al primero.
En una pila, los elementos se añaden y se quitan por el mismo extremo, llamado cabecera.
En una cola, los elementos se añaden por un extremo y se quitan por el otro.
Un árbol es una estructura jerárquica y no lineal, con raíz, nodos, nodos terminales, ramas y altura.
En un árbol binario, cada nodo puede tener ninguno, uno o dos sucesores.

Resumen generado con IA a partir del documento. Ponte a prueba

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:

Comprobar si está llena.
Si no lo está, incrementar en 1 el puntero de la pila.
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

Preguntas frecuentes

¿Qué diferencia hay entre una pila y una cola?

En una pila, los elementos se añaden y se quitan por el mismo extremo, llamado cabecera. En una cola, se añaden por un extremo y se quitan por el otro.

¿Qué es un nodo en una lista?

Cada uno de los elementos de una lista se llama nodo. En una lista enlazada, cada nodo tiene un campo de información y un indicador de enlace.

¿Cuáles son los tipos de recorrido de un árbol?

Son el preorden, el inorden y el postorden. Todos acceden a cada nodo sin visitar dos veces el mismo elemento.