Operaciones Con Listas

ALGORITMO Y ESTRUCTURA DE DATOS.

* FUNDAMENTO TEORICO:

OBJETIVOS:
* Conocer un poco más de los arreglos con listas
* Aprender las funciones que realiza un arreglo con listas
* Reconocer un arreglo con listas.

OPERACIONES CON LISTAS
¿QUE ES UNA LISTA?
En Ciencias de la Computación, una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada paraimplementar 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 lamemoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato auto referenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dichopunto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos yaconstruidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
Utilización de las listas
Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puedeser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.
A veces, las listas enlazadas son usadas paraimplementar vectores asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas máseficientemente para recorrer ésta serie de datos.

Las listas son unas estructuras de datos muy útiles para los casos en los que se necesita almacenar información de la que no se conoce su tamaño con antelación.
También son valiosas para las situaciones en las que el volumen de datos se puede incrementar o decrementar dinámicamente durante la ejecución del programa.

Ventajas
Como muchasopciones en programación y desarrollo, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. He aquí una lista con algunas de las ventajas más comunes que implican las estructuras de tipo lista. En general, teniendo una colección dinámica donde los elementos están siendo añadidos y eliminadosfrecuentemente e importa la localización de los nuevos elementos introducidos se incrementa el beneficio de las listas enlazadas.

Listas Enlazadas vs. Vectores o Matrices
| Vector | Lista Enlazada |
Indexado | O(1) | O(n) |
Inserción / Eliminación al final | O(1) | O(1) or O(n)[2] |
Inserción / Eliminación en la mitad | O(n) | O(1) |
Persistencia | No | Simples sí |
Localidad | Buena |...