04 listas enlazadas
DESCRIPTION
listas enlazadasTRANSCRIPT
-
1
PROGRAMA
ASIGNATURA ESTRUCTURAS DE DATOS
TEMA LISTAS ENLAZADAS
Concepto Estructura de datos Una estructura de datos es una clase contenedora que proporciona almacenamiento para items de datos y capacidades para almacenar y recuperar esos datos.
Concepto Abstraccin La abstraccin es un proceso mental mediante el cual se entiende que al conocer un objeto, entonces se conocen todas sus caractersticas. Por ejemplo, al nombrar el objeto Computador, entonces se sabe que con l se pueden hacer programas, navegar en Internet, guardar informacin, y adems tiene tamao, velocidad, memoria RAM, etc. Al conocer el objeto, entonces se ABSTRAEN todas sus propiedades, funciones y caractersticas.
En ste ejemplo, Computador es el Tipo Abstracto de Dato. Entonces, Abstraccin de datos es el proceso mediante el cual se define, implementa y se usa un TIPO DE DATO ABSTRACTO. Se podra decir que un TIPO DE DATO ABSTRACTO (TDA) corresponde a un conjunto de propiedades de una entidad y las operaciones o funciones que los afectan. TDA bsicos son LISTAS ENLAZADAS, PILAS, COLAS, ARBOL, TABLAS HASH.
-
2
Listas enlazadas Es necesario entender primero que los arrays tienen algunas desventajas como:
En un array desordenado la bsqueda es lenta.
En un array ordenado la insercin es lenta.
En ambos casos, la eliminacin es lenta.
El tamao de un array no se puede cambiar despus de creado. Estos problemas se solucionan con las estructuras de datos llamadas Lista Enlazada. La Lista Enlazada es una estructura en la cual los elementos se almacenan de forma no adyacente, en vez de un vector de posiciones de memoria consecutivas. Una de las ventajas ms importantes de la Lista Enlazada es la optimizacin del uso de memoria pues no se desperdicia el espacio de nodos vacos, como sucede como los arrays, pues los arrays reservan el espacio de memoria aun cuando no la use. Cada elemento de la lista enlazada se almacena en un NODO que contiene el objeto y una referencia. La mayor desventaja de la Lista Enlazada es que para localizar un dato especfico debe ser recorrida desde el inicio, lo que quiere decir que no se puede ir al i-simo elemento como se hace en un array. Existen tres (3) tipos de listas:
1. Lista enlazada simple 2. Lista doblemente enlazada 3. Lista circular
Lista enlazada simple
-
3
Lista doblemente enlazada Tiene enlace al nodo siguiente pero tambin al nodo anterior.
Lista circular En una lista enlazada circular, el primer y el ltimo nodo estn unidos. El ltimo nodo apunta al primero.
-
4
Lista enlazada simple Una Lista Enlazada est compuesta por una serie de Nodos, donde cada Nodo contiene el dato almacenado y una referencia al siguiente Nodo de Lista; de este modo la Lista slo necesita una referencia al primer Nodo para poder tener acceso a todos sus elementos. La lista enlazada est compuesta por:
1. Una clase auto-referenciada, con al menos un campo cuyo tipo de referencia es el nombre de la clase.
2. Nodo: un objeto creado desde una clase auto-referenciada. 3. Campo de enlace: un campo cuyo tipo de referencia es el nombre de la clase. 4. Enlace: la referencia a un campo de enlace. 5. Y la clase que genera la lista enlazada.
class Empleado { private int numeroemp; private String nombre; private double salario; public Empleado next; } Esta clase es auto-referenciada porque el campo next tiene el tipo Empleado. En el cdigo anterior, next es un campo de enlace. Por el contrario, numeroemp, nombre, y salario son campos no de enlace. En el cdigo anterior, la referencia next a un nodo Empleado es un enlace.
-
5
EJERCICIO DE CLASE Implemente el siguiente cdigo de lista enlazada en un programa que capture las notas del primer corte de los estudiantes del curso. Recuerde que el programa debe:
1. Capturar la nota de cada estudiante 2. Indicar la nota mxima 3. Indicar la nota mnima 4. Indicar el promedio de las notas
Pero es muy importante que analice el funcionamiento de los mtodos sobre la lista enlazada. //Esta es la clase Nodo;
public class Nodo {
//Atributos de la clase nodo
Object Dato;
Nodo Sig;
//Constructor del nodo para crear un objeto
public Nodo(Object Valor){
Dato=Valor;
Sig=null;
}
//Constructor del nodo para crear un objeto del siguiente nodo
public Nodo(Object Valor,Nodo Sign){
Dato=Valor;
Sig=Sign;
}
}
//Ahora la clase Lista
import javax.swing.JOptionPane;
public class Lista {
//Atributos de la lista
Nodo Pri;
Nodo Ult;
String Nom;
//Constructor de la lista
public Lista(String n){
Pri=Ult=null;
Nom=n;
}
-
6
//Constructor
public boolean ListaVacia(){//EN CASO DE QUE LA LISTA ESTE VACIA
if(Pri==null){
return true;
}
else{
return false;
}
}
//Nombre de la lista
public Lista(){
this("Lista");
}
//Metodo para insertar por el frente de la lista
public void Ifrente(Object Elem){
if(ListaVacia()){
Pri=Ult=new Nodo(Elem);
}
else{
Pri=new Nodo(Elem,Pri);
}
}
//Metodo para insertar por la parte posterior de la lista
public void Iposterio(Object Elem){
if(ListaVacia()){
Pri=Ult=new Nodo(Elem);
}
else{
Ult=Ult.Sig=new Nodo(Elem);
}
}
//Metodo para mostrar los datos de la lista
public void Mostrar(){
Nodo Actual=Pri;
if(ListaVacia()){
System.out.println("La "+Nom+" esta vacia");
}
while(Actual!=null){
System.out.println(Actual.Dato);
Actual=Actual.Sig;
}
}
//Metodo para eliminar el frente de la lista
public void Efrente(){
if(ListaVacia()){
Pri=Pri.Sig;
-
7
}
else if(Pri.equals(Ult)){
Pri=Ult=null;
}
else{
Pri=Pri.Sig;
}
}
//Metodo para eliminar el posterior de la lista
public void Eposterior(){
if(ListaVacia()){
Pri=Pri.Sig;
}
else if(Pri.equals(null)){
Ult=null;
}
else{
Pri=Pri.Sig;
}
}
}
PSEUDOCODIGOS
Empieza la lista de enlace simple
-
8
Insertar un Nodo antes del primer nodo
Insertar un Nodo despus del ltimo Nodo
-
9
Insertar un Nodo entre dos nodos
Imgenes tomadas de: www.programacion.com Anlisis del algoritmo de ingresar un nodo entre otros dos public void Agregaentredos(Object m){
if(ListaVacia()){
System.out.println("La "+Nom+" esta vacia");
} else {
temp = new Nodo(m);
Nodo Actual=Pri;
while(Actual.Dato.equals(2)== false){ //inserta despus del nodo 2
Actual=Actual.Sig;
}
temp.Sig = Actual.Sig ;
Actual.Sig = temp;
}
-
10
Pseudocdigo de agregar un nodo entre otros dos Si ListaVacia entonces Muestre Lista est vacia De lo contrario Crear Nodo temporal
Ir al primer nodo Recorrer lista hasta encontrar nodo //Saltar al siguiente nodo Actual = Actual.siguiente Fin recorrido //Al encontrar el nodo donde se desea insertar Referencia temporal siguiente = Actual siguiente Referencia actual siguiente = Temporal Fin si
Borrar cualquier nodo que no sea el primero Localiza el nodo que precede al nodo a borrar y le asigna el enlace que hay en el campo next del nodo a borrar al campo next del nodo que le precede. En el siguiente ejemplo vamos a borrar el nodo D.
Pseudocdigo de borrar cualquier elemento que no sea el primero Ir al nodo inicial Buscar el nodo que se desea borrar Al nodo anterior hacerlo apuntar al nodo subsiguiente
-
11
El siguiente ejemplo borrar el nodo que queda despus del nodo 9. Lista enlazada (4,1,9,2,3) public void borracualquiera(){
Nodo Actual=Pri; //Se ubica en el primer nodo
while(Actual.Dato.equals(9)== false){
Actual=Actual.Sig;
}
Actual.Sig = Actual.Sig.Sig;
}
Investiga: Cmo borrar preguntando antes que nodo se desea borrar?
Lista doblemente enlazada Las listas de enlace simple restringen el movimiento por lo nodos a una sola direccin. Problemas de la lista enlazada simple No se puede recorrer una lista de enlace simple en direccin opuesta a menos que se use un algoritmo de inversin (esto lleva ms tiempo). Se tendra que repetir el algoritmo de inversin para volverlo al estado original. No se puede borrar un nodo sin acceder al nodo predecesor. Estos problemas se solucionan con la LISTA DOBLEMENTE ENLAZADA. En la LISTA DOBLEMENTE ENLAZADA cada nodo tiene un par de campos de enlace. Un campo de enlace permite atravesar la lista hacia adelante, mientras que el otro permite atravesar la lista haca atrs. Cada nodo se enlaza con el siguiente mediante el campo de enlace next, excepto el ltimo nodo, cuyo campo de enlace next contiene null para indicar el final de la lista (en direccin hacia adelante). Para la direccin hacia atras, una variable de referencia contiene una referencia al ltimo nodo de la direccin normal (hacia adelante), lo que se interpreta como el primer nodo. Cada nodo se enlaza con el anterior mediante el campo de enlace previous, y el primer nodo de la direccion hacia adelante, contiene null en su campo previous para indicar el fin de la lista.
-
12
El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la
lista).
El puntero siguiente del ltimo elemento debe apuntar hacia NULL (el fin de la lista).
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:
Comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el prximo elemento.
Comenzando por el final, el puntero anterior permite el desplazamiento hacia el elemento anterior.
Piense: Qu pasa cuando se inicia la creacin de la lista doblemente enlazada? El primer nodo que se crea ser el nodo inicial y el nodo final.
Mtodos de la lista doblemente enlazada Agregar al final public void agregaralfinal(String dato){
Nodo2 nuevo = new Nodo2(dato);
if(estaVacia()){
topehaciaadelante = nuevo;
topehaciaatras = nuevo;
} else {
topehaciaatras.next = nuevo;
nuevo.next = null;
nuevo.prev = topehaciaatras;
topehaciaatras = nuevo;
}
}
-
13
Agregar al inicio public void agregaralinicio(String dato){
Nodo2 nuevo = new Nodo2(dato);
if(estaVacia()){
topehaciaadelante = nuevo;
topehaciaatras = nuevo;
} else {
topehaciaadelante.prev = nuevo;
nuevo.next = topehaciaadelante;
topehaciaadelante = nuevo;
}
} Borrar al final public void borraralfinal(){
if(estaVacia()){
System.out.println("Esta vaca");
} else {
Nodo2 ultimo = topehaciaatras.prev;
ultimo.next = null;
topehaciaatras = ultimo;
}
} Borrar al inicio public void borraralinicio(){
if(estaVacia()){
System.out.println("Esta vaca");
} else {
Nodo2 primero = topehaciaadelante.next;
primero.prev = null;
topehaciaadelante = primero;
}
} Buscar un nodo public String buscar(String dato){
Nodo2 buscado = null;
Nodo2 iterador = topehaciaadelante;
while(iterador != null && buscado == null){
if(iterador.name == dato){
buscado = iterador;
} else {
iterador = iterador.next;
}
}
return dato;
}
-
14
Lista enlazada circular El campo de enlace del ltimo nodo de una lista de enlace simple contiene un enlace nulo, ocurre lo mismo en los campos de enlace del primer y ltimo elemento en ambas direcciones en las listas doblemente enlazadas. En la lista enlazada circular, el ltimo nodo contiene la referencia al primer nodo.
Las operaciones que se realizan sobre una lista circular son similares a las operaciones sobre listas lineales, teniendo en cuenta que no hay primero ni ltimo nodo, aunque s un nodo de acceso a la lista. La construccin de una lista circular se puede hacer con enlace simple o enlace doble. Analicemos el siguiente cdigo: //Clase Nodo para la lista circular doblemente enlazada
public class Nodolc {
int info;
Nodolc ant,sig;
public void Nodolc(){
ant = null;
sig = null;
}
} //lista circular doblemente enlazada
public class ListaCircular {
private Nodolc raiz;
public ListaCircular () {
raiz=null;
}
public void insertarPrimero(int x) {
Nodolc nuevo = new Nodolc();
nuevo.info=x;
if (raiz==null) {
nuevo.sig=nuevo;
nuevo.ant=nuevo;
raiz=nuevo;
} else {
Nodolc ultimo=raiz.ant;
nuevo.sig=raiz;
-
15
nuevo.ant=ultimo;
raiz.ant=nuevo;
ultimo.sig=nuevo;
raiz=nuevo;
}
}
public void imprimir ()
{
if (!vacia()) {
Nodolc reco=raiz;
do {
System.out.print (reco.info + "-");
reco = reco.sig;
} while (reco!=raiz);
System.out.println();
}
}
public void insertarUltimo(int x) {
Nodolc nuevo=new Nodolc();
nuevo.info=x;
if (raiz==null) {
nuevo.sig=nuevo;
nuevo.ant=nuevo;
raiz=nuevo;
} else {
Nodolc ultimo=raiz.ant;
nuevo.sig=raiz;
nuevo.ant=ultimo;
raiz.ant=nuevo;
ultimo.sig=nuevo;
}
}
public boolean vacia ()
{
if (raiz == null)
return true;
else
return false;
}
public int cantidad ()
{
int cant = 0;
if (!vacia()) {
Nodolc reco=raiz;
do {
cant++;
reco = reco.sig;
} while (reco!=raiz);
}
return cant;
}
public void borrar (int pos)
{
if (pos
-
16
if (cantidad()==1) {
raiz=null;
} else {
Nodolc ultimo=raiz.ant;
raiz = raiz.sig;
ultimo.sig=raiz;
raiz.ant=ultimo;
}
} else {
Nodolc reco = raiz;
for (int f = 1 ; f