Algoritmos y Estructura de Datos

Una lista simplemente enlazada es la más fundamental estructura de datos basada en punteros, y del concepto fundamental de ésta derivan las 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.

En estas listas tenemos "nodos" que son objetos que se irán enlazando entre ellos para formar la lista completa. Los nodos tienen principalmente dos atributos: un atributo "contenido", usado para almacenar un objeto en donde se contendrá la información requerida; y otro atributo "siguiente", usado para hacer referencia al siguiente nodo de la lista.

Implementación:

Para implementar una lista simple enlazada, se define una clase Nodo, la cual indica el tipo de los objetos guardados en los nodos de la lista. Para este caso se asume que los elementos son String (puede ser cualquier tipo). También es posible definir nodos que puedan guardar tipos arbitrarios de elementos.

Dada la clase Nodo, se puede definir una clase, ListaSimple, definiendo la lista enlazada actual. Esta clase guarda una referencia al nodo cabeza y una variable va contando el número total de nodos.

                    

                        
/** Nodo de una lista simple enlazada de cadenas . */
public class Nodo {
private String elemento; // Los elementos son cadenas de caracteres
private Nodo sig;

/** Crea un nodo con el elemento dado y el nodo sig . */
public Nodo ( String s, Nodo n) {
elemento = s;
sig = n;
}


/** Lista simple enlazada . */
public class ListaSimple {
protected Nodo cabeza ; // nodo cabeza de la lista
protected long tam ; // cantidad de nodos en la lista

/** constructor por defecto que crea una lista vaca */
public ListaSimple () {
cabeza = null ;
tam = 0;
}

// ... métodos de actualización y búsqueda deberán ir aquí
}
                    
                

Links de apoyo