viernes, 15 de octubre de 2021
martes, 22 de octubre de 2019
Lista Doblemente Enlazadas
La diferencia entre las listas simplemente enlazada y las doblemente enlazada
como podemos observar en la imagen anterior de 12 apunta a nulo, siguiente de 12 apunta a anterior de 57 inicio de 57 apunta a anterior de 95 y siguiente de 95 apunta a nulo, anterior de 95 apunta a siguiente de 57 y anterior de 57 apunta a siguiente de 12
a continuación les mostrare el siguiente ejercicio de lista doblemente enlazadas
Es que las doblemente enlazada contiene dos punteros uno apunta al nodo siguiente y otro apunta al nodo anterior y en la simplemente enlazada solo contiene un puntero
para explicar mejor las listas doblemente enlazada observemos el siguiente ejemplo
como podemos observar en la imagen anterior de 12 apunta a nulo, siguiente de 12 apunta a anterior de 57 inicio de 57 apunta a anterior de 95 y siguiente de 95 apunta a nulo, anterior de 95 apunta a siguiente de 57 y anterior de 57 apunta a siguiente de 12
a continuación les mostrare el siguiente ejercicio de lista doblemente enlazadas
ALGORITMOS DE LA CLASE LISTA
Declaramos dos variables que son inicio y fin
de tipo privadas
Luego creamos un constructor
Donde inicio es igual a fin igual a nulo
·
Algoritmo
para saber si la lista está vacía
Método de tipo booleano
Retornamos inicio igual de igual de nulo
*Donde
retornamos verdadero porque la lista esta vacía
·
Algoritmo
para agregar nodo al final
Método tipo void
Si no está vacía
Fin igual a nuevo (elemento, nulo, fin)
Fin de anterior de siguiente igual fin
Entonces
Inicio igual fin igual nuevo (elemento)
·
Algoritmo
para agregar nodo al inicio
Método tipo void
Si no está vacía
Inicio igual nuevo (elemento, inicio, nulo)
Inicio de siguiente de anterior igual inicio
Entonces
Inicio igual fin igual nuevo (elemento)
·
Algoritmo
para mostrar la lista de inicio a fin
Método void
Si no está vacía
Nodo Doble auxiliar igual inicio
Mientras (auxiliar no es igual a nulo)
Datos igual datos más auxiliar de datos
Auxiliar igual auxiliar de siguiente
·
Algoritmo
para mostrar fin de inicio
Método void
Si no está vacía
Nodo Doble auxiliar igual fin
Mientras (auxiliar no es igual a nulo)
Datos igual datos más auxiliar de datos
Auxiliar igual auxiliar de anterior
package
listadoblemente;
import
javax.swing.JOptionPane;
public class ListaDoble {
private NodoDoble inicio,fin;
//CONSTRUCTOR DE LA LISTA
public ListaDoble (){
inicio=fin=null;
}
//METODO PARA SABER SI LA LISTA ESTA VACIA
public boolean estaVacia (){
return inicio == null;
}
//METODO PARA AGREGAR UN NODO AL FINAL
public void agregarAlFinal(int el){
if(!estaVacia()){
fin=new NodoDoble(el,null,fin);
fin.anterior.siguiente = fin;
} else {
inicio=fin=new NodoDoble(el);
}
}
//METODO PARA AGREGAR AL INICIO
public void agregarAlInicio(int el){
if(!estaVacia()){
inicio=new
NodoDoble(el,inicio,null);
inicio.anterior.siguiente = inicio;
} else {
inicio=fin=new NodoDoble(el);
}
}
//METODO PARA MOSTRAR DE INICIO A FIN
public void mostrarListaInicioFin(){
if(!estaVacia()){
String
datos="<-->";
NodoDoble auxiliar=inicio;
while(auxiliar!=null){
datos = datos + "[ "
+ auxiliar.dato + " ]" + "<-->";
auxiliar = auxiliar.siguiente;
}
JOptionPane.showMessageDialog(null,
datos, "Mostrando"
+ "Lista de inicio a
fin",JOptionPane.INFORMATION_MESSAGE);
}
}
//METODO PARA MOSTRAR DE FIN A INICIO
public void mostrarListaFinInicio(){
if(!estaVacia()){
String
datos="<-->";
NodoDoble auxiliar=fin;
while(auxiliar!=null){
datos = datos + "[ "
+ auxiliar.dato + " ]" + "<-->";
auxiliar = auxiliar.anterior;
}
JOptionPane.showMessageDialog(null,
datos, "Mostrando"
+ "Lista de fin a
inicio",JOptionPane.INFORMATION_MESSAGE);
}
}
}
ALGORITMOS DE LA CLASE NODOS
Declaramos
dato, siguiente, anterior de tipo entero
Luego
creamos un constructor para inicializar las variables
Dato
igual a elemento
Siguiente
igual de S
Anterior
igual de A
En el
segundo constructor para cuando no haya nodos
Mandamos
a llamar el elemento
Y le
colocamos nulo
Que
nos dice que no tenemos ningún nodo
package listadoblemente;
public class NodoDoble {
public int dato;
NodoDoble
siguiente,anterior;
//CONSTRUCTOR CUANDO
YA HAY NODOS
public NodoDoble(int
el, NodoDoble s, NodoDoble a){
dato = el;
siguiente = s;
anterior = a;
}
//CONSTRUCTOR CUANDO
NO HAY NODOS
public NodoDoble (int
el){
this(el,null,null);
}
}
ALGORITMOS PARA EL MAIN
- Instanciar objeto de la clase lista
- Declarar variables opción/opción y elemento/el
- iniciar variable opción = 0
-hacer
-un do while donde colocamos las opciones y
donde va ir try case
-Controlar errores (try- catch)
-opción va a ser igual a las opciones de menú
(en este caso son 5
opciones)
-menú de opciones con la variable opción (switch)
-realizar cada una de las opciones dentro del
menú
-mientras opción sea diferente del número de
opciones (en este caso 8)
package
listadoblemente;
import
javax.swing.JOptionPane;
public
class ListaDoblemente {
public static void main(String[] args) {
ListaDoble impLista = new ListaDoble();
int opcion=0;
String el;
do{
try{
opcion =
Integer.parseInt(JOptionPane.showInputDialog(null,""
+"1. Agregar
un elemento al final de la lista\n"
+"2. Agregar
un elemento al final de la lista\n"
+"3. Mostrar los elementos de inicio
a fin\n"
+"4. Mostrar
los elementos de fin a inicio\n"
+"5.
Salir","Opciones del programa",3));
switch(opcion){
case 1: //1. Agregar un elemento
al final de la lista
try{
el=JOptionPane.showInputDialog
(
null,
"Ingreso
el elemento",
"Insertando al final",3
);
impLista.agregarAlFinal(el);
}catch(NumberFormatException n){
JOptionPane.showMessageDialog(null, "Error" + n.getMessage());
}
break;
case 2: //2. Agregar un
elemento al inicio de la lista
try{
el=JOptionPane.showInputDialog
(
null,
"Ingreso el elemento",
"Insertando al inicio",3
);
impLista.agregarAlInicio(el);
}catch(NumberFormatException n){
JOptionPane.showMessageDialog(null, "Error" + n.getMessage());
}
break;
case 3: //3. Mostrar los
elementos de inicio a fin
impLista.mostrarListaInicioFin();
break;
case 4: //4. Eliminar un
elementos de fin a inicio
impLista.mostrarListaFinInicio();
break;
default:
JOptionPane.showMessageDialog(null, "Opcion incorrecta");
break;
case 5://5. Salir
JOptionPane.showMessageDialog(null, "Programa terminado...");
break;
}
}catch(Exception e){
JOptionPane.showMessageDialog(null,
"Error"+ e.getMessage());
}
} while (opcion !=5);
}
}
Listas Simplemente enlazadas
Nodo.java
·
Creamos una clase publica llamada nodo
o
Declaramos dato y siguiente
o
Luego creamos un constructor //con diferente parámetro
§
Inicializamos dato = d // d el dato que se tiene
§
Inicializamos siguiente = null // el nodo siguiente
o
Luego declaramos lo siguiente
§
Dato es igual a d
§
Y siguiente es igual a n
package letraslse;
public class Nodo {
public String dato;
public Nodo siguiente;
//CONSTRUCTOR
public Nodo(String d){
this.dato = d;
this.siguiente=null;
}
public Nodo(String d, Nodo n){
dato =d ;
siguiente = n;
}
}
LetrasLSE.java
·
Instanciar objeto de la clase lista
o Declaramos
variable opción opcion y elemento el
o Iniciar
variable opcion = 0
o Hacer
un do while donde colocamos donde colocamos las opciones y donde va a ir
el try case
o Controlar
errores (try – case)
o opción
va a ser igual a las opciones de menú (en este caso son 6 opciones)
o menú
de opciones con la variable opción (switch)
o realizar
cada una de las opciones dentro del menú
§ Agregar
un elemento al inicio de la lista
package letraslse;
import javax.swing.JOptionPane;
import java.lang.String;
public class LetrasLSE {
public static void
main(String[] args) {
Lista impLista = new Lista();
int opcion=0;
String el;
do{
try{
opcion =
Integer.parseInt(JOptionPane.showInputDialog(null,""
+"1. Agregar
un elemento al inicio de la lista\n"
+"2. Agregar un elemento al
final de la lista\n"
+"3. Mostrar
los elementos de la lista\n"
+"4. Eliminar
un elemento del inicio de la lista\n"
+"5. Eliminar
un elemento especifico\n"
+"6.
Salir","Opciones del programa",3));
switch(opcion){
case 1: //1. Agregar un
elemento al inicio de la lista
try{
el=JOptionPane.showInputDialog
(
null,
"Ingreso
el elemento",
"Insertando al inicio",3
);
impLista.agregarAlInicio(el);
}catch(NumberFormatException n){
JOptionPane.showMessageDialog(null, "Error" + n.getMessage());
}
break;
case 2: //2.
Agregar un elemento al final de la lista
try{
el=JOptionPane.showInputDialog
(
null,
"Ingreso
el elemento",
"Insertando al final",3
);
impLista.agregarAlFinal(el);
}catch(NumberFormatException n){
JOptionPane.showMessageDialog(null, "Error" + n.getMessage());
}
break;
case 3: //3. Mostrar los
elementos de la lista
impLista.mostrarLista();
break;
case 4: //4. Eliminar un
elemento del inicio de la lista
el=impLista.borrarDelInicio();
JOptionPane.showMessageDialog
(
null,
"El
elemento eliminado es "+el,
"Eliminando NODO
del inicio",
JOptionPane.INFORMATION_MESSAGE
);
break;
default:
JOptionPane.showMessageDialog(null, "Opcion incorrecta");
break;
case 5://5. Eliminar un elemento
especifico
try{el=JOptionPane.showInputDialog
(
null,
"Ingrese el elemento a eliminar",
"Eliminando
Nodo...",JOptionPane.INFORMATION_MESSAGE
);
impLista.borrarEspecifico(el);
JOptionPane.showMessageDialog
(
null,
"El
elemento eliminado es "+el,
"Eliminando NODO
especifico",
JOptionPane.INFORMATION_MESSAGE
);
}catch(NumberFormatException n){
JOptionPane.showMessageDialog(null,
"Error" + n.getMessage());
}
break;
case 6://6.
Salir
JOptionPane.showMessageDialog(null, "Programa terminado...");
break;
}
}catch(Exception e){
JOptionPane.showMessageDialog(null, "Error"+ e.getMessage());
}
} while (opcion !=6);
}
}
Lista.java
·
Declaramos dos variables que son inicio y fin
·
luego creamos un constructor
o
donde inicio y fin es igual a nulo
//algoritmo para saber si la lista esta vacía
·
método tipo booleano
o
si inicio es igual a fin retornara
verdadero true
o
si no retornara falso false
//algoritmo
para agregar nodo al inicio
·
método tipo void
·
inicio igual nuevo nodo (elemento, inicio)
o si
fin es igual a null
§ entonces
fin es igual a inicio
//algoritmo
para agregar nodo al final
·
método tipo void
o
si no esta vacia
§
fin de siguiente es igula a nuevo (elemento)
§
fin es igual a fin de siguiente
o
entonces
§
inicio es igual a fin y es igual a nuevo (elemento)
//algoritmo
para mostrar los datos
·
método tipo void
o
nodo recorrer es igual a inicio
o
mientras recorrer no sea igual a null
§
imprimir “recorrer.dato”
§
recorrer es igual recorrer de siguiente
//método
para eliminar un nodo del inicio
·
elemento es igual a inicio de dato
·
si inicio es igual a fin a nulo
o
apuntar inicio y fin a nulo
·
si no entonces
o
retornar el valor del elemento
//algoritmo
para eliminar un nodo especifico
·
si la lista no esta vacia
o
si inicio es igual a fin y elemento igual a
inicio de dato
§
entonces apuntar inicio y fin a nulo
o
si no el elemento igual (inicio de dato)
§
entonces apuntar inicio a inicio de siguiente
o
si no entonces
§
crear un nodo temporal y anterior
§
apuntar anterior a inicio
§
apuntar temporal a inicio de siguiente
§
mientras temporal sea diferente de nulo y
temporal de dato sea diferente de elemento
·
apuntar anterior anterior de siguiente
·
apuntar temporal a temporal de siguiente
§
si temporal sea diferente de nulo
·
apuntar anterior de siguiente a temporal de
siguiente
·
si temporal es igual a fin
o
fin va a ser igual a anterior
package
eliminariniciolse;
public
class Lista {
protected Nodo inicio,fin;
//CONSTRUCTOR
public Lista(){
inicio = null;
fin =null;
}
//METODO PARA SABER SI LA LISTA ESTA VACIA
public
boolean estaVacia(){
if(inicio==fin){
return true;
}else{
return false;
}
}
//METODO PARA AGREGAR AL INICIO
public void agregarAlInicio(int
elemento){
//creando nodo
inicio = new Nodo(elemento, inicio);
if(fin==null){
fin=inicio;
}
}
//Metodo para agreagr al final
public void agregarAlFinal(int
elemento){
if(!estaVacia()){
fin.siguiente = new Nodo
(elemento);
fin = fin.siguiente;
}else{
inicio = fin = new Nodo
(elemento);
}
}
//METODOD PARA MOSTRAR LOS DATOS
public void mostrarLista(){
Nodo recorrer = inicio;
System.out.println("\n");
while(recorrer
!= null){
System.out.print("["+recorrer.dato+"] -->");
recorrer = recorrer.siguiente;
}
}
//Metodo para eliminar del inicio
public int borrarDelInicio(){
int elemento = inicio.dato;
if(inicio==fin){
inicio = null;
fin=null;
}else{
inicio = inicio.siguiente;
}
return elemento;
}
//Metodo para eliminar un nodo
especifico
public void borrarEspecifico(int
elemento){
if(!estaVacia())
if(inicio==fin &&
elemento==inicio.dato){
inicio=fin=null;
}else
if(elemento==inicio.dato){
inicio=inicio.siguiente;
}else{
Nodo anterior, temporal;
anterior=inicio;
temporal=inicio.siguiente;
while(temporal != null
&& temporal.dato != elemento){
anterior=anterior.siguiente;
temporal=temporal.siguiente;
}
if(temporal != null){
anterior.siguiente=temporal.siguiente;
if(temporal==fin){
fin=anterior;
}
}
}
}
int
borrarEspecifico() {
throw new
UnsupportedOperationException("Not supported yet."); //To change body
of generated methods, choose Tools | Templates.
}
}
Suscribirse a:
Entradas (Atom)
-
La recursividad Que es la Recursividad? Como su nombre lo indica la recursibidad va utilizando los mismos recursos contant...
-
A continuación, nuestra opinión de por qué es importante conocer los Tipos de Datos Abstracto y qué aplicaciones encontramos en los TDA....
-
La diferencia entre las listas simplemente enlazada y las doblemente enlazada Es que las doblemente enlazada contiene dos punteros uno apu...
