Conceptos Fundamentales de Estructuras de Datos Lineales y No Lineales

Estructura de Datos

¿Qué es una Lista Enlazada?

Corresponde a una estructura lineal compuesta por una colección de datos homogéneos con alguna relación entre ellos. Dicha estructura se crea a través del método **dinámico de memoria**.

En una lista enlazada, el orden de los elementos está determinado por un campo **enlace (puntero)** explícito en cada elemento, por ejemplo: pilas y colas dinámicas.

Tipos de Listas Enlazadas

• Listas lineales simplemente enlazadas
• Listas Circulares
• Listas doblemente enlazadas
• Listas *múltiplemente* enlazadas
• Listas Simplemente Enlazadas (Nota: Este ítem parece duplicar el primero, se mantiene por fidelidad al original)

Lista Lineal Simplemente Enlazada

Una lista lineal simplemente enlazada es una estructura en la que cada elemento enlaza con el siguiente. El recorrido se inicia a partir de un **puntero ubicado al comienzo de la lista** (la cabeza).

El último elemento (nodo) de la lista apunta a una dirección vacía que indica el fin de la estructura.

Cabe destacar que en una lista lineal enlazada, solo es posible acceder a los elementos sucesores pero no a los antecesores. Además, siempre es necesario mantener un puntero a la **cabeza de la lista** para acceder a los demás elementos.

Listas Circulares

Una lista circular es una lista lineal en la que el último elemento enlaza con el primero. Entonces es posible acceder a cualquier elemento de la lista desde cualquier punto dado.

La definición de tipo es equivalente a la anterior, solo se debe modificar la dirección a la que apunta el enlace ubicado en el último nodo.

Las operaciones sobre una lista circular resultan más sencillas. Cuando recorremos una lista circular, diremos que hemos llegado al final de la misma cuando nos encontremos de nuevo en el punto de partida; suponiendo que en este punto se deja un puntero fijo. Otra solución al problema anterior sería ubicar en cada lista circular un **elemento especial identificable**, como lugar de parada. Este elemento especial recibe el nombre de **cabeza de la lista**. Esto presenta la ventaja de que la lista circular no estará nunca vacía.

Listas Doblemente Enlazadas

Una lista doblemente enlazada es una lista lineal en la que cada elemento tiene dos enlaces: uno al elemento **siguiente** y otro al elemento **anterior**.

Esto permite recorrer la lista en cualquier dirección.

Las operaciones sobre una lista doblemente enlazada se realizan sin ninguna dificultad. Sin embargo, casi siempre es mucho más fácil la manipulación de las mismas cuando se añade un elemento de cabeza y existe un doble enlace entre el último elemento y el primero. Esta estructura recibe el nombre de **lista circular doblemente enlazada**.

Colas (Primero en Entrar, Primero en Salir - FIFO)

Una cola es un tipo especial de lista abierta en la que solo se pueden insertar nodos en uno de los extremos de la lista (la parte trasera o *rear*) y solo se pueden eliminar nodos en el otro (la parte frontal o *front*).

• Como sucede con las pilas, las escrituras de datos siempre son **inserciones de nodos**, y las lecturas siempre **eliminan el nodo leído**.
• Todos los *buffers* aplican algoritmos de colas.
• Una vez en la cola, no se puede usar hasta que termine su turno.
• La fila es estática, la cola no (son **dinámicas**).

Pilas (Primero en Entrar, Último en Salir - LIFO)

Para la pila necesitaremos un puntero que se llama **tope** y lo vamos a utilizar para saber la siguiente posición de la pila.

• Las pilas tienen tamaño **estático** (su tamaño siempre es conocido).
• Una pila es un tipo especial de lista abierta en la que solo se pueden insertar y eliminar nodos en uno de los extremos de la lista.

Funciones Comunes para Pilas y Colas

• PUSH(): Permite colocar elementos en la cola o pila.
• POP(): Permite sacar elementos de la pila o cola.

Estas operaciones en pilas se conocen específicamente como "push" (insertar) y "pop" (eliminar).

Árbol Binario

Es una estructura **dinámica**, volátil, **secuencial** y **no lineal**.

Es no lineal porque tiene 3 algoritmos de orden distintos:

1. PRE ORDEN: Raíz / Izquierda / Derecha (R/I/D)
2. IN ORDEN: Izquierda / Raíz / Derecha (I/R/D)
3. POST ORDEN: Izquierda / Derecha / Raíz (I/D/R)

La **raíz no se considera nivel**.

Estructura de Nodo (Ejemplo Conceptual)

Struct hoja 
{
val1;
val2;
. 
. 
valn;
struct hoja*izq; 
struct hoja*der; 
}

Conceptos Adicionales

• Puntero anterior/variables/puntero siguiente: Relacionado con estructuras bidireccionales como las listas doblemente enlazadas.
• Lineal: Recorre la estructura en un solo sentido (aplicable a listas simplemente enlazadas).