Una lista
enlazada es una colección de elementos
que se encuentran situados uno
tras otro, los cuales están conectados
consecutivamente por una referencia.
En esa grafica podemos apreciar de la manera más simple las conexiones de los elementos (nodos) uno tras otro.
Declaración de un nodo
Consiste en
elementos llamados nodos, que se componen de las siguientes partes la primera
parte contiene la información, valores genéricos dato o tipo de elemento son
los campos, la segunda parte es la referencia (denominada sgte) que enlaza al
siguiente elemento de la lista.
En esa grafica podemos apreciar de la manera más simple las conexiones de los elementos (nodos) uno tras otro.
La lista
simplemente enlazada cada nodo contiene un solo enlace que lo conecta al nodo
siguiente, es muy eficiente en recorridos directos.
La forma más común de representar las listas
enlazadas, es la que tenemos a continuación donde el primer nodo de la lista
apunta a la cabeza, las lista enlaza nodos desde el frente al final (cola) de
la lista, el nodo final su campo es null. La lista se recorre desde el primer
al último nodo, En cualquier punto del recorrido la posición actual se
referencia por el puntero actual, una lista vacía no contiene nodos se
representa con el puntero cabeza con null.
Operaciones que se realizan con una
lista enlazada
Las operaciones basicas que se realizan en una lista enlzadas son:
Las operaciones basicas que se realizan en una lista enlzadas son:
1. Insertar: al comienzo, despues y
final de la lista.
2. visualizar los elementos de la lista
3. eliminar: se elimina el nodo con el
valor que coincida con la referencia.
4. editar : se edita con el valor
de nodo que indica la referencia
5. contar elementos de la lista.
6. buscar: devuelve true si el valor
existe y false si es lo contrario.
7. Encontrar el valor mayor
8. Ordenar lista
Declaración de un nodo
Para
comenzar se debe declarar un nodo, con sus dos partes las cuales se combinarán
el dato (puede ser entero, doble, carácter) y el enlace correspondiente.
Creamos una
clase donde tendremos las dos partes de un nodo, el dato y el enlace, la lista enlazada en
este caso será de números enteros.
package
Entidades;
public class
Nodo
{
{
int dato;
Nodo enlace;
public Nodo(int n)
{
{
dato = n;
enlace = null;
}
Como podemos
fijarnos en el constructor Nodo se inicializa el objeto a un dato y el enlace a
null. La visibilidad de los campos del nodo es por defecto public para
que pueda ser usado en el mismo paquete todas las operaciones.
Construcción
de una lista
La clase
lista define primero el atributo cabeza, referencia el nodo para acceder a los
elementos de la lista, el constructor inicializa primero lista vacía (null).
Declaracion
de la clase Lista Simple:
public class
ListaEnlazadaSimple {
private Nodo cab; // Puntero que
indica el inicio de la lista se conoce como cabeza de la lista.
public ListaEnlazadaSimple()
{
cab=null;
}
}
}
Consultar si
la lista está vacía: Retorna true
si el primero nodo no apunta a otro nodo.
public boolean estaVacia() {
boolean vacia = false;
if (cab == null) {
vacia =
true;
}
return vacia;
}
Insertar por
la cabeza o inicio: Se define un
nuevo nodo agregando un valor, luego se consulta si la lista esta vacía, en
caso de estarlo se inicializa la lista añadiendo como cabecera al nuevo nodo,
caso contrario se va agregando los nodos al inicio de la lista, retorna la
referencia this.
public ListaEnlazadaSimple InsertarInicio(int entrada) {
Nodo nuevo = new Nodo(entrada);
if (estaVacia()) {
cab = nuevo;
} else {
nuevo.sgte = cab;
cab = nuevo;
}
return this;
}
Insertar al
final de la lista: Se define un
nuevo nodo al cual se le agrega el valor entrada, consulta si la lista esta
vacía, si es así se inicializa la cabecera añadiendo un nuevo nodo, caso
contrario recorre la lista hasta llegar al último nodo y se agrega en valor
nuevo, esto se con un método que busca el ultimo nodo.
public ListaEnlazadaSimple InsertarFin(Nodo ultimo, int entrada)
{
Nodo nuevo = new Nodo(entrada);
if (estaVacia()) {
cab = nuevo;
} else {
ultimo.sgte = nuevo;
}
return this;
}
Insertar después
de un Nodo: Se declara
un nuevo nodo al cual se le asigna el valor entrada, luego verifica si el nodo
anterior no está vacío si lo esta se asigna el nodo anterior al siguiente,
luego se inicializa el nodo sgte a un nuevo nodo, en este caso debe existir un
nodo anterior para poder insertar el siguiente nodo.
public ListaEnlazadaSimple InsertarDespues(Nodo anterior, int entrada) {
Nodo nuevo = new Nodo(entrada);
if (anterior.sgte != null) {
nuevo.sgte = anterior.sgte;
}
anterior.sgte = nuevo;
return this;
}
Imprimir la
Lista: Se
inicializa n añadiendo el valor de la cabecera, mientras n no sea un valor
nulo, se va imprimiendo todos los nodos y n va recorriendo los nodos.
public void VisualizarLista()
{
Nodo n;
n= cab;
while(n!=null)
{
JOptionPane.showMessageDialog(null,"[" + n.info +"]=>"
);
n=n.sgte;
}
}
Buscar Nodo:
Se declara
al nodo como índice, luego se recorre la lista por medio de la estructura for
comparando si el valor ingresado es igual a la información de un nodo en caso
de ser positiva la estructura de control retorna el índice.
public Nodo Buscar(int valor) {
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (valor == indice.info) {
return indice;
}
}
return null;
}
Buscar último Nodo: Se declara al nodo como índice, luego se recorre la
lista hasta que índice sea nulo luego retorna índice el cual es el último valor
con el cual se inserta al final.
public Nodo BuscarUltimoNodo()
{
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (indice.sgte == null) {
return
indice;
}
}
return null;
}
public ListaEnlazadaSimple Editar(Nodo nodo, int entrada) {
if (!estaVacia()) {
nodo.info = entrada;
}
return this;
}
Eliminar
Nodo: Elimina una
posición de la lista por medio de un valor ingresado.
public void Eliminar(int valor) {
Nodo actual, anterior;
boolean encontrado;
actual = cab;
anterior = null;
encontrado = false;
while ((actual != null) && (!encontrado))
{
encontrado = (actual.info == valor);
if (!encontrado) {
anterior = actual;
actual = actual.sgte;
}
}
if (actual != null) {
if (actual == cab) {
cab =
actual.sgte;
} else {
anterior.sgte = actual.sgte;
}
actual = null;
}
}
Contar lo
elementos de la lista: Se declara el nodo índice, se declara la variable pos, se recorre la lista
y se va acumulando la variable pos por cada nodo, y retorna pos.
public int Count()
{
Nodo indice;
int pos=0;
for (indice = cab; indice != null; indice =
indice.sgte)
{
pos = pos +1;
}
return pos;
}
Ordenar
Lista: Se puede
utilizar diferentes algoritmos de ordenación, como el de selección.
public void OrdenarSeleccion() {
Nodo indice, subindice; //i2,j
Nodo indiceMenor;
for (indice = cab; indice != null; indice = indice.sgte) {
indiceMenor = indice;
//j explora la sublista lista[i+1]..lista[n-1]
for (subindice = indice.sgte; subindice != null; subindice = subindice.sgte)
{
if (indiceMenor.info > subindice.info )
{
indiceMenor = subindice;
}
}
if (indice != indiceMenor) {
intercambio(indice, indiceMenor);
}
}
}
//método que
utiliza el ordenamiento por selección.
public void intercambio(Nodo i, Nodo j) {
int aux;
aux = i.info;
i.info =
j.info;
j.info = aux;
}
Mayor valor
de la lista: Se
inicializa índice se declara una variable aux con la información de la
cabecera de la lista, se recorre la lista comparando si los valores del
nodo son mayores que la variable aux al cual se le asigna los valores de los
nodos.
public int MayorValor()
{
Nodo indice;
int aux=cab.info;
for (indice = cab; indice != null; indice = indice.sgte)
{
if(indice.info > aux)
{
aux= indice.info;
}
}
return aux;
}
}Ejemplo:
Ejemplos de listas numeros
//Declaración del Nodo
package Entidades;
public class Nodo {
public int info;
public Nodo sgte;
public Nodo(int x)
{
info= x;
sgte = null;
}
public Nodo()
{
}
}
//Declaración de la lista
package Controlador;
import Entidades.Nodo;
public class ListaEnlazadaSimple {
private Nodo cab;
public ListaEnlazadaSimple()
{
cab=null;
}
public boolean estaVacia() {
boolean vacia = false;
if (cab == null) {
vacia = true;
}
return vacia;
}
public ListaEnlazadaSimple InsertarInicio(int entrada) {
Nodo nuevo = new Nodo(entrada);
if (estaVacia()) {
cab = nuevo;
} else {
nuevo.sgte = cab;
cab = nuevo;
}
return this;
}
public ListaEnlazadaSimple InsertarFin(Nodo ultimo, int entrada)
{
Nodo nuevo = new Nodo(entrada);
if (estaVacia()) {
cab = nuevo;
} else {
ultimo.sgte = nuevo;
}
return this;
}
public ListaEnlazadaSimple InsertarDespues(Nodo anterior, int entrada) {
Nodo nuevo = new Nodo(entrada);
if (anterior.sgte != null) {
nuevo.sgte = anterior.sgte;
}
anterior.sgte = nuevo;
return this;
}
public void VisualizarLista()
{
Nodo n;
n= cab;
while(n!=null)
{
System.out.print("[" + n.info +"]=>" );
n=n.sgte;
}
}
public Nodo Buscar(int valor) {
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (valor == indice.info) {
return indice;
}
}
return null;
}
public Nodo BuscarUltimoNodo()
{
Nodo indice;
for (indice = cab; indice != null; indice = indice.sgte)
{
if (indice.sgte == null) {
return indice;
}
}
return null;
}
public ListaEnlazadaSimple Editar(Nodo nodo, int entrada) {
if (!estaVacia()) {
nodo.info = entrada;
}
return this;
}
public void Eliminar(int valor) {
Nodo actual, anterior;
boolean encontrado;
actual = cab;
anterior = null;
encontrado = false;
while ((actual != null) && (!encontrado))
{
encontrado = (actual.info == valor);
if (!encontrado) {
anterior = actual;
actual = actual.sgte;
}
}
if (actual != null) {
if (actual == cab) {
cab = actual.sgte;
} else {
anterior.sgte = actual.sgte;
}
actual = null;
}
}
public int Count()
{
Nodo indice;
int pos=0;
for (indice = cab; indice != null; indice = indice.sgte)
{
pos = pos +1;
}
return pos;
}
public void OrdenarSeleccion() {
Nodo indice, subindice; //i2,j
Nodo indiceMenor;
for (indice = cab; indice != null; indice = indice.sgte) {
indiceMenor = indice;
//j explora la sublista lista[i+1]..lista[n-1]
for (subindice = indice.sgte; subindice != null; subindice = subindice.sgte)
{
if (indiceMenor.info > subindice.info )
{
indiceMenor = subindice;
}
}
if (indice != indiceMenor) {
intercambio(indice, indiceMenor);
}
}
}
public void intercambio(Nodo i, Nodo j) {
int aux;
aux = i.info;
i.info = j.info;
j.info = aux;
}
public int MayorValor()
{
Nodo indice;
int aux=cab.info;
for (indice = cab; indice != null; indice = indice.sgte)
{
if(indice.info > aux)
{
aux= indice.info;
}
}
return aux;
}
}
//Método main
package applistasenlazadassimple;
import Controlador.ListaEnlazadaSimple;
/**
*
* @author Wilson Belduma
*/
public class AppListasEnlazadasSimple {
public static void main(String[] args) {
ListaEnlazadaSimple Lista= new ListaEnlazadaSimple();
Lista.InsertarInicio(1);
Lista.InsertarFin(Lista.BuscarUltimoNodo() , 2);
Lista.InsertarInicio(3);
Lista.InsertarFin(Lista.BuscarUltimoNodo(), 4);
Lista.VisualizarLista();//visualiza elementos insertados al inicio y al final
Lista.InsertarDespues(Lista.Buscar(1), 5);
Lista.VisualizarLista();
///Lista.Editar(Lista.Buscar(4), 44);
System.out.println();
System.out.println("lista ordenada");
Lista.OrdenarSeleccion();
Lista.VisualizarLista();//visualiza lista ordenada
System.out.println();
System.out.println("Cantidad de elementos"+Lista.Count());
System.out.println("El mayor valor es :" + Lista.MayorValor());
}
}
No hay comentarios.:
Publicar un comentario