Estructuras Dinámicas
Dinamica Lineales
- Listas Enlazadas.- Simples, Dobles, Circulares
- Pilas
- Cola
- Bicola
Dinamica No lineales
- -Arboles.-Binarios, Binarios De Búsqueda
- -Grafos
Una lista enlazada es una serie de nodos, conectados entre sí a través de una referencia, en donde se almacena la información de los elementos de la lista. Por lo tanto, los nodos de una lista enlazada se componen de dos partes principales:
class NodoLista
{
Object elemento;
NodoLista siguiente;
}
La referencia contenida en el nodo de una lista se denomina siguiente, pues indica en dónde se encuentra el siguiente elemento de la lista. El último elemento de la lista no tiene nodo siguiente, por lo que se dice que la referencia siguiente del último elemento es null (nula).
La siguiente figura muestra un ejemplo de una lista enlazada cuyos elementos son strings:
NodoLista aux=lista;
Siguiendo con el ejemplo anterior, para insertar un nuevo nodo justo delante del nodo referenciado por aux se deben modificar las referencias siguiente del nodo aux y del nodo a insertar.
NodoLista nuevo=new NodoLista(...);
//"nuevo" es la referencia del nodo a insertar en la lista
nuevo.siguiente=aux.siguiente;
aux.siguiente=nuevo;
//Notese que no es lo mismo realizar los cambios de referencia
//en un orden distinto al presentado, puesto que en ese caso
//se "pierde" la lista desde el nodo siguiente a aux
El procedimiento presentado a continuación es un ejemplo de cómo se programa el recorrido de una lista enlazada. Se supondrá que los objetos almacenados en cada nodo son strings:
void recorrido(NodoLista lista)
{
NodoLista aux=lista;
while (aux!=null)
{
System.out.println(aux.elemento);
aux=aux.siguiente;
}
}
Para invertir el orden de la lista, es decir, que el último elemento de la lista ahora sea el primero, que el penúltimo elemento de la lista ahora sea el segundo, etc..., modificando sólo las referencias y no el contenido de los nodos, es necesario realizar una sola pasada por la lista, y en cada nodo visitado se modifica la referencia siguiente para que apunte al nodo anterior. Es necesario mantener referencias auxiliares para acordarse en donde se encuentra el nodo anterior y el resto de la lista que aún no ha sido modificada:
void invertir(NodoLista lista)
{
NodoLista siguiente=lista;
NodoLista anterior=null;
while(lista!=null)
{
siguiente=lista.siguiente;
lista.siguiente=anterior;
anterior=lista;
lista=siguiente;
}
}
La implementación vista de los nodos también se conoce como lista de enlace simple, dado que sólo contiene una referencia al nodo siguiente y por lo tanto sólo puede recorrerse en un solo sentido. En una lista de doble enlace se agrega una segunda referencia al nodo previo, lo que permite recorrer la lista en ambos sentidos, y en general se implementa con una referencia al primer elemento y otra referencia al último elemento.
Lista Circular
Una lista circular es aquella en donde la referencia siguiente del último nodo en vez de ser null apunta al primer nodo de la lista. El concepto se aplica tanto a listas de enlace simple como doblemente enlazadas.
En muchas aplicaciones que utilizan listas enlazadas es útil contar con un nodo cabecera, tambien conocido como . que es un nodo "falso", ya que no contiene información relevante, y su referencia siguiente apunta al primer elemento de la lista. Al utilizar un nodo cabecera siempre es posible definir un nodo previo a cualquier nodo de la lista, definiendo que el previo al primer elemento es la cabecera.
Si se utiliza un nodo cabecera en una lista de doble enlace ya no es necesario contar con las referencias primero y último, puesto que el nodo cabecera tiene ambas referencias: su referencia siguiente es el primer elemento de la lista, y su referencia anterior es el último elemento de la lista. De esta forma la lista de doble enlace queda circular de una manera natural
.
-BUSCAR
Buscando un elemento específico en una lista enlazada, incluso si esta es ordenada, normalmente requieren tiempo O (n) (búsqueda lineal). Esta es una de las principales desventajas de listas enlazadas respecto a otras estructuras. Además algunas de las variantes expuestas en la sección anterior, hay numerosas vías simples para mejorar el tiempo de búsqueda.
-ORDENAR
OPERACIONES
Constructor
Lista vacia
CONSTRUCTOR
//Lista vacia
1…Public lista(string n){
Nombre=n;
Pri=ult=null;
}
2…Public boolean ListaVacia(){
Return (pri==null);
}
INSERCIONES.-
FRENTE
POSTERIOR
POS-N
1…Insertar al frente
La Inserción al Principio básicamente busca si existe algún lugar disponible en el arreglo Info. y lo agrega como primer Nodo si es que es posible .
Public void InsertarFrente(Object obj){
If (ListaVacia())
Prim=ult=null(obj);
Else
Prim=new Nodo(obj, pri);
}
2…INSPOSTERIOR
La Inserción después de un Nodo Determinado básicamente hace lo mismo que la inserción al principio, la única diferencia es que este recibe la posición del nodo en la que será Insertada. Este Algoritmo se usa para Inserción Ordenada que más adelante
Public void InsPosterior(Object obj){
If (listaVacia())
Prim=ult=new nodo(obj);
Else
Ult=ult.sig=new nodo(obj);
}
-CONTAR NODO DE UNA LISTA
Public int contnodos(){
Nodo Actual=Prim; int cont=0;
While(Actual !=null){
Cont++;
Actual=Actual.sig;//avanza
}
Return cant;
}
}
3….InsPos_n
Public void insPos_n(object obj, int pos){
If (ListaVacia())
InsertaFrente();
Else{
If(pos==1){insertaFrente();}
If (pos==ContElem()){insertaPosterior;
Else{
Nodo Actual=Prim;
For(int i=0; i<=pos_n; i++){
Actual=Actual.sig;
Nodo Nuevo=new Nodo(obj, Actual.sig)
Actual sig=nuevo;
}
}
Public class lista simple{
Private nodo prim;
Private nodo ult;
Private string nombre;
}
Public lista Simple (){
Prim=ult=null;
Nombre=””;
}
Public lista simple(string n){
Prim=ult=null;
Nombre=n;
}
Public Boolean ListaVacia(){
Return prim==null;
}
Public void InsFrente( Object obj){}
Public void Insposterior(Object obj){}
Public void insposicion(Object obj, int pos){}
-ELIMINACIONES
Public object DelFrente(){
If (Listavacia()) trows excepcion
Object datoARemover=prim.dato;
If(prim.equals cult)
Prim=ult=null;
Else{
Nodo Actual=prim;
Prim=prim.sig;
Actual.sig=null;
}
Return datoARemover;
}
DELPOSTERIOR
1
If(listaVacia())
Object DatoARemover=ult.dato;
2
If(prim.equals(null))
Prim=ult=null;
3
Else{
Nodo Actual=pri;
While(Actual.sig !=ult)
Actual=Actual.sig;
}
DELPOS_N
Public void ElemPos_n(Object , int Pos)
If(listaVacia()) {ElimFrente();}
Else{
If(pos==1){ElimFrente();}
If(pos==cantElem());{elemPost();}
Else{
Nodo=Actual=prim;
For(int i=1; i<=Pos_n; i++){
Actual=Actual.sig;
datoARemover=Pos.Dato;
}
Return DatoaRemover;
}
}
//PARA ELIMINAR ENTRE MEDIO Y ENLAZAR AL SIGUIENTE
Public object DelPos ( int Pos) {
If ( ListaVacia)
If (Pos == 1)DelFrente(){
If (Pos == numElemen)DelPosterior();
Else {
Object DatoARemoer
If (prim.equals(ult)){
Prim = ult = null;
Return DatoARemover;
}
Else{
Nodo actual = prim;
For (int i = 1; i <= pos; i++){
Actual = actual.sig;
DatoARemover = (actual.sig).Dato
(aBorrar.Dato)
Actual.sig = (actual.sig).sig;
(aBorrar.sig) ;
aBorrar.sig = null;
return DatoARemover;
}
}
}
}
//MODIFICACIONES AL FRENTE
Algoritmo completo
Public void update frente (object obj new )
If( listaVacia())
Else
Prim.Dato = obj new;
//MODIFICACIONES POSTERIOR
Algoritmo completo
Public void update post (object obj )
If( listaVacia())
Else
ult.Dato = obj;
//MODIFICA LA POSICION
Algoritmo completo
Public void update pos (object obj new, int pos ){
If( listaVacia()) //ERROR
If(pos == 1) updateFrente(obj new) ;
If(pos == numElemen) update post (object new) ;
Else{
nodo.actual = prim;
for( int i = 1; I <= pos; i++)
actual = actual.sig;
actual.dato = obj new;
}
}
//MOSTRAR LISTA
Public void mostrarLista(){
Nodo.actual = prim;
While( actual != null)
Joptionpane (actual.dato)
Actual = actual.sig;
LISTA DOBLE CIRCULARRealizar el siguiente recorrido
1; 1-2-3-2 = (actual.sig.sig).ant
2; 2-3-4-1-4 = (((actual.sig).sig).sig).ant
3; 1-2-1-4 = (((actual.sig).ant).sig)
Recorrido optimo
4; 1-4 = actual.ant
5; 3-1 = (actual.ant).ant
6; 2-4 = (actual.sig ).sig
Class nodoDoble{
Object Dato ;
Nodo sig;
Nodo ant;
Public nodoDato() { }
}
Class listaDobleCircular{
String Nombre;
Nodo ultimo;
Nodo actual; // OPCIONAL
}
INSERCIONES
insUltimo
Nuevo.sig = ultimo.sig;
Nuevo.ant = ultimo;
Ultimo.sig.ant = Nuevo;
Ultimo.sig = Nuevo;
Ultimo = Nuevo;
InsPos_n
Nuevo.sig = actual.sig;
Nuevo.ant = actual;
Actual.sig.ant = Nuevo;
Actual.sig = Nuevo;
Eliminaciones
*DeleteUltimo
1 actual.sig = ultimo.sig;
2 actual.sig.ant = actual;
3 ultimo = null;
Ultimo.ant = ultimo.sig = null;
deletePrimero
1 actual sig.ant = ultimo;
2 ultimo.sig = actual.sig;
3 actual.sig = actual.ant =null;
Del Pos_n
Aux.sig = actual.sig;
Actual.sig.ant = aux;
Actual.sig = actual.ant = null;
Trabajo corregido!
ResponderEliminarhola no tienes el metodo de busqueda para una cola dinamica
ResponderEliminar