listas
definicion 
Una lista es una estructura de datos secuencial.

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 que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores 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

 CARACTERISTICAS

La cantidad reservada de almacenamiento para la pila o la cola es fija. Vimos pilas y colas alojadas en arreglos.

Problemas al insertar o eliminar elementos.

Una representación secuencial, refleja el orden lógico de los elementos físicamente almacenados en la lista; el orden físico y lógico son los mismos.

Solución a los problemas de movimiento de los datos que se ha encontrado al utilizar representaciones secuenciales.

Con la representación no secuencial el orden lógico y el orden físico de los elementos no es necesario que sea el mismo.

El orden lógico se representa de tal forma que cada elemento apunta al siguiente elemento, es decir, se encuentran ligados

   CLACIFICACION

lista densa: la propia estructura determina cuál es el siguiente elemento de la lista. Ejemplo: un array.

lista enlazada: la posición del siguiente elemento de la estructura la determina el elemento actual. Es necesario almacenar al menos la posición de memoria del primer elemento. Además es dinámica, es decir, su tamaño cambia durante la ejecución del programa.

Una lista enlazada se puede definir recursivamente de la siguiente manera:

una lista enlazada es una estructura vacía o
- un elemento de información y un enlace hacia una lista (un nodo).

 Implementación

Para representar en lenguaje C esta estructura de datos se utilizarán punteros, un tipo de datos que suministra el lenguaje. Se representará una lista vacía con la constante NULL. Se puede definir la lista enlazada de la siguiente manera:

struct lista

{

 int clave;

struct lista *sig;

};

Listas ordenadas 

Las listas ordenadas son aquellas en las que la posición de cada elemento depende de su contenido. Por ejemplo, podemos tener una lista enlazada que contenga el nombre y apellidos de un alumno y queremos que los elementos -los alumnos- estén en la lista en orden alfabético.

struct lista *L;

L = NULL; 

 Cabecera ficticia y centinela

Como se ha observado anteriormente, a la hora de insertar o actualizar elementos en una lista ordenada o reorganizable es fundamental actualizar el primer elemento de la lista cuando sea necesario. Esto lleva un coste de tiempo, aunque sea pequeño salvo en el caso de numerosas inserciones y borrados. Para subsanar este problema se utiliza la cabecera ficticia.

 

Se declara una lista vacía con cabecera, reservando memoria para la cabecera, de la siguiente manera:

struct lista {

  int clave;

  struct lista *sig;

}

...

struct lista *L;

L = (struct lista *) malloc(sizeof(struct lista));

L->sig = NULL;

Listas doblemente enlazadas

Son listas que tienen un enlace con el elemento siguiente y con el

anterior. Una ventaja que tienen es que pueden recorrerse en ambos sentidos, ya sea para efectuar una operación con cada elemento o para insertar/actualizar y borrar. La otra ventaja es que las búsquedas son algo más rápidas puesto que no hace falta hacer referencia al elemento anterior. Su inconveniente es que ocupan más memoria por nodo que una lista simple.

Listas circulares

Las listas circulares son aquellas en las que el último elemento tiene un enlace con el primero. Su uso suele estar relacionado con las colas, y por tanto su desarrollo se realizará en el tema de colas. Por supuesto, se invita al lector a desarrollarlo por su cuenta.