Listas Simples

Es un conjunto de elementos de un tipo dado que se encuentran ordenados y pueden variar en número. Esta es una definición general, que incluye los ficheros y vectores.

Las entradas de una guía o directorio telefónico, por ejemplo, están en líneas sucesivas, excepto en las partes superior e inferior de cada columna. Una lista lineal se almacena en la memoria principal de una computadora en posiciones sucesivas de memoria; cuando se almacenan en cinta magnética, los elementos sucesivos se presentan en sucesión en la cinta. Esta asignación de memoria se denomina almacenamiento secuencial. Posteriormente, se verá que existe otro tipo de almacenamiento denominado encadenado o enlazado.

Una lista lineal se almacena en la memoria de la computadora en posiciones sucesivas o adyacentes y se procesa como un array unidimensional. En este caso, el acceso a cualquier elemento de la lista es fácil; sin embargo, la inserción o borrado requiere un desplazamiento de lugar de los elementos que le siguen y en consecuencia el diseño de un algoritmo específico.

Para permitir operaciones con las listas como arrays se deben dimensionar éstos con tamaño suficiente para que contengan todos los posibles elementos de la lista.

La inserción o eliminación de un elemento, excepto en la cabecera o final de la lista, necesita una traslación de un parte de los elementos de la misma: la que precede o sigue a la posición del elemento modificado.

Las operaciones directas de añadir y eliminar se efectúan únicamente en los extremos de la lista. Esta limitación es una de las razones por las que esta estructura es poco utilizada.

OPERACIONES CON LAS LISTAS SIMPLEMENTE ENLAZADAS

Las operaciones que se pueden realizar con listas lineales contiguas son:

1. Insertar, eliminar o localizar un elemento.

2. Determinar el tamaño – número de elementos – de la lista.

3. Recorrer la lista para localizar un determinado elemento.

4. Clasificar los elementos de la lista en orden ascendente o descendente.

5. Unir dos o más listas en una sola.

6. Dividir una lista en varias sublistas.

7. Copiar la lista.

8. Borrar la lista.

LISTAS ENLAZADAS

Las listas enlazadas o de almacenamiento enlazado son mucho más flexibles y potentes, y su uso es mucho más amplio que la lista contigua.

Una lista enlazada o encadenada es un conjunto de elementos en los que cada elemento contiene la posición o dirección del siguiente elemento de la lista.

Cada elemento de la lista enlazada debe tener al menos dos campos: un campo que tiene el valor del elemento y un campo (enlace, link) que contiene la posición del siguiente elemento, es decir, su conexión, enlace o encadenamiento. Los elementos de una lista son enlazados por medio de los campos enlaces

Una lista enlazada sin ningún elemento se llama lista vacía. Su puntero inicial o de cabecera tiene el valor nulo (NULL).

Una lista enlazada se define por:

· El tipo de sus elementos: campo de información (datos) y campo enlace (puntero).

· Un puntero de cabecera que permite acceder al primer elemento de la lista.

· Un medio para detectar el último elemento de la lista: puntero nulo (NULL).

Representacion Grafica