Listas

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 el mismonú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 modo deacceso 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ón de unelemento 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. La localizaciónde 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 su orden o posiciónrelativa 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.
Pilas.
Una pila es una lista ordinal en la que el modo de acceso a sus elementos esdel tipo LIFO. Los añadidos y extracciones de elementos de una estructura se realizan solo por un extremo, luego el único elemento accesible de la pila es el que se encuentre en la cima. Esto exigirá que la manipulación sobre un elemento, necesite que el mismo ocupe la posición de cima.
Sobre una estructura de tipo pila, surgen de forma natural las operaciones que permiten añadir elementos yquitar elementos.
Implementación utilizando tablas 
Esta realización consiste en ir guardando consecutivamente los elementos de la pila en un vector de tamaño fijo. Un índice marcará la posición del último elemento que se ha añadido a la pila. Por tanto, las inserciones en la estructura se realizarán en la posición inmediatamente siguiente a la posición marcada como cima, pasando a ser esta nuevaposición ocupada la nueva cima de la pila.
El hecho de utilizar un vector para almacenar los elementos, puede conducir a la situación en que la pila esté llena, es decir, que no quepa ningún elemento más. Esto se producirá cuando el índice que señala la cima de la pila sea igual al tamaño del vector.
Otros Tipos De Listas
Listas reorganizables.- Son aquellas listas en las que el último elementoconsultado 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





LISTA ENLAZADA LINEAL (SIMPLE)


Una lista enlazada simple contiene dos valores; el valor actual del nodo y un...