Pilas Colas Y Listas Definiciones Y Ventajas

 
Listas abiertas
Definición
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL. En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo o llamaremosa ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista. Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía. El nodo típico para construir listas tiene esta forma:
struct nodo {int dato; struct nodo *siguiente;};
En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en lapráctica no hay límite en cuanto a la complejidad de los datos a almacenar.
Declaraciones de tipos para manejar listas en C:
Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta:
typedef struct _nodo {int dato; struct _nodo *siguiente;} tipoNodo; typedef tipoNodo *pNodo;typedef tipoNodo *Lista;
tipoNodoes el tipo para declarar nodos, evidentemente .pNodo es el tipo para declarar punteros a un nodo. Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo apuntado
 Es muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, yaque si no existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el espacio de memoria que ocupa.
Operaciones básicas con listas:
Con las listas tendremos un pequeño repertorio de operaciones básicas que se pueden realizar:
• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
Moverse a través de unalista, anterior, siguiente, primero. Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar un nodo en una lista vacía, o al principio de una lista no vacía, ola final, o en una posición intermedia.

Insertar elementos en una lista abierta
Veremos primero los casos sencillos y finalmente construiremos un algoritmo genérico para la inserción de elementosen una lista.
Insertar un elemento en una lista vacía
Este es, evidentemente, el caso más sencillo. Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además el puntero a la lista valdrá NULL: El proceso es muy simple, bastará con que:
1. nodo->siguiente apunte a NULL.
2. Lista apunte a nodo.
Insertar un elemento en la primera posición de una listaPodemos considerar el caso anterior como un caso particular de éste, la única diferencia es que en el caso anterior la lista es una lista vacía, pero siempre podemos, y debemos considerar una lista vacía como una lista.
Añadir elemento en una lista doblemente enlazada, caso general:
Para generalizar todos los casos anteriores, sólo necesitamos añadir una operación:

1. Si lista está vacíahacemos que Lista apunte a nodo. Y nodo->anterior y nodo->siguiente a NULL.
2. Si lista no está vacía, hacemos que nodo->siguiente apunte a Lista->siguiente.
3. Después que Lista->siguiente apunte a nodo.
4. Hacemos que nodo->anterior apunte a Lista.
5. Si nodo->siguiente no es NULL, entonces hacemos que nodo->siguiente->anterior apunte a nodo.

El paso 1 es equivalente a insertarun nodo en una lista vacía.

Los pasos 2 y 3 equivalen a la inserción en una lista enlazada corriente.

Los pasos 4, 5 equivalen a insertar en una lista que recorre los nodos en sentido contrario.

Existen más casos, las listas doblemente enlazadas son mucho más versátiles, pero todos los casos pueden reducirse a uno de los que hemos explicado aquí.


1 Buscar o localizar un elemento de...