Listas Enlazadas...

LISTAS ENLAZADA

¿QUE ES UNA LISTA ENLAZADA?
Es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada
elemento se conecta al siguiente elemento por un “enlace” o “puntero”.

Una lista enlazada o estructura ligada, es una estructura lineal que almacena una colección
de elementos generalmente llamados nodos, en donde cada nodo puede almacenar datos y
ligas aotros nodos. De esta manera los nodos pueden localizarse en cualquier parte de la
memoria, utilizando la referencia que lo relaciona con otro nodo dentro de la estructura.
Las listas enlazadas permiten almacenar información en posiciones de memoria que no sean
contiguas; para almacenar la información contienen elementos llamados nodos. Estos nodos
poseen dos campos uno para almacenar lainformación o valor del elemento y otro para el
enlace que determina la posición del siguiente elemento o nodo de la lista.
El principal beneficio de las listas enlazadas respecto a los array 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 dealmacenamiento.
Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link
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 dicho punto está
previamente identificado o localizado), pero no permiten un acceso aleatorio.
Las listas enlazadas pueden serimplementadas en muchos lenguajes. Lenguajes tales como
Lisp y Scheme tiene estructuras de datos ya construidas, 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.

CARACTERISTICAS
La lista debe estar ordenada.
A diferencia de las pilas y las colas sepueden extraer e insertar elementos en
cualquier parte de la lista.
Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados
que permitan la manipulación de los datos que contiene. Los operadores básicos de una
lista enlazada son:



Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al
principio o final de la lista o bienen orden.



Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.



Buscar: busca un elemento en la lista.



Localizar: obtiene la posición del nodo en la lista.



Vaciar: borra todos los elementos de la lista

VENTAJAS Y DESVENTAJAS SOBRE LOS ARREGLOS
Como muchas opciones en programación y desarrollo, no existe un único método correcto
pararesolver 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 eliminados frecuentemente e importa la
localización de los nuevos elementosintroducidos se incrementa el beneficio de las listas
enlazadas

VENTAJAS SOBRE LOS ARREGLOS:
Los elementos se pueden insertar en una lista indefinidamente mientras que un arreglo tarde
o temprano se llenará o necesitará ser redimensionado, una costosa operación que incluso
puede no ser posible si la memoria se encuentra fragmentada.

DESVENTAJAS SOBRE LOS ARREGLOS:

Las listas son de accesosecuencial, y sólo puede ser recorrida en una dirección.
El acceso secuencial es más lento en las listas.
Se requiere de almacenamiento extra para las referencias
Puede resultar lento asignar memoria para cada nuevo elemento.

TIPOS DE LISTAS ENLAZADAS
LISTAS ENLAZADAS SIMPLES:

Una lista de enlace simple es una lista enlazada de nodos, donde cada nodo tiene un único
campo de enlace. Una...