Juan Guillermo Echeverri Tapias
07 de Mayo del 2012

¿Que son las listas doblemente encadenadas y como puede ser un ejemplo de ellas?

jhon alexander murillo osorio
07 de Mayo del 2012

En las listas lineales ya estudiadas, el recorrido de ellas solo se podía hacerse en único sentido: de izquierda a derecha (principio a final).en numerosas ocasiones se necesita recorrer las listas en ambas direcciones. Las listas que pueden recorrerse en ambas direcciones se denominan listas doblemente enlazada. En estas listas cada nodo consta del campo info de datos y dos campos de enlace o punteros: anterior (ant) y siguiente (sig).


Ejemplo:


import java.io.*;

class Nodo{
//atributos
int dato;
Nodo sig; // referencia al siguiente elemento
Nodo ant; // referencia al anterior elemento
//métodos
Nodo( ) { } // constructor sin parámetros
}

class ListaDobleEncadenada{

Nodo cab;
Nodo movil;
Nodo fin;

public ListaDobleEncadenada( ){} //constructor
public void iniciar_lista_doble_encadenada( )

{
cab = null;
fin = null;
}
public void insertar_nodo_inicio()throws IOException
{
BufferedReader Teclado;
Teclado= new BufferedReader(new InputStreamReader(System.in));
Nodo nuevo = new Nodo();
System.out.println("Digite el numero: ");
nuevo.dato=Integer.parseInt(Teclado.readLine());
if (fin == null)
{
Cab = fin =nuevo;
nuevo.ant = nuevo.sig = null;
}
else
{ movil = cab;
nuevo.sig = movil;
movil.ant = nuevo;
cab = nuevo;
nuevo.ant = null;
}
}
public void borrar_nodo_posicion( )throws IOException{
int cn, pos;
BufferedReader Teclado;
Teclado=new BufferedReader(new InputStreamReader(System.in));
cn = 1;
Nodo borra;
if (cab == null){
System.out.println("NO hay elementos en la Lista");
return;
}
System.out.println("Digite la posicion: ");
pos = Integer.parseInt(Teclado.readLine());
movil = cab;
if (cab != null)
{
if ((pos == 1)&&(movil.sig == null))
{
borra = movil;
cab = null;
fin = null;
borra = null;
}
else
if ((pos == 1)&&(movil.sig != null))
{
borra = movil;
movil = movil.sig;
cab = movil;
movil.ant = null;
borra = null;
}
else
while (movil != null)
{
if (cn + 1 == pos)
{
borra = movil.sig;
movil.sig = borra.sig;
if (fin == borra)
fin = movil;
if (movil.sig != null)
{
movil = movil.sig;
movil.ant = borra.ant;
}
borra = null;
}
movil= movil.sig;
cn++;
}
}
else
System.out.println("NO hay nodos");
}
public void imprimir_lista_cab( )
{
movil = cab;
while(movil != null){
System.out.println(movil.dato + " ");
movil = movil.sig;
}
}
public void imprimir_lista_fin( )
{
movil = fin;
while(movil != null){
System.out.println(movil.dato + " ");
movil = movil.ant;
}
}

public void destruir_lista_doble_encadenada( ){
Nodo borra;
borra = cab;
movil = cab;
while(movil != null){
movil = movil.sig;
borra = null;
borra = movil;
}
}
}

class Test{
public static void main(String[ ] args)throws IOException{
BufferedReader Teclado;
Teclado= new BufferedReader(new InputStreamReader(System.in));
int opc;
ListaDobleEncadenada lista = new ListaDobleEncadenada();
lista.iniciar_lista_doble_encadenada();
do{
System.out.println("1.Almacenar un Numero en la Lista Doblemente Encadenada");
System.out.println("2.Borrar un Numero en la Lista Doblemente Encadenada mediante la Posicion");
System.out.println("3.Imprimir Lista Doblemente Encadenada por la cabeza");
System.out.println("4.Imprimir Lista Doblemente Encadenada por el fin");
System.out.println("5.Salir");
System.out.println("digite la opcion");
opc=Integer.parseInt(Teclado.readLine());
switch(opc){
case 1: lista.insertar_nodo_inicio();
break;
case 2: lista.borrar_nodo_posicion();
break;
case 3: lista.imprimir_lista_cab();
break;
case 4: lista.imprimir_lista_fin();
break;
}
}while (opc!=5);
lista.destruir_lista_doble_encadenada( );
}
}