Programa de

Ing. De Sistemas

Estructura
de Datos
Sesión 7

Tema:
Listas Doblemente
Enlazadas
Resultado de aprendizaje Evidencia de aprendizaje

Aplica estructuras dinámicas lineales en la Informe de laboratorio: listas enlazadas dobles.

construcción de soluciones informáticas de una
organización.
Contenido
Listas Doblemente Enlazadas

• Definición
• Operaciones con Listas Doblemente
Enlazadas
Revisa el
siguiente
video:
Después de haber visualizado el video en la slide
anterior, reflexionamos y respondemos las
siguientes interrogantes:

01 ¿Qué son las listas dobles?

02 ¿En qué se diferencian de las listas simples?

03 ¿Cómo se puede recorrer una lista doble?

 Tema
Listas
Doblemente
Enlazadas
Estructura de Datos – Sesión 7

Lista doblemente enlazada

Cada nodo contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor.
La lista es eficiente tanto como en recorrido directo (“adelante”) como en recorrido
inverso (“atras”).
Estructura de Datos – Sesión 7

Nodo
public class Nodo {
int dato;
Nodo sig;
Nodo ant;
public Nodo(int num)
public class Nodo { { dato=num;
private int data; // almacena el dato sig=ant=null;
}
private Nodo sig; //”enlace” al próximo nodo }

private Nodo ant; // ”enlace” al anterior nodo

}
Estructura de Datos – Sesión 7

Operaciones de una lista doblemente enlazada

• Añadir o insertar elementos.

• Buscar elementos.
• Borrar elementos.
• Moverse a través de la lista, siguiente y anterior.

sig

ant

Inicio fin
Estructura de Datos – Sesión 7

Insertar nuevo nodo

• Insertar nodo en la primera posición

1-. Nodosiguiente // debe apuntar a Lista.
2-. Nodoanterior y Listaanterior // debe apuntar a null
3-. Listaanterior //debe apuntar a nodo

Nuevo
nodo

1
null
Dato Dato Dato
…
2
3
Estructura de Datos – Sesión 7

public class Nodo {

Insertar nuevo nodo int dato;
Nodo sig;
Nodo ant;
public Nodo(int num)
Nuevo { dato=num;
nodo
sig=ant=null;
}
}

Nodo InsertaInicio(Nodo inicio, int num)

{ Nodo nuevo=new Nodo(num); // se llama al constructor
//Realizando los enlaces correspondientes
[Link]=inicio;
if(inicio==null) // solo para la primera vez
{ fin=nuevo;
[Link]=null;
}
if(inicio!=null)
[Link]=nuevo;
inicio=nuevo;
return inicio;
Estructura de Datos – Sesión 7

Recorrido en una lista doble

HACIA ADELANTE HACIA ATRAS

int Suma(Nodo inicio) int Suma(Nodo fin)

{ Nodo aux=inicio; { Nodo aux=fin;
int suma=0; int suma=0;
//Recorriendo la lista //Recorriendo la lista
while(aux!=null) while(aux!=null)
{ //Sumando los datos { //Sumando los datos
suma=suma+[Link]; suma=suma+[Link];
//Avanzando al siguiente nodo //Retrocediendo al nodo anterior
aux=[Link]; aux=[Link];
} }
return suma; return suma;
} }
Estructura de Datos – Sesión 7

Eliminar nodo

eliminaPrimer( nodo)
1.- Si nodo apunta a Lista // hacemos que Lista apunte
Lista=siguiente.
2.- Hacemos que nodo=siguiente=anterior// apunte a NULL
3.- Borramos el nodo apuntado por nodo.

Caso 2
Caso 2.1. Eliminar el primer nodo
Estructura de Datos – Sesión 7

Eliminar nodo

Caso 2.2 Eliminar un nodo intermedio

eliminaMedio(nodo)
1-. Si nodo apunta a Lista
Lista=siguiente
2-. nodo= siguiente
3-. Nodo = anterior
4-. Borramos el nodo apuntado por nodo
Estructura de Datos – Sesión 7

Eliminar nodo

Caso 3 Eliminar el último nodo

eliminaUltimo(nodo)
1-. Si nodo apunta a Lista
Lista=anterior.
2- nodo=anterior=siguiente apunte a NULL
3-. Borramos el nodo apuntado por nodo.
 void Eliminar(Nodo inicio, int elem)
{ Nodo actual;
Estructura de Datos – Sesión 7

boolean encontrado=false;
Eliminar nodo actual=inicio;
while((actual!=null)&& (!encontrado)) //bucle de Búsqueda
{ encontrado=([Link]==elem); // se actualiza elvalor de encontrado
if(!encontrado) // severifica para pasar al siguiente nodo
actual=[Link];
}
//Realizando los enlaces
if (actual != null) // se verifica si se encontro el elemento buscado
{ if (actual == ini)
{ ini = [Link]; // borrar el primero
if([Link]!=null)
[Link]=null;
}
else if ([Link]!=null) // No es el ultimo
{ [Link]=[Link];
[Link]=[Link];
}
else
{ [Link]=null; // el ultimo
fin=[Link]; // moviendo el final
}
actual=null;
}
}
Estructura de Datos – Sesión 7

Buscar Nodo según característica

Nodo Buscar(Nodo inicio,String cod)

{ //Generamos un puntero y lo colocamos al inicio de la lista
Nodo pos=inicio;
//Recorriendo la lista para encontrar la información public class Nodo{
while(pos!=null && ) // atributos
pos=[Link]; public String codigo;
//Retorno de la posición del dato // puntero al siguiente nodo
return pos; public Nodo sig ;
} public Nodo ant;
// el constructor de nodos
Nodo (String cod)
{ codigo=cod;
ant = sig = null;
}
}
Estructura de Datos – Sesión 7

Ejemplo

Construya una aplicación que utilice

listas doblemente enlazadas y que
permita realizar el registro de
empleados donde se podrá guardar,
mostrar, consultar, actualizar y
eliminar el registro de empleado. Para
todas estas operaciones considere el
ingreso del código del empleado.
Estructura de Datos – Sesión 7

Ejemplo

DECLARACIÓN DEL
CLASE NODO
Estructura de Datos – Sesión 7

Ejemplo
Estructura de Datos – Sesión 7

Ejemplo

BOTÓN GUARDAR
Estructura de Datos – Sesión 7

Ejemplo

BOTÓN
CONSULTAR
Estructura de Datos – Sesión 7

Ejemplo

BOTÓN ACTUALIZAR
 Estructura de Datos – Sesión 7

Ejemplo

BOTÓN
ELIMINAR
Autoevaluación
Sesión 7
 Característica de las listas dobles

Contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor.

Pregunta 1

La lista es eficiente en recorrido directo (“adelante”)-

La lista es eficiente en recorrido inverso (“atrás”).

Todas son correctas

 Característica de las listas dobles

Contiene dos enlaces, uno a su nodo predecesor y el otro a su nodo sucesor.

Pregunta 1

La lista es eficiente en recorrido directo (“adelante”)-

La lista es eficiente en recorrido inverso (“atrás”).

Todas son correctas

 No son operaciones en listas dobles

Añadir o insertar elementos., Buscar elementos

Pregunta 2

Borrar elementos, Moverse a través de la lista, siguiente y anterior.

Permutar entre elementos, Enlazar elementos con vectores.

Todas son correctas

 No son operaciones en listas dobles

Añadir o insertar elementos., Buscar elementos

Pregunta 2

Borrar elementos, Moverse a través de la lista, siguiente y anterior.

Permutar entre elementos, Enlazar elementos con vectores.

Todas son correctas

 Como declaramos un nodo:

public class Nodo {

private int data;
private Nodo sig;
private Nodo ant;
Pregunta 3

}
public class Nodo {
private Nodo ant;
private int data;
private Nodo sig;
}
public class Nodo {
private Nodo sig;
private Nodo ant;
private int data;
}
Todas son correctas
 Como declaramos un nodo:

public class Nodo {

private int data;
private Nodo sig;
private Nodo ant;
Pregunta 3

}
public class Nodo {
private Nodo ant;
private int data;
private Nodo sig;
}
public class Nodo {
private Nodo sig;
private Nodo ant;
private int data;
}

Todas son correctas

 Una lista doble se puede recorrer:

Siempre haca adelante, pero nunca hacia atrás

Pregunta 4

Hacia adelante o hacia atrás

Únicamente hacia atrás pero no hacia adelante

Todas son falsas

 Una lista doble se puede recorrer:

Siempre haca adelante, pero nunca hacia atrás

Pregunta 4

Hacia adelante o hacia atrás

Únicamente hacia atrás pero no hacia adelante

Todas son falsas

Autoevaluación
¡Vamos por más logros!

¡Felicitaciones!
Ha concluido la autoevaluación
 Es un tipo de lista enlazada que permite moverse hacia delante y hacia
atrás. Cada nodo de una lista doblemente enlazada tiene dos enlaces,
Conclusiones

además de los campos de datos. Un enlace, el derecho, se utiliza para

navegar la lista hacia delante. El otro enlace, el isquierdo, se utiliza para
navegar la lista hacia atras.

El doble enlace de los nodos permite recorrer la lista en cualquier

dirección. Mientras que agregar o eliminar un nodo en una lista doblemente
enlazada requiere cambiar más enlaces que en estas mismas operaciones en
una lista enlazada simple, las operaciones son más simples porque no hay
necesidad de mantener guardado el nodo anterior durante el recorrido, ni
necesidad de recorrer la lista para hallar el nodo anterior, la referencia al
nodo que se quiere eliminar o insertar es lo único necesario.
Aplicando lo
aprendido:
A partir de los conceptos estudiados en la presente sesión
desarrollamos la Guía de Laboratorio 06 que encontraremos en la
plataforma Blackboard, luego sube tu solución en la sesión
correspondiente a la evaluación.
 BLASCO, Francisco. Programación Orientada a Objetos en Java. [en
línea]. Madrid: RA-MA Editorial. 2019. ISBN: 9788499648651.
Disponible en:
Referencias

[Link]
a-objetos-en-jav a-1591713437?preview=true
.

CAMPESATO, Osward. Data Structures in Java. [en línea]. 1st. Ed.

Bloomfield: Mercury Learning & Information. 2023. ISBN: 1-68392-953-
5. Disponible en:
[Link]

CEBALLOS, Francisco Javier. Programación orientada a objetos con C++.

[en línea]. 5ta Ed. Madrid: RA-MA Editorial. ISBN: 9788499647845.
Disponible en:
[Link]