Listas

LISTAS
Una lista es una estructura de datos homogénea y dinámica, que va a estar formada por una secuencia de elementos, donde cada uno de ellos va seguido de otro o de ninguno.

En cuanto a su modo de acceso las listas se dividen en densas y enlazadas. El modo de acceso es independiente de la implementación realizada.

Las listas densas se caracterizan porque los elementos siguen unasecuencia física. El acceso a un elemento es por su orden o posición relativa dentro de la lista. Sabemos cuales es el siguiente elemento porque para acceder a él hemos tenido que pasar por todos los anteriores. La localización de un elemento cualquiera será:

-el primero si es el primer elemento de la lista.-N-esimo si para llegar a él hemos pasado por N-1 elementos.
Siguen una estructura física secuencial luego se pueden implementar utilizando ficheros, arreglos y punteros.

Las listas enlazadas son aquellas en las que cada elemento que los compone contiene la información necesaria para acceder al elemento siguiente. A un elemento se accede por la información contenida enun campo clave. La localización de un elemento cualquiera será: un elemento de la lista tendrá la dirección K si K es el primero y K es conocido (dirección de inicio).
Estará en la dirección J si J está contenida en el elemento anterior.

La mayor diferencia es que en la primera clase importa el orden de llegada, mientras que en la segunda depende de la clave.

LISTAS SIMPLES 

•Colección lineal de elementos llamados nodos.
• Existe un elemento llamado inicio que apunta al primer elemento de la lista.
• Cada nodo contiene un campo de enlace que apunta al siguiente elemento.
• El último elemento de la lista en su campo enlace apunta a nulo.
• Al principio el apuntador inicio apunta a nulo.
  
• Insertar: Agrega un elemento a la lista.
• Eliminar:Retira un elemento de la lista.
• Buscar: Busca un elemento en la lista.
• Recorrer: Visita todos los elementos de la lista.
• Vacía: Indica si la lista contiene o no elementos.
• Tamaño: Indica el número de elementos de la lista.
 Con las operaciones anteriores, define una interfase para una lista simple que contiene datos de tipo String. 
Operaciones con listas simples public interface ILista{
public void insertar(String elemento);
public boolean eliminar(String elemento);
public String eliminar();
public boolean buscar(String elemento);
public String recorrer();
public boolean vacía();
public int tamaño();
}  
 Implementación de la interfase ILista 
public boolean buscar(String elemento){
Nodo temporal = inicio;
while (temporal != null) {
if(elemento.equals(temporal.dato))
return true;
else
temporal= temporal.enlace;
}
return false;
}
public String recorrer(){ …. }
public void insertar(String elemento){
Nodo n = new Nodo(elemento);
// donde se inserta???
// al frente?
// al final?
// en el medio?
}
public boolean eliminar(String elemento){// elimina a un elemento especifico
}
public String eliminar(){ // elimina el primerelemento
String temporal = inicio.dato;
inicio = inicio.enlace;
return temporal;
}
} 
public class Lista implements ILista{
class Nodo{
     public String dato;
     public Nodo enlace;
     Nodo (String n){
     dato = n;
     enlace = null;
    }
}
Nodo inicio;
public Lista(){
inicio = null;
}
public boolean vacía(){
return (inicio == null);
}
public int tamaño(){
int n=0;Nodo temporal=inicio;
while (temporal != null) {
n++;
temporal = temporal.enlace;
}
return n;
}

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.
[pic]
Una lista enlazada simple contiene dos valores: el valor...