Clase
UNIDAD Nº 1: TEMAS:
Listas. Listas genéricas doblemente
encadenadas. 5
Objetivos:
Implementar los algoritmos para procesar listas
genéricas doblemente encadenadas.
Lista doblemente encadenadas.
A las listas vistas hasta el momento podemos recorrerlas solamente en una dirección
(Listas simplemente encadenadas). Hay problemas donde se requiere recorrer la lista en
ambas direcciones, en estos casos el empleo de listas doblemente encadenadas es
recomendable.
Como ejemplo pensemos que debemos almacenar un menú de opciones en una lista,
la opción a seleccionar puede ser la siguiente o la anterior, podemos desplazarnos en ambas
direcciones.
Representación gráfica de una lista doblemente encadenada:
* 8 4 3 *
4
raiz
Observemos que una lista doblemente encadenada tiene dos punteros por cada nodo,
uno apunta al nodo siguiente y otro al nodo anterior.
Seguimos teniendo un puntero (raiz) que tiene la dirección del primer nodo.
El puntero sig del último nodo igual que las listas simplemente encadenadas apunta a null, y el
puntero ant del primer nodo apunta a null.
Se pueden plantear Listas tipo pila, cola y genéricas con enlace doble.
Hay que tener en cuenta que el requerimiento de memoria es mayor en las listas
doblemente encadenadas ya que tenemos dos punteros por nodo.
La estructura del nodo es:
class Nodo {
int info;
Instituto Superior Santo Domingo Página 1 de 15
Nodo sig, ant;
}
Resolveremos algunos métodos para administrar listas genéricas empleando listas
doblemente encadenadas para analizar la mecánica de enlace de nodos.
Muchos de los métodos, para listas simple y doblemente encadenadas no varía, como
por ejemplo: el constructor, vacia, cantidad, etc.
- Clase ListaGenerica.
public class ListaGenerica {
class Nodo {
int info;
Nodo ant,sig;
}
private Nodo raiz;
public ListaGenerica () {
raiz=null;
}
public void insertar (int pos, int x)
{
if (pos <= cantidad () + 1) {
Nodo nuevo = new Nodo ();
[Link] = x;
if (pos == 1){
[Link] = raiz;
if (raiz!=null)
[Link]=nuevo;
raiz = nuevo;
} else
if (pos == cantidad () + 1) {
Nodo reco = raiz;
while ([Link] != null) {
reco = [Link];
}
[Link] = nuevo;
[Link]=reco;
[Link] = null;
} else {
Nodo reco = raiz;
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Nodo siguiente = [Link];
[Link] = nuevo;
[Link]=reco;
[Link] = siguiente;
[Link]=nuevo;
}
}
}
public int extraer (int pos) {
if (pos <= cantidad ()) {
Instituto Superior Santo Domingo Página 2 de 15
int informacion;
if (pos == 1) {
informacion = [Link];
raiz = [Link];
if (raiz!=null)
[Link]=null;
} else {
Nodo reco;
reco = raiz;
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Nodo prox = [Link];
[Link] = [Link];
Nodo siguiente=[Link];
if (siguiente!=null)
[Link]=reco;
informacion = [Link];
}
return informacion;
}
else
return Integer.MAX_VALUE;
}
public void borrar (int pos)
{
if (pos <= cantidad ()) {
if (pos == 1) {
raiz = [Link];
if (raiz!=null)
[Link]=null;
} else {
Nodo reco;
reco = raiz;
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Nodo prox = [Link];
prox=[Link];
[Link] = prox;
if (prox!=null)
[Link]=reco;
}
}
}
public void intercambiar (int pos1, int pos2) {
if (pos1 <= cantidad () && pos2 <= cantidad ()) {
Nodo reco1 = raiz;
for (int f = 1 ; f < pos1 ; f++)
reco1 = [Link];
Nodo reco2 = raiz;
for (int f = 1 ; f < pos2 ; f++)
reco2 = [Link];
int aux = [Link];
[Link] = [Link];
[Link] = aux;
}
}
public int mayor () {
if (!vacia ()) {
Instituto Superior Santo Domingo Página 3 de 15
int may = [Link];
Nodo reco = [Link];
while (reco != null) {
if ([Link] > may)
may = [Link];
reco = [Link];
}
return may;
}
else
return Integer.MAX_VALUE;
}
public int posMayor() {
if (!vacia ()) {
int may = [Link];
int x=1;
int pos=x;
Nodo reco = [Link];
while (reco != null){
if ([Link] > may) {
may = [Link];
pos=x;
}
reco = [Link];
x++;
}
return pos;
}
else
return Integer.MAX_VALUE;
}
public int cantidad ()
{
int cant = 0;
Nodo reco = raiz;
while (reco != null) {
reco = [Link];
cant++;
}
return cant;
}
public boolean ordenada() {
if (cantidad()>1) {
Nodo reco1=raiz;
Nodo reco2=[Link];
while (reco2!=null) {
if ([Link]<[Link]) {
return false;
}
reco2=[Link];
reco1=[Link];
}
}
return true;
}
public boolean existe(int x) {
Nodo reco=raiz;
Instituto Superior Santo Domingo Página 4 de 15
while (reco!=null) {
if ([Link]==x)
return true;
reco=[Link];
}
return false;
}
public boolean vacia ()
{
if (raiz == null)
return true;
else
return false;
}
public void imprimir ()
{
Nodo reco = raiz;
while (reco != null) {
[Link] ([Link] + "-");
reco = [Link];
}
[Link]();
}
public static void main(String[] ar) {
ListaGenerica lg=new ListaGenerica();
[Link] (1, 10);
[Link] (2, 20);
[Link] (3, 30);
[Link] (2, 15);
[Link] (1, 115);
[Link] ();
[Link] ("Luego de Borrar el primero");
[Link] (1);
[Link] ();
[Link] ("Luego de Extraer el segundo");
[Link] (2);
[Link] ();
[Link] ("Luego de Intercambiar el primero con el
tercero");
[Link] (1, 3);
[Link] ();
if ([Link](10))
[Link]("Se encuentra el 20 en la lista");
else
[Link]("No se encuentra el 20 en la lista");
[Link]("La posición del mayor
es:"+[Link]());
if ([Link]())
[Link]("La lista está ordenada de menor a
mayor");
else
[Link]("La lista no está ordenada de menor a
mayor");
}
}
Instituto Superior Santo Domingo Página 5 de 15
Para insertar en una determinada posición dentro de la lista:
public void insertar (int pos, int x)
Primero con un if verificamos que exista esa posición en la lista (por ejemplo si la lista
tiene 4 nodos podemos insertar hasta la posición 5, es decir uno más allá del último):
if (pos <= cantidad () + 1) {
Si ingresa al if ya podemos crear el nodo:
Nodo nuevo = new Nodo ();
[Link] = x;
Ahora debemos analizar si la inserción es al principio de la lista, al final o en medio ya
que los enlaces varían según donde se lo inserta.
Para saber si se inserta al principio de la lista preguntamos si en pos llega un 1:
if (pos == 1){
Si llega un 1 luego enlazamos el puntero sig del nodo que creamos con la dirección
del primer nodo de la lista (raiz apunta siempre al primer nodo de la lista)
Verificamos si raiz está apuntando actualmente a un nodo, en caso afirmativo
enlazamos el puntero ant con el nodo que acabamos de crear y luego desplazamos raiz
al nodo creado:
[Link] = raiz;
if (raiz!=null)
[Link]=nuevo;
raiz = nuevo;
Si no se inserta al principio de la lista preguntamos si se inserta al final:
if (pos == cantidad () + 1) {
En caso de insertarse al final recorremos la lista hasta el último nodo:
Nodo reco = raiz;
while ([Link] != null) {
reco = [Link];
}
y enlazamos el puntero sig del último nodo de la lista con la dirección del nodo que
acabamos de crear (disponemos en sig del nodo creado el valor null ya que no hay
otro nodo más adelante) El puntero ant del nodo que creamos lo enlazamos con el
nodo que era último hasta este momento y está siendo apuntado por reco:
[Link] = nuevo;
[Link]=reco;
[Link] = null;
Instituto Superior Santo Domingo Página 6 de 15
Si no se inserta al principio o al final significa que tenemos que insertar en medio de
la lista.
Disponemos un for donde avanzamos un puntero auxiliar y nos detenemos una
posición antes a donde tenemos que insertarlo:
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Disponemos otro puntero auxiliar que apunte al nodo próximo a donde está apuntando
reco. Ahora enlazamos el puntero sig del nodo apuntado por reco con la dirección del
nodo creado y el puntero sig del nodo creado con la dirección del nodo siguiente. El
puntero ant del nodo apuntado por nuevo lo enlazamos con el nodo apuntado por raiz
y el puntero ant del nodo apuntado por siguiente lo apuntamos a nuevo (con esto
tenemos actualizados los cuatro punteros internos a la lista):
Nodo siguiente = [Link];
[Link] = nuevo;
[Link]=reco;
[Link] = siguiente;
[Link]=nuevo;
El método extraer recibe como parámetro la posición del nodo a extraer:
public int extraer (int pos) {
Primero verificamos que la posición exista en la lista:
if (pos <= cantidad ()) {
En caso que exista verificamos si el nodo a extraer es el primero de la lista (este
análisis debe hacerse ya que si es el primero de la lista se modifica el puntero raiz):
if (pos == 1) {
Si es el primero guardamos en una variable auxiliar la información del nodo y
avanzamos el puntero raiz, luego si raiz apunta a un nodo disponemos el puntero ant
de dicho nodo a null:
informacion = [Link];
raiz = [Link];
if (raiz!=null)
[Link]=null;
Si el nodo a extraer no está al principio de la lista avanzamos con una estructura
repetitiva hasta el nodo anterior a extraer:
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Luego definimos otro puntero auxiliar y lo disponemos en el siguiente nodo a donde
está apuntando reco:
Instituto Superior Santo Domingo Página 7 de 15
Nodo prox = [Link];
Ahora enlazamos el puntero sig del nodo apuntado por reco al nodo siguiente del nodo
apuntado por prox (es decir el nodo apuntado por prox queda fuera de la lista)
disponemos finalmente otro puntero llamado siguiente que apunte al nodo que se
encuentra una posición más adelante del nodo apuntado por prox, si dicho puntero
apunta a un nodo actualizamos el puntero ant de dicho nodo con la dirección del nodo
apuntado por reco:
[Link] = [Link];
Nodo siguiente=[Link];
if (siguiente!=null)
[Link]=reco;
informacion = [Link];
El método borrar es muy similar al método extraer con la diferencia de que no retorna
valor:
public void borrar (int pos)
{
if (pos <= cantidad ()) {
if (pos == 1) {
raiz = [Link];
if (raiz!=null)
[Link]=null;
} else {
Nodo reco;
reco = raiz;
for (int f = 1 ; f <= pos - 2 ; f++)
reco = [Link];
Nodo prox = [Link];
prox=[Link];
[Link] = prox;
if (prox!=null)
[Link]=reco;
}
}
}
El método intercambiar recibe dos enteros que representan las posiciones de los nodos
que queremos intercambiar sus informaciones:
public void intercambiar (int pos1, int pos2) {
Mediante un if verificamos que las dos posiciones existan en la lista:
if (pos1 <= cantidad () && pos2 <= cantidad ()) {
Definimos un puntero auxiliar llamado reco1, lo inicializamos con la dirección del
primer nodo y mediante un for avanzamos hasta la posición almacenada en pos1:
Nodo reco1 = raiz;
for (int f = 1 ; f < pos1 ; f++)
Instituto Superior Santo Domingo Página 8 de 15
reco1 = [Link];
De forma similar con un segundo puntero auxiliar avanzamos hasta la posición
indicada por pos2:
Nodo reco2 = raiz;
for (int f = 1 ; f < pos2 ; f++)
reco2 = [Link];
Por último intercambiamos las informaciones que almacenan cada nodo:
int aux = [Link];
[Link] = [Link];
[Link] = aux;
El método que retorna el mayor de la lista:
public int mayor () {
Verificamos que la lista no esté vacía:
if (!vacia ()) {
Suponemos que el mayor es el primero de la lista e inicializamos un puntero auxiliar
con la dirección del segundo nodo de la lista:
int may = [Link];
Nodo reco = [Link];
Mediante una estructura repetitiva recorremos toda la lista:
while (reco != null) {
Cada vez que encontramos un nodo con información mayor que la variable may la
actualizamos con este nuevo valor y avanzamos el puntero reco para visitar el
siguiente nodo:
if ([Link] > may)
may = [Link];
reco = [Link];
Fuera de la estructura repetitiva retornamos el mayor:
return may;
El método que retorna la posición del mayor es similar al anterior con la salvedad que
debemos almacenar en otro auxiliar la posición donde se almacena el mayor:
public int posMayor() {
if (!vacia ()) {
int may = [Link];
int x=1;
int pos=x;
Nodo reco = [Link];
Instituto Superior Santo Domingo Página 9 de 15
while (reco != null){
if ([Link] > may) {
may = [Link];
pos=x;
}
reco = [Link];
x++;
}
return pos;
}
else
return Integer.MAX_VALUE;
}
El método que debe retornar si está ordenada la lista de menor a mayor es:
public boolean ordenada() {
Lo primero que verificamos si la lista tiene más de un nodo significa que debemos
controlarla:
if (cantidad()>1) {
Disponemos dos punteros auxiliares con las direcciones del primer y segundo nodo de
la lista:
Nodo reco1=raiz;
Nodo reco2=[Link];
Mediante un while mientras no se finaliza la lista:
while (reco2!=null) {
controlamos si la información del segundo nodo es menor al nodo anterior significa
que la lista no está ordenada y podemos parar el análisis retornando un false
if ([Link]<[Link]) {
return false;
Dentro del while avanzamos los dos punteros a sus nodos siguientes respectivamente.
reco2=[Link];
reco1=[Link];
Fuera del while retornamos true indicando que la lista está ordenada de menor a
mayor
return true;
El método existe:
public boolean existe(int x) {
Instituto Superior Santo Domingo Página 10 de 15
Mediante un while recorremos la la lista:
Nodo reco=raiz;
while (reco!=null) {
y en cada nodo que visitamos controlamos si el parámetro x es igual a la información
del nodo, en caso afirmativo salimos del método retornando true:
if ([Link]==x)
return true;
reco=[Link];
Fuera del while retornamos false indicando que ningún nodo coincide con el
parámetro x:
return false;
Ejercicio Propuesto
Plantear una clase para administrar una lista genérica doblemente encadenada
implementando los siguientes métodos:
a) Insertar un nodo al principio de la lista.
b) Insertar un nodo al final de la lista.
c) Insertar un nodo en la segunda posición. Si la lista está vacía no se inserta el nodo.
d) Insertar un nodo en la ante última posición.
e) Borrar el primer nodo.
f) Borrar el segundo nodo.
g) Borrar el último nodo.
h) Borrar el nodo con información mayor.
Instituto Superior Santo Domingo Página 11 de 15
Solución.
Se agrega la solución al problema propuesta para ser consultada en caso de no poder
implementar alguno de los métodos propuestos.
public class ListaGenericaDoble {
class Nodo {
int info;
Nodo ant,sig;
}
private Nodo raiz;
public ListaGenericaDoble () {
raiz=null;
}
public void insertarPrimero(int x)
{
Nodo nuevo = new Nodo ();
[Link] = x;
[Link]=raiz;
if (raiz!=null)
[Link]=nuevo;
raiz=nuevo;
}
public void insertarUtlimo(int x) {
Nodo nuevo = new Nodo ();
[Link] = x;
if (raiz==null)
raiz=nuevo;
else {
Nodo reco=raiz;
while ([Link]!=null) {
reco=[Link];
}
[Link]=nuevo;
[Link]=reco;
}
}
public void insertarSegundo(int x) {
if (raiz!=null) {
Nodo nuevo = new Nodo ();
[Link] = x;
if ([Link]==null) {
//Hay un solo nodo.
[Link]=nuevo;
[Link]=raiz;
} else {
Nodo tercero=[Link];
[Link]=tercero;
[Link]=nuevo;
[Link]=nuevo;
[Link]=raiz;
}
}
}
Instituto Superior Santo Domingo Página 12 de 15
public void insertarAnteUltimo(int x) {
if (raiz!=null) {
Nodo nuevo = new Nodo ();
[Link] = x;
if ([Link]==null) {
//Hay un solo nodo.
[Link]=raiz;
raiz=nuevo;
} else {
Nodo reco=raiz;
while ([Link]!=null) {
reco=[Link];
}
Nodo anterior=[Link];
[Link]=reco;
[Link]=anterior;
[Link]=nuevo;
[Link]=nuevo;
}
}
}
public void borrarPrimero() {
if (raiz!=null) {
raiz=[Link];
if (raiz!=null)
[Link]=null;
}
}
public void borrarSegundo() {
if (raiz!=null) {
if ([Link]!=null) {
Nodo tercero=[Link];
tercero=[Link];
[Link]=tercero;
if (tercero!=null)
[Link]=raiz;
}
}
}
public void borrarUltimo () {
if (raiz!=null) {
if ([Link]==null) {
raiz=null;
} else {
Nodo reco=raiz;
while([Link]!=null) {
reco=[Link];
}
reco=[Link];
[Link]=null;
}
}
}
public void imprimir () {
Nodo reco = raiz;
while (reco != null) {
Instituto Superior Santo Domingo Página 13 de 15
[Link] ([Link] + "-");
reco = [Link];
}
[Link]();
}
public void borrarMayor() {
if (raiz!=null) {
Nodo reco=raiz;
int may=[Link];
while (reco!=null) {
if ([Link]>may) {
may=[Link];
}
reco=[Link];
}
reco=raiz;
while (reco!=null) {
if ([Link]==may) {
if (reco==raiz) {
raiz=[Link];
if (raiz!=null)
[Link]=null;
reco=raiz;
} else {
Nodo atras=[Link];
[Link]=[Link];
reco=[Link];
if (reco!=null)
[Link]=atras;
}
} else {
reco=[Link];
}
}
}
}
public static void main(String[] ar) {
ListaGenericaDoble lg=new ListaGenericaDoble();
[Link] (10);
[Link](45);
[Link](23);
[Link](89);
[Link]();
[Link]("Insertamos un nodo al final:");
[Link](160);
[Link]();
[Link]("Insertamos un nodo en la segunda
posición:");
[Link](13);
[Link]();
[Link]("Insertamos un nodo en la anteultima
posición:");
[Link](600);
[Link]();
[Link]("Borramos el primer nodo de la lista:");
[Link]();
[Link]();
[Link]("Borramos el segundo nodo de la lista:");
Instituto Superior Santo Domingo Página 14 de 15
[Link]();
[Link]();
[Link]("Borramos el ultimo nodo de la lista:");
[Link]();
[Link]();
[Link]("Borramos el mayor de la lista:");
[Link]();
[Link]();
}
}
Instituto Superior Santo Domingo Página 15 de 15
