Listas Simples

Concepto Listas:

Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los array convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Tipo de Listas:

Existen diferentes tipos de listas como las pueden ser: simples o sencillas, circulares y dobles.

 

Listas simples o sencillas:

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.

 

 Listas Dobles:

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 si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.

Listas circulares:

En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Operaciones con Listas:

Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:

• Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
• Insertar un nodo al inicio.
• Insertar un nodo antes o después de cierto nodo.
• Insertar un nodo al final. 

• 
  
  
  
   
  
  
• Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:
• Eliminar el primer nodo.
• Eliminar el último nodo.
• Eliminar un nodo con cierta información.
• Eliminar el nodo anterior o posterior al nodo cierta con información. 

• 
  
   
  
  
  
  
  
  
  
  
   
 

• Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.  

• Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.

Programa1: 

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 Menu\t");
            System.out.println("Operaciones con listas");
            System.out.println("1.-Insertar al principio");
            System.out.println("2.- Insertar al dinal");
            System.out.println("3.- Borrar al proncipio");
            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 operacion que desee");
            op= leer.nextInt();
            switch(op){
            case 1:
                System.out.println("Insertar numero");
                num= leer.nextInt();
                lista.addFirst(num);
                break;
                case 2:
                    System.out.println("inserte numero");
                    num=leer.nextInt();
                    lista.addFirst(num);
                    break;
                case 3:
                    System.out.println("Se borro el primer nodo");
                    lista.removeFirst();
                    break;
                case 4:
                    System.out.println("Seborra 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 borran todos los elementos de la lista");
                    lista.clear();
                    break;
                case 7:
                    System.out.println("Al rato");
                    break;
                   
            }
               
            }
        while(op!=7);
        }
       
    }

 }

Programa2:

import java.util.*;

import ListaEnteros.ListaOrdenada;

public class ListaEnOrden

{

public static void main(String [] a)
{

Random r;
int d;
ListaOrdenada lista;
int k;

r = new Random(); // generador de números aleatorios
lista = new ListaOrdenada(); // crea lista vacía
k = r.nextInt(99)+1;// número de elementos

// inserta elementos en la lista

for (; k >= 0; k-- )
{

d = r.nextInt();

lista.insertaOrden(d);

}// escribe los elementos de la lista

System.out.println("Elementos de la lista ordenada \n");

lista.visualizar();

}

}

 Programa3:

package listaDobleEnlace;

public class IteradorLista

{
Nodo actual;
public IteradorLista(ListaDoble ld)
{

actual = ld.cabeza;

}

public Nodo siguiente()

{
Nodo a;
a = actual;
if (actual != null)
{

actual = actual.adelante;

}return a;

}

}

 


Videos:

Bibliografia 

http://angielastra.blogspot.com/2010/11/listas.html

http://sistemas.itlp.edu.mx/tutoriales/estru1/42.htm