Embedded Files
Objetivos
Con el estudio de este capítulo, usted podrá:
• Distinguir entre una estructura secuencial y una estructura enlazada.
• Definir el tipo abstracto de datos Lista.
• Conocer las operaciones básicas de la listas enlazadas.
• Implementar una lista enlazada para un tipo de elemento.
• Aplicar la estructura Lista para almacenar datos en el desarrollo de aplicaciones.
• Definir una lista doblemente enlazada.
• Definir una lista circular.
• Implementar listas enlazadas ordenadas.
• Realizar una lista genérica.
Introducción
En este capítulo se comienza el estudio de las estructuras de datos dinámicas. Al contrario que las estructuras de datos estáticas (arrays —listas, vectores y tablas— y estructuras), cuyo tamaño en memoria permanece inalterable durante la ejecución del programa, las estructuras de datos dinámicas crecen y se contraen a medida que se ejecuta el programa.
La estructura de datos que se estudiará en este capítulo es la lista enlazada (ligada o encadenada, linked list): una colección de elementos (denominados nodos) dispuestos uno a continuación de otro, cada uno de ellos conectado al siguiente por un “enlace” o “referencia”.
En el capítulo se desarrollan métodos para insertar, buscar y borrar elementos en listas enlazadas. De igual modo,
se muestra el tipo abstracto de datos (TAD) que representa las listas enlazadas.
Las listas enlazadas son estructuras muy flexibles y con numerosas aplicaciones en el mundo de la programación
FUNDAMENTOS TEÓRICOS de listas enlazadas
Las estructuras de datos lineales de elementos homogéneos (listas, tablas, vectores) utilizaban arrays para implementar tales estructuras, siendo los elementos de tipo primitivo (int, long, double...); también se ha utilizado la clase Vector, aunque los elementos, en este caso, han de ser referencias.
Esta técnica obliga a fijar por adelantado el espacio a ocupar en memoria, de modo que, cuando se desea añadir un nuevo elemento que rebase el tamaño prefijado del array, no es posible realizar la operación sin que se produzca un error en tiempo de ejecución.
Esta característica se debe a que los arrays hacen un uso ineficiente de la memoria. Gracias a la asignación dinámica de variables, se pueden implementar listas de modo que la memoria física utilizada se corresponda con el número de elementos de la tabla; para ello, se recurre a las referencias (apuntadores) que hacen un uso más eficiente de la memoria.
CONCEPTO
Una lista enlazada es una colección o secuencia de elementos dispuestos uno detrás de otro, en la que cada elemento se conecta al siguiente elemento por un “enlace” o “referencia”. La idea básica consiste en construir una lista cuyos elementos, llamados nodos, se componen de dos partes (campos): la primera parte contiene la información y es, por consiguiente, un valor de un tipo genérico (denominado Dato, TipoElemento, Info, etc.), y la segunda parte es una referencia (denominado enlace o sgte) que apunta (enlaza) al siguiente elemento de la lista.
La representación gráfica más extendida es aquella que utiliza una caja (un rectángulo) con
dos secciones en su interior. En la primera sección se escribe el elemento o valor del dato, y
en la segunda sección, el enlace o referencia mediante una flecha que sale de la caja y apunta
al nodo siguiente
Para recordar
Una lista enlazada consta de un número de elementos, y cada elemento tiene dos
componentes (campos), una referencia al siguiente elemento de la lista y un valor, que
puede ser de cualquier tipo
Los enlaces se representan por flechas para facilitar la comprensión de la conexión entre
dos nodos e indicar que el enlace tiene la dirección en memoria del siguiente nodo. Los enlaces
también sitúan los nodos en una secuencia. En la Figura 8.2, los nodos forman una secuencia
desde el primer elemento (e1 ) al último elemento (en ). El primer nodo se enlaza al segundo,
éste se enlaza al tercero, y así sucesivamente hasta llegar al último nodo, que debe ser
representado de forma diferente para significar que este nodo que no se enlaza a ningún otro.
La Figura 8.3 muestra diferentes representaciones gráficas utilizadas para dibujar el campo
enlace del último nodo.
CLASIFICACIÓN DE LISTAS ENLAZADAS
Las listas se pueden dividir en cuatro categorías :
• Listas simplemente enlazadas. Cada nodo (elemento) contiene un único enlace que lo
conecta al nodo siguiente o nodo sucesor. La lista es eficiente en recorridos directos
(“adelante”).
• Listas doblemente enlazadas. Cada nodo contiene dos enlaces, uno a su nodo predecesor
y otro a su nodo sucesor. La lista es eficiente tanto en recorrido directo (“adelante”) como
en recorrido inverso (“atrás”).
• Lista circular simplemente enlazada. Una lista enlazada simplemente en la que el último
elemento (cola) se enlaza al primer elemento (cabeza) de tal modo que la lista puede ser
recorrida de modo circular (“en anillo”).
Lista circular doblemente enlazada. Una lista doblemente enlazada en la que el último
elemento se enlaza al primer elemento y viceversa. Esta lista se puede recorrer de modo
circular (“en anillo”) tanto en dirección directa (“adelante”) como inversa (“atrás”).
La implementación de cada uno de los cuatro tipos de estructuras de listas se puede desarrollar
utilizando referencias.
Problema 1:
Confeccionar una clase que administre una lista tipo pila (se debe poder insertar, extraer e imprimir los datos de la pila)
Programa:
public class Pila {
class Nodo {
int info;
Nodo sig;
}
private Nodo raiz;
public Pila () {
raiz=null;
}
public void insertar(int x) {
Nodo nuevo;
nuevo = new Nodo();
nuevo.info = x;
if (raiz==null)
{
nuevo.sig = null;
raiz = nuevo;
}
else
{
nuevo.sig = raiz;
raiz = nuevo;
}
}
public int extraer ()
{
if (raiz!=null)
{
int informacion = raiz.info;
raiz = raiz.sig;
return informacion;
}
else
{
return Integer.MAX_VALUE;
}
}
public void imprimir() {
Nodo reco=raiz;
System.out.println("Listado de todos los elementos de la pila.");
while (reco!=null) {
System.out.print(reco.info+"-");
reco=reco.sig;
}
System.out.println();
}
public static void main(String[] ar) {
Pila pila1=new Pila();
pila1.insertar(10);
pila1.insertar(40);
pila1.insertar(3);
pila1.imprimir();
System.out.println("Extraemos de la pila:"+pila1.extraer());
pila1.imprimir();
}
}
Analicemos las distintas partes de este programa:
class Nodo {
int info;
Nodo sig;
}
private Nodo raiz;
Para declarar un nodo debemos utilizar una clase. En este caso la información del nodo (info) es un entero y siempre el nodo tendrá una referencia de tipo Nodo, que le llamamos sig.
El puntero sig apunta al siguiente nodo o a null en caso que no exista otro nodo. Este puntero es interno a la lista.
También definimos un puntero de tipo Nodo llamado raiz. Este puntero tiene la dirección del primer nodo de la lista. En caso de estar vacía la lista, raiz apunta a null (es decir no tiene dirección)
El puntero raiz es fundamental porque al tener la dirección del primer nodo de la lista nos permite acceder a los demás nodos.
public Pila () {
raiz=null;
}
En el constructor de la clase hacemos que raiz guarde el valor null. Tengamos en cuenta que si raiz tiene almacenado null la lista está vacía, en caso contrario tiene la dirección del primer nodo de la lista.
public void insertar(int x) {
Nodo nuevo;
nuevo = new Nodo();
nuevo.info = x;
if (raiz==null)
{
nuevo.sig = null;
raiz = nuevo;
}
else
{
nuevo.sig = raiz;
raiz = nuevo;
}
}
Uno de los métodos más importantes que debemos entender en una pila es el de insertar un elemento en la pila.
Al método llega la información a insertar, en este caso en particular es un valor entero.
La creación de un nodo requiere dos pasos:
- Definición de un puntero o referencia a un tipo de dato Nodo:
Nodo nuevo;
- Creación del nodo (creación de un objeto):
nuevo = new Nodo();
Cuando se ejecuta el operador new se reserva espacio para el nodo. Realmente se crea el nodo cuando se ejecuta el new.
Paso seguido debemos guardar la información del nodo:
nuevo.info = x;
En el campo info almacenamos lo que llega en el parámetro x. Por ejemplo si llega un 5 el nodo queda:
Por último queda enlazar el nodo que acabamos de crear al principio de la lista.
Si la lista está vacía debemos guardar en el campo sig del nodo el valor null para indicar que no hay otro nodo después de este, y hacer que raiz apunte al nodo creado (sabemos si una lista esta vacía si raiz almacena un null)
if (raiz==null)
{
nuevo.sig = null;
raiz = nuevo;
}
Gráficamente podemos observar que cuando indicamos raiz=nuevo, el puntero raiz guarda la dirección del nodo apuntado por nuevo.
Tener en cuenta que cuando finaliza la ejecución del método el puntero nuevo desaparece, pero no el nodo creado con el operador new.
En caso que la lista no esté vacía, el puntero sig del nodo que acabamos de crear debe apuntar al que es hasta este momento el primer nodo, es decir al nodo que apunta raiz actualmente.
else
{
nuevo.sig = raiz;
raiz = nuevo;
}
Como primera actividad cargamos en el puntero sig del nodo apuntado por nuevo la dirección de raiz, y posteriormente raiz apunta al nodo que acabamos de crear, que será ahora el primero de la lista.
Antes de los enlaces tenemos:
Luego de ejecutar la línea:
nuevo.sig = raiz;
Ahora tenemos:
Por último asignamos a raiz la dirección que almacena el puntero nuevo.
raiz = nuevo;
La lista queda:
El método extraer:
public int extraer ()
{
if (raiz!=null)
{
int informacion = raiz.info;
raiz = raiz.sig;
return informacion;
}
else
{
return Integer.MAX_VALUE;
}
}
El objetivo del método extraer es retornar la información del primer nodo y además borrarlo de la lista.
Si la lista no está vacía guardamos en una variable local la información del primer nodo:
int informacion = raiz.info;
Avanzamos raiz al segundo nodo de la lista, ya que borraremos el primero:
raiz = raiz.sig;
el nodo que previamente estaba apuntado por raiz es eliminado automáticamente por la máquina virtual de Java, al no tener ninguna referencia.
Retornamos la información:
return informacion;
En caso de estar vacía la pila retornamos el número entero máximo y lo tomamos como código de error (es decir nunca debemos guardar el entero mayor en la pila)
return Integer.MAX_VALUE;
Es muy importante entender gráficamente el manejo de las listas. La interpretación gráfica nos permitirá plantear inicialmente las soluciones para el manejo de listas.
Por último expliquemos el método para recorrer una lista en forma completa e imprimir la información de cada nodo:
public void imprimir() {
Nodo reco=raiz;
System.out.println("Listado de todos los elementos de la pila.");
while (reco!=null) {
System.out.print(reco.info+"-");
reco=reco.sig;
}
System.out.println();
}
Definimos un puntero auxiliar reco y hacemos que apunte al primer nodo de la lista:
Nodo reco=raiz;
Disponemos una estructura repetitiva que se repetirá mientras reco sea distinto a null. Dentro de la estructura repetitiva hacemos que reco avance al siguiente nodo:
while (reco!=null) {
System.out.print(reco.info+"-");
reco=reco.sig;
}
Es muy importante entender la línea:
reco=reco.sig;
Estamos diciendo que reco almacena la dirección que tiene el puntero sig del nodo apuntado actualmente por reco.
Gráficamente:
Al analizarse la condición:
while (reco!=null) {
se valúa en verdadero ya que reco apunta a un nodo y se vuelve a ejecutar la línea:
reco=reco.sig;
Ahora reco apunta al siguiente nodo:
La condición del while nuevamente se valúa en verdadera y avanza el puntero reco al siguiente nodo:
reco=reco.sig;
hora sí reco apunta a null y ha llegado el final de la lista (Recordar que el último nodo de la lista tiene almacenado en el puntero sig el valor null, con el objetivo de saber que es el último nodo)
Para poder probar esta clase recordemos que debemos definir un objeto de la misma y llamar a sus métodos:
public static void main(String[] ar) {
Pila pila1=new Pila();
pila1.insertar(10);
pila1.insertar(40);
pila1.insertar(3);
pila1.imprimir();
System.out.println("Extraemos de la pila:"+pila1.extraer());
pila1.imprimir();
}
Insertamos 3 enteros, luego imprimimos la pila, extraemos uno de la pila y finalmente imprimimos nuevamente la pila
Problema 2:
Agregar a la clase Pila un método que retorne la cantidad de nodos y otro que indique si esta vacía.
Programa:
public class Pila {
class Nodo {
int info;
Nodo sig;
}
private Nodo raiz;
Pila () {
raiz=null;
}
public void insertar(int x) {
Nodo nuevo;
nuevo = new Nodo();
nuevo.info = x;
if (raiz==null)
{
nuevo.sig = null;
raiz = nuevo;
}
else
{
nuevo.sig = raiz;
raiz = nuevo;
}
}
public int extraer ()
{
if (raiz!=null)
{
int informacion = raiz.info;
raiz = raiz.sig;
return informacion;
}
else
{
return Integer.MAX_VALUE;
}
}
public void imprimir() {
Nodo reco=raiz;
System.out.println("Listado de todos los elementos de la pila.");
while (reco!=null) {
System.out.print(reco.info+"-");
reco=reco.sig;
}
System.out.println();
}
public boolean vacia() {
if (raiz==null) {
return true;
} else {
return false;
}
}
public int cantidad() {
int cant=0;
Nodo reco=raiz;
while (reco!=null) {
cant++;
reco=reco.sig;
}
return cant;
}
public static void main(String[] ar) {
Pila pila1=new Pila();
pila1.insertar(10);
pila1.insertar(40);
pila1.insertar(3);
pila1.imprimir();
System.out.println("La cantidad de nodos de la lista es:"+pila1.cantidad());
while (pila1.vacia()==false) {
System.out.println(pila1.extraer());
}
}
}
Para verificar si la pila esta vacía verificamos el contenido de la variable raiz, si tiene null luego la lista esta vacía y por lo tanto retornamos un true:
public boolean vacia() {
if (raiz==null) {
return true;
} else {
return false;
}
}
El algoritmo para saber la cantidad de nodos es similar al imprimir, pero en lugar de mostrar la información del nodo procedemos a incrementar un contador:
public int cantidad() {
int cant=0;
Nodo reco=raiz;
while (reco!=null) {
cant++;
reco=reco.sig;
}
return cant;
}
Para probar esta clase en la main creamos un objeto de la clase Pila insertamos tres enteros:
Pila pila1=new Pila();
pila1.insertar(10);
pila1.insertar(40);
pila1.insertar(3);
Imprimimos la pila (nos muestra los tres datos):
pila1.imprimir();
Llamamos al método cantidad (nos retorna un 3):
System.out.println("La cantidad de nodos de la lista es:"+pila1.cantidad());
Luego mientras el método vacía nos retorne un false (lista no vacía) procedemos a llamar al método extraer:
while (pila1.vacia()==false) {
System.out.println(pila1.extraer());
}
Problemas propuestos
Agregar un método a la clase Pila que retorne la información del primer nodo de la Pila sin borrarlo.
Solución
public class Pila {
class Nodo {
int info;
Nodo sig;
}
private Nodo raiz;
Pila () {
raiz=null;
}
public void insertar(int x) {
Nodo nuevo;
nuevo = new Nodo();
nuevo.info = x;
if (raiz==null)
{
nuevo.sig = null;
raiz = nuevo;
}
else
{
nuevo.sig = raiz;
raiz = nuevo;
}
}
public int extraer ()
{
if (raiz!=null)
{
int informacion = raiz.info;
raiz = raiz.sig;
return informacion;
}
else
{
return Integer.MAX_VALUE;
}
}
public int retornar ()
{
if (raiz!=null)
{
int informacion = raiz.info;
return informacion;
}
else
{
return Integer.MAX_VALUE;
}
}
public void imprimir() {
Nodo reco=raiz;
System.out.println("Listado de todos los elementos de la pila.");
while (reco!=null) {
System.out.print(reco.info+"-");
reco=reco.sig;
}
System.out.println();
}
public static void main(String[] ar) {
Pila pila1=new Pila();
pila1.insertar(10);
pila1.insertar(40);
pila1.insertar(3);
pila1.imprimir();
System.out.println("Extraemos de la pila:"+pila1.extraer());
pila1.imprimir();
System.out.println("Retornamos primero de la pila:"+pila1.retornar());
pila1.imprimir();
}
}
Page updated
Report abuse