Listas y colas en c++

Universidad Mariano Gálvez
Ing. Francisco Aroche
Estructuras de Datos

Investigación de Pilas, Colas, Listas y funciones de C

José Alberto Contreras Dávila
1890-08-499

Listas
En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los quese guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una listaenlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista EnlazadasSimples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Lista Enlazadas Simples
Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero.
La asignación de memoria es hecha durante la ejecución.

En una lista los elementos son contiguos en loque concierne al enlazado.

En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos.
El enlace entre los elementos se hace mediante un puntero.
En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
El desplazamiento se hace en una sola dirección, del primer al último elemento.
Si deseas desplazarte en las dos direcciones (hacia delante y hacia atrás) deberás utilizar las [ listas doblemente enlazadas]
Construcción del modelo de unelemento de la lista
Para definir un elemento de la lista, será utilizado el tipo struct.
El elemento de la lista contendrá un campo dato y un puntero siguiente.
El puntero siguiente debe ser del mismo tipo que el elemento, si no, no podrá apuntar hacia el elemento.
El puntero siguiente permitirá el acceso al próximo elemento.
typedef struct ElementoLista {char *dato;
struct ElementoLista *siguiente;
}Elemento;

Para tener el control de la lista es preferible guardar ciertos elementos:
El primer elemento, el último elemento, el número de elementos.

Para ello será utilizado otra estructura (no es obligatorio, pueden ser utilizadas variables)
typedef struct ListaIdentificar {Elemento *inicio;
Elemento *fin;
int tamaño;
}Lista;

El puntero inicio contendrá la dirección del primer elemento de la lista.
El puntero fin contendrá la dirección del último elemento de la lista.
La variable tamaño contiene el número de elementos.

Cualquiera que sea la posición en la lista, los punteros inicioy fin apuntan siempre al primer y último elemento.
El campo tamaño contendrá el numero de elementos de la lista cualquiera que sea la operación efectuada sobre la lista.

Inserción y la eliminación
Para la inserción y la eliminación, una solo función bastará si está bien concebida de acuerdo a lo que se necesite.
Debo recordar que este artículo es puramente didáctico.
Por esta razón he...