Listas Enlazadas

LAS ESTRUCTURAS LISTAS ENLAZADAS


Las estructuras enlazadas de datos son fundamentales para el desarrollo de software, especialmente en el diseño e implementación de colecciones.

Una estructura enlazada es una estructura de datos que utiliza variables de referencia a objetos con el fin de crear enlaces entre objetos.

Una variable de referencia a objeto almacena la dirección de unobjeto, que indica donde esta almacenado en la memoria.

Considere una situación en la que una clase definida como dato, instancia una referencia a otro objeto de la misma clase. Por ejemplo, suponga que tenemos una clase denominada Person que contiene el nombre, la dirección y otra informacion relevantes acerca de una persona y además también contiene una variable de referencia a otro objeto Person.Public class Person
{
Private String name;
Private String address;

Private Person next; // un enlace a otro objeto Person

//resto del código

}

Utilizando exclusivamente esta clase, podemos crear una estructura enlazada. Cada objeto Person contendrá un enlace a un segundo objeto Person. Este segundo objeto también contendrá una referencia a un objeto Person, que a su vezcontendrá otra, etc Este tipo de objetos se denomina en ocasiones auto-referencial.

Este tipo de relación forma la base de lo que se denomina lista enlazada, que es una estructura enlazada en la que cada objeto hace referencia al siguiente, creando una ordenación lineal de los objetos de la lista.

Los objetos almacenados en una lista se denominan, de modo genérico, nodos de la lista.

Unalista enlazada esta compuesta de objetos, cada uno de los cuales apunta al siguiente objeto en la lista.

A diferencia de las matrices, que tiene un tamaño fijo, las listas enlazadas no tienen ningún límite superior en lo que respecta a su capacidad, salvo las limitaciones de memoria de la propia computadora. Una lista enlazada se considera como una estructura dinámica, porque su tamaño crece y secontrae según sea necesario para albergar todos los elementos que haya que almacenar.

En java todos los objetos se crean dinámicamente a partir de un área de memoria denominada cúmulo del sistema o almacén de espacio libre.

Al crear la lista insertamos los elementos por la cabeza.

Cuando insertamos nuevos nodos podemos hacerlo por la cabeza o en cualquier posición de la lista.

En laLista enlazada la colección de elementos (denominados nodos) estan dispuestos uno a continuación del otro, y cada uno de ellos conectados al siguiente elemento por un enlace o referencia.

La primera parte o campo contiene información y es por consiguiente una valor de tipo genérico (denominada dato, Tipo Elemento, Info, etc) y la segunda parte o campo es una referencia (denominada enlace osiguiente) que apunta al siguiente elemento de la lista.


[pic]
El primer nodo se enlaza al segundo, el segundo nodo se enlaza al tercero y así sucesivamente hasta llegar al último

El final se identifica como el nodo cuyo campo referencia tiene el valor null.

La lista se recorre desde el primero al ultimo nodo, en cualquier punto del recorrido la posición actual se referencia por lareferencia actual

En caso de que la lista no contenga ningún nodo (esta vacía), la cabeza es nulo

Operaciones con listas

Definición de la clase nodo y referencia a nodo
Inicialización o creación de la lista
Insertar elementos en una lista
Eliminar elementos de una lista
Buscar elementos de una lista
Recorrer una lista enlazada (visitar cada nodo de la lista)
Comprobar que la lista estavacía.


Definición de un nodo

Cada nodo es una combinación de dos partes: un tipo de dato (entero, doble, carácter o referencia) y un enlace al siguiente nodo

Class nodo
{
Int dato

}

La construcción y manipulación de una lista requiere el acceso a los nodos de la lista a través de una o más referencia a nodos. Normalmente se incluye una refencia al primer nodo (cabeza) y una...