LISTAS SIMPLES Y DOBLES

Listas simples enlazadas :





La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.







Lista Doblemente Enlazada :





Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL o a la lista vacía si es el primer nodo; y otro que apunta al siguiente nodo siguiente, o apunta al valor NULL o a la lista vacía si es el último nodo.






Aplicaciones de las listas enlazadas :



Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.
A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos






OPERACIONES CON LISTAS SIMPLES:







1. Insertar
2. Borrar
3. Buscar
4. Recorrer
5. Vacio
6.Tamaño





OPERACIONES CON LISTAS DOBLES:




1. Buscar

2. Insertar

3. Eliminar

4. Recorrer

5. Vacio





// EN LISTAS SIMPLES:

PUBLIC VOID ( INSERTAR) ( STRING ELEMENTO);
PUBLIC BOOLEAN ELIMINAR ( STRING ELEMENTO);
PUBLIC STRING ELIMINAR ();
PUBLIC BOOLEAN BUSCAR ( STRING ELEMENTO);
PUBLIC STRING RECORRER();
PUBLIC BOOLEAN VACIO();
PUBLIC INT TAMAÑO ();
// EN LISTAS DOBLES:
FUNCIONES:


- get_first: Obtiene el primero y regresa los datos a el nodo cabecera.
- get_last: Obtiene el ultimo y regresa los datos al nodo cola.
- IS_empty: (Vacio) Regresa informacion sobre la lista esta vacia o no?
- java.util




El siguiente código inserta un elemento a continuación de otro en una lista simple. El diagrama muestra como funciona:














De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista:



SIMPLES:

Insertar

ANTES / DESPUES

Pseudocodigo:

p __cab

mensaje (antes/ despues);

Si antes entonces

Mientras que p < > null Haga

Si p (dato) = " x " entonces

new (q)

leer

(q (dato)

Aant[ ]

Bdes----

EN JAVA:

Nodo inicio

public Lista ( ) {

inicio = null;

}

public boolean vacia ( ) {

return ( inicio = null );

}

public int tamaño ( ){

int n = o

Nodotemporal = inicio

While ( temporal ! = null ) {

n ++

temporal = temporal.enlace

}

return n;

}

public boolean Buscar ( string elemento ){

Nodotemporal = inicio;

while ( temporal ! = null

if elemento.equals ( temporal.dato))

return true;

else

temporal = temporal.enlace

}

return false;

}

LISTAS ENLAZADAS

-isEmpty: Determina su la lista esta vacia.

-Size: Determina el numero de elementos en la lista.

DECLARAR UN NODO

Declare ClassNodo

Declare String Name

Declare NodoNext

end declare

Declare Nodo top = null

top = new nodo

top.name= " a"

top.next = null

* Informacion

- Entero

- Real

- String

EN LISTAS DOBLES:

Insertar un nodo en la ultima posicion:

temp = new nodo

temp.name = " c "

temp.next = null

while temp2. next is not null

temp2 = temp2.next

end while

temp2. next = temp

No hay comentarios:

Publicar un comentario en la entrada