simone pepe

Concepto.

Una lista es una estructura de datos homogénea y dinámica, que va a estar formada por una secuencia de elementos, donde cada uno de ellos va seguido de otro o de ninguno.
Homogénea: Todos los elementos que la forman tienen el mismo tipo base
Dinámica: Puede crecer o decrecer en tiempo de ejecución según nuestras necesidades. Dos listas pueden ser diferentes si:
No tienen elmismo número de elementos:
L1: gato, perro.
L2: gato, canario, cerdo.

Cuando, aun teniendo el mismo número de elementos, estos son distintos:
L1: gato, perro.
L2: gato, cerdo.

Cuando, aun teniendo el mismo número de elementos y siendo estos los mismos, no están dispuestos en el mismo orden.
L1: gato, perro.
L2: perro, gato. 

Hay varios criterios para clasificar las listas: según su modode acceso o según su información de acceso.

Modo De Acceso.

Atendiendo a este, se dividen en densas y enlazadas. El modo de acceso es independiente de la implementación realizada.

Listas densas
Se caracterizan porque los elementos siguen una secuencia física. Sabemos cuales es el siguiente elemento porque para acceder a él hemos tenido que pasar por todos los anteriores. La localizaciónde un elemento cualquiera será:
El primero si es el primer elemento de la lista.
N-esimo si para llegar a el hemos pasado por N-1 elementos.
Siguen una estructura física secuencial luego se pueden implementar utilizando ficheros, ARRAYS y punteros.

Listas enlazadas
Son aquellas en las que cada elemento que los compone contiene la información necesaria para acceder al elemento siguiente. Lalocalización de un elemento cualquiera será:
Un elemento de la lista tendrá la dirección K si K es el primero y K es conocido (dirección de inicio).
Estará en la dir. J si J está contenida en el elemento anterior.
Informacion de acceso.
Listas ordinales
Los elementos se van colocando en la lista a medida que llegan y se identifican por el orden de llegada .El acceso a un elemento es por suorden o posición relativa dentro de la lista.

Listas calificadas
Los elementos se clasifican por una clave y pueden estar ordenados o no estarlo. A un elemento se accede por la información contenida en un campo clave.
Diferencias: En la primera clase importa en orden de llegada, mientras que en la segunda depende de la clave.


Otros Tipos De Listas
Listas reorganizables.- Son aquellaslistas en las que el último elemento consultado se sitúa al principio.
Listas circulares.- En ellas el último elemento apunta al primero.
Listas doblemente enlazadas.- Cada elemento tiene dos punteros, uno de los cuales apunta al elemento siguiente y otro al anterior.
Listas circulares doblemente enlazadas


La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodosse 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 y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista.
Cuando elpuntero 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 la práctica no hay límite en cuanto a la complejidad de los datos a almacenar.
Declaraciones de tipos paramanejar 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;
tipoNodo es el tipo para declarar nodos, evidentemente.
pNodo es el tipo para declarar punteros a un nodo....