Lista Simplemente Enlanzada

 Ahora se creara una Lista Simple en equipo bajo las siguientes personas:
-Gustavo Richart Rios
-Luis Guillermo Gonzales
-Erick Martin Guzman
1) Concepto
Las listas enlazadas son estructuras de datos semejantes a los array salvo que el acceso a un elemento no se hace mediante un indice sino mediante un puntero.
La asignación de memoria es hecha durante la ejecución.
En una lista los elementos son contiguos en lo que concierne al enlazado.






En cambio, mientras que en un array los elementos están contiguos en la memoria, en una lista los elementos están dispersos.
El enlace entre los elementos se hace mediante un puntero.
En realidad, en la memoria la representación es aleatoria en función del espacio asignado.

El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista).

Para acceder a un elemento, la lista es recorrida comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
El desplazamiento se hace en una sola dirección, del primer al último elemento.
Si deseas desplazarte en las dos direcciones (hacia delante y hacia atrás) deberás utilizar las [ listas doblemente enlazadas]
2) Aplicacion

Listas Simples Enlazadas

Nuestra estructura de datos tendrá dos campos. Vamos a mantener la variables PrimerNodos que siempre apunta al primer nodo de tal lista, ó nulo para la lista vacía.

record Node {
    data // El dato almacenado en el nodo
    next // Una referencia al nodo siguiente, nulo para el último nodo
 }

record List {
     Node PrimerNodo   // Apunta al primer nodo de la lista; nulo para la lista vacía
 }

El recorrido en una lista enlazada es simple, empezamos por el primer nodo y pasamos al siguiente hasta que la lista llegue al final.

node := list.PrimerNodo
 while node not null {
     node := node.next
 }

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

function insertAfter(Node node, Node newNode) {
     newNode.next := node.next
     node.next    := newNode
 }

Insertar al principio de una lista requiere una función por separado. Se necesita actualizar PrimerNodo.

function insertBeginning(List list, Node newNode) {
     newNode.next   := list.firstNode
     list.firstNode := newNode
 }

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

function removeAfter(Node node) { 
     obsoleteNode := node.next
     node.next := node.next.next
     destroy obsoleteNode
 }

function removeBeginning(List list) { 
     obsoleteNode := list.firstNode
     list.firstNode := list.firstNode.next          
     destroy obsoleteNode
 }

Advertimos que BorrarPrincipio pone PrimerNodo a nulo cuando se borra el último elemento de la lista. Adjuntar una lista enlazada a otra puede resultar ineficiente a menos que se guarde una referencia a la cola de la lista, porque si no tendríamos que recorrer la lista en orden hasta llegar a la cola y luego añadir la segunda lista.
3) Video
Parte 1

Parte 2

4) Imagenes
EJemplo

Insertar datos

Insertar al inicio

Insertar al final

Eliminar al inicio

5) Programa

/*
 * Lista Simplemente enlazada.
 *
 */ /**
 *
 * @author Pain
 */
//Clase Nodo. Utiliza el enlace llamado nodoDer o nodo derecho y el valor a introducir.
public class Nodo {
    Nodo nodoDer;
    int dato;
    public Nodo(int dato) {
        this.dato = dato;
        this.nodoDer = null;
    }
}
/*
 * Clase de Lista enlazada y metodos de agregar al final y borrar del mismo, asi como mostrar tamaño y visualizar lista.
 *
 */
import javax.swing.JOptionPane;
/**
 *
 * @author Pain
 */
public class ListaS {
    private Nodo primero;
    private Nodo ultimo;
    private int tamano;
    public ListaS() {
        this.primero = null;
        this.ultimo = null;
        this.tamano = 0;
    }
//Metodo utilizado para denotar que la lista se encuentra vacia.
    public boolean siVacio() {
        return (this.primero == null);
    }
//Metodo para agregar al final de la lista.
    public ListaS addLast(int dato) {
        if(siVacio()) {
            Nodo nuevo = new Nodo(dato);
            primero = nuevo;
            ultimo = nuevo;
            nuevo.nodoDer = nuevo;
        }
        else {
            Nodo nuevo = new Nodo(dato);
            nuevo.nodoDer = null;
            ultimo.nodoDer = nuevo;
            ultimo = nuevo;
        }
        this.tamano++;
        return this;
    }
//Metodo para borrar al final de la lista.
    public Nodo deleteLast() {
        Nodo eliminar = null;
        if(siVacio()) {
            JOptionPane.showMessageDialog(null, "La lista se encuentra vacia");
            return null;
        }
        if(primero == ultimo) {
            primero = null;
            ultimo = null;
        }
        else {
            Nodo actual = primero;
            while(actual.nodoDer != ultimo) {
                actual = actual.nodoDer;
            }
            eliminar = actual.nodoDer;
            actual.nodoDer = null;
            ultimo = actual;
        }
        this.tamano--;
        return eliminar;
    }
//Metodo que imprime el tamaño de la lista.
    public void tamano() {
        JOptionPane.showMessageDialog(null, "El tamaño es:\n " + this.tamano);
    }
//Metodo que imprime la lista y los valores ingresados.
    public void imprimir() {
        if(tamano != 0) {
            Nodo temp = primero;
            String str = "";
            for(int i = 0; i < this.tamano; i++) {
                str = str + temp.dato + "\n";
                temp = temp.nodoDer;
            }
            JOptionPane.showMessageDialog(null, str);
        }
    }
}

Creditos y Agradecimientos

  

Introduccion

Bienvenido
Aqui se explicara todo lo relacionado a la estructura y organizacion de datos bajo los siguientes datos:
-Conceptos
-Investigacion
-Aplicacion
-Videos