Listas Doblemente Enlazadas

LISTAS DOBLEMENTE LIGADAS. 

Es una coleccion de nodos, en la cual cada uno de ellos tiene dos apuntadores, uno apuntando a su predecesor (LIGAIZQ) y otra a su sucesor (LIGADER). Por medio de estos punteros se podra entonces avanzar o retroceder a traves de la lista, segun se tomen las direcciones de uno u otro

apuntador.

Las operaciones que se pueden llevar a cabo con este tipo de estructuras son las mismas que con listas simplemente ligadas. En esta seccion se presentaran las operaciones de:

• Recorrido de la lista: Al tener cada nodo  una doble liga, la lista se puede recorrer tanto del inicio al final, mediante la ligas derechas, com en sentido inverso; es decir del final al principio, con las ligas izquierdas.
• Inserccion de un elemento: Agrgar un nuevo nodo a la lista y establecer los apuntadores correspondientes.
• Borrado de un elemento: Eliminar un elemento de la lista, redefiniendo los apuntadores correspondientes y liberando el espacio de memoria ocupado por el nodo.

Listas Enlazadas

Definicion:

Corresponde a una estructura lineal compuesta por una colección de datos homogéneos con alguna relación entre ellos. Dicha estructura se crea a través del método dinámico de memoria.
En una lista enlazada el orden de los elementos está determinado por un campo enlace (puntero) explícito en cada elemento, por ejemplo: pilas y filas dinámicas.
La representación de lista enlazada es la más óptima debido a que cualquier proceso de actualización (modificación inserción o eliminación) se realiza en base a reasignación de punteros. En este capítulo trataremos sólo con las listas enlazadas ya que las listas secuenciales ya son bien conocidas por ustedes.

Operaciones Con Listas:

• Crear una lista vacía.
• Recorrer la lista.
• Buscar un elemento en la lista.
• Insertar nuevos elementos.
• Eliminar elementos ya existente.

Características:

Las   listas   enlazadas   se   implementan   aprovechando   todas   las   ventajas   de   la   asignación   dinámica   de

memoria. Ésta es la forma habitual y más eficaz de realizar su implementación. Sin embargo, ésta no

es la única implementación posible. También pueden ser implementadas estáticamente definiendo el tipo

arreglo como nodos y utilizar los índices en el campo enlace para determinar el siguiente nodo.

Aunque pueda parecer más eficiente implementar una lista enlazada mediante arreglos, realmente no lo es.

En el caso de un arreglo, siempre se deberá mantener una lista paralela de nodos vacíos de manera que

cuando se necesite alojar un nuevo nodo, se tome de esta última lista un nodo disponible y cuando se

quiera liberar un nodo habrá de ser devuelto a la lista.

Es importante observar la distinción existente entre un tipo de datos abstracto y su implementación. Ambos

conceptos  pueden  ser  considerados  de  forma  estática  o  dinámica. Una  variable  de  tipo  array  es  una

estructura  típicamente estática, pero  puede  ser  almacenada  en  memoria  de  forma  estática  o dinámica

(mediante punteros). Lo mismo sucede con los conceptos pila o lista, que por naturaleza son estructuras

puramente dinámicas pero que pueden implementarse con asignación de memoria estática (dentro de un

array).

Programa Lista simplemente enlazada

/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */

/**

 *

 * @author alumno

 */

import java.util.*;

public class ListaLigada {

    public static void main(String[] args) {

        Scanner leer = new Scanner(System.in);

        int num;

        int op;

        LinkedList lista = new LinkedList();

        do{

            System.out.println("\t Menú \t");

            System.out.println("Operaciones con listas");

            System.out.println("1.- Insertar al principio");

            System.out.println("2.- Insertar al final");

            System.out.println("3.- Borrar al principio");

            System.out.println("4.- Borrar al final");

            System.out.println("5.- Mostrar la lista");

            System.out.println("6.- Borrar toda la lista");

            System.out.println("7.- Salir");

            System.out.println("\n");

            System.out.println("Elija la operación que desee");

            op= leer.nextInt();

            switch(op){

                case 1:

                    System.out.println("Inserte numero");

                    num = leer.nextInt();

                    lista.addFirst(num);

                    break;

                case 2:

                    System.out.println("Inserte numero");

                    num = leer.nextInt();

                    lista.addLast(num);

                    break;

                case 3:

                    System.out.println("Se borrara el primer nodo");

                    lista.removeFirst();

                    break;

                case 4:

                    System.out.println("Se borrara el nodo final");

                    lista.removeLast();

                    break;

                case 5:

                    System.out.println("La lista es la siguiente");

                    List lista2= new ArrayList(lista);

                    Iterator it = lista2.iterator();

                    while(it.hasNext()){

                        System.out.println(it.next()+"");

                    }

                    break;

                case 6:

                    System.out.println("Se borraran todos los elementos de la lista");

                    lista.clear();

                    break;

                case 7:

                    System.out.println("Al rato");

                    break;

            }

        }

        while(op!=7);

    }

}