Estructura de Datos: UNIDAD 3 ESTRUCTURAS LINEALES ESTÁTICAS Y DINÁMICAS

3.1 Estructura Datos Pilas
3.2 Estructura Datos Colas
3.3 Listas Enlazadas
3.3.1 Lista Enlazada Simples
3.3.2 Lista Enlazada Dobles

3.1 Estructura Datos Pilas
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como "push" y "pop", respectivamente "empujar" y "tirar". Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.
El ejemplo del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
El nodo típico para construir pilas es:

struct nodo {
int dato;
struct nodo *siguiente;
};

Los tipos que definiremos normalmente para manejar pilas serán casi los mismos que para manejar listas, tan sólo cambiaremos algunos nombres:

typedef struct _nodo {

int dato;
struct _nodo *siguiente;}
tipoNodo; typedef tipoNodo *pNodo;
typedef tipoNodo *Pila;

tipoNodo es el tipo para declarar nodos, evidentemente.
· pNodo es el tipo para declarar punteros a un nodo.
· Pila es el tipo para declarar pilas.

3.2 Estructura Datos Colas
Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.
El ejemplo cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada

3.3 Listas Enlazadas
La lista enlazada que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.
En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.
Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:
Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista. Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:

Insertar un nodo al inicio.
Insertar un nodo antes o después de cierto nodo.
Insertar un nodo al final.
Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:

Eliminar el primer nodo.
Eliminar el último nodo.
Eliminar un nodo con cierta información.
Eliminar el nodo anterior o posterior al nodo cierta con información.
Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar

3.3.2 Listas enlazadas Simples
Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de 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. Aunque normalmente a la variable de referencia se la suele llamar top, usted puede elegir el nombre que quiera. La siguiente figura presenta una lista de enlace simple de tres nodos, donde top referencia al nodo A, A conecta con B y B conecta con C y C es el nodo final:

Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porue tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlace simple no existe

3.3.2 Lista Enlazada Dobles
Una lista doble, ó doblemente ligada es una colección de nodos en la cual cada nodo tiene dos punteros, uno de ellos apuntando a su predecesor (li) y otro a su sucesor(ld). Por medio de estos punteros se podrá avanzar o retroceder a través de la lista, según se tomen las direcciones de uno u otro puntero.
La estructura de un nodo en una lista doble es la siguiente:
Existen dos tipos de listas doblemente ligadas:
Listas dobles lineales. En este tipo de lista doble, tanto el puntero izquierdo del primer nodo como el derecho del último nodo apuntan a NIL.

Listas dobles circulares. En este tipo de lista doble, el puntero izquierdo del primer nodo apunta al último nodo de la lista, y el puntero derecho del último nodo apunta al primer nodo de la lista.
Debido a que las listas dobles circulares son más eficientes, los algoritmos que en esta sección se traten serán sobre listas dobles circulares.
En la figura siguiente se muestra un ejemplo de una lista doblemente ligada lineal que almacena números: