Comparacion de Listas Enlazadas, Hasmap

Mientras que estudio para un parcial dejare esto por aca, la finalidad del post es ver las cualidades de las siguientes estructuras y juzgar cual es la mejor y cual puede servir segun lo que se quiera programar.

Listas:Se puede acceder(insertar, eliminar) por cualquier parte
Pilas: Solo tiene un unimito punto de acceso y atraves de este se pueden añadir o eliminar elementos.
Colas: Solo tiene dos puntos de acceso, uno para consultar y otro pasa eliminar.

Listas:

Lista Enlazada Simple

Consideraciones que tiene una lista:

Las listar pueden ser implementadas tanto con arrays como con puntoros, pero que pasa con los array se tiene que asignar un tamaño estatico lo cual es ineficiente.
Cuando se crea un lista el nodo cabecera tendra un dato null y un puntero null, que es lo que iria en el contrstructor.
Los nodos de una lista pueden que no ocupen posiciones continuas en memoria
Una lista se considera que esta llena cuando ya no queda espacio en memoria para crear un nodo
Cuando se va a insertar una lista se debe verificar que la lina no este vacia.
El apuntador asl inicio de la lista es el que nos va a indicar el siguiente elemento si por alguna razon se pierde este apuntador se perdera toda la informacion que tenemos en la lista

Busquedas.
Para realizar la busqueda de una dato en una lista es necesario que este ordenada.

Se pueden implementar dos algoritmos de forma recursiva para la busqueda de informacion, uno de forma ascendente y otra de forma desordenada.

Algoritmo de Busqueda en listas enlazadas

Codigo de una Lista Simple

public class Listaa {

 private Object dato;
 private Listaa sig;

 // Constructores
 public Listaa() { // Crear una lista vacia
  dato = null;
  sig = null;
 }

 

 public Listaa(Listaa otra) { // crea una lista a partir de otra
  dato = otra.dato;
  sig = otra.sig;
 }

 public boolean vacia() { //verifica si los datos actuales estan vacios
  return sig == null && dato == null;
 }

 public void insertarInicio(Object x) {
  sig = new Listaa(this); //Se crea una lista apartir de la ya esta actualmente, y se cambia el apuntador
  dato = x;
 }

 public void insertar(Object x, int k) { // insertar un dato en la k-esima
           // posicion de la lista
  if(vacia() || k == 0){
   insertarInicio(x);
  }else{
   sig.insertar(x, k - 1);//Se hace "recursion"(saltos) para llegar a la posision que me dieron
  }
 }

 public void insertarFinal(Object x) {
  if (vacia()) { //
   dato = x;
   sig = new Listaa(); //Se crea el siguiente nodo en null
  }else {
   sig.insertarFinal(x); //Hacer "recursion hasta llega al ultimo nodo que es null"
  }
 }

 public Object eliminar(Object x) { //Elimina el dato que se le ingrese y retorna el objeto eleminado
  Object res = null;
  if (!vacia()) {
   if (dato.equals(x)) {//COmpara los objectos
    res = dato;
    dato = sig.dato;
    sig = sig.sig;//el siguiente sera el siguiente de mi siguiente
   } else {
    res = sig.eliminar(x); //hace "recursion" para recorrese toda la lista
   }
  }
  return res;
 }

 public int tamano() {
  if (vacia())
   return 0;
  return 1 + sig.tamano(); //Hacer "Recursion" para el conteo de nodos
 }

 public boolean buscar(Object x) {
  if (vacia()){
   return false;
  }
  if (dato.equals(x))
   return true;
  return sig.buscar(x);//hacer "recursion" hasta recorrerse toda la lista

 }

 public Object obtener(int pos) {
  if (vacia())
   return null;
  if (pos == 0)
   return dato; //Cuando llega aca ya no hace el siguiente return

  return sig.obtener(pos - 1);
 }

 public String toStringg() {
  String res = "[" + resto() + "]";
  return res;
 }

 private String resto() {
  String res = "";
  if (!vacia()) {
   res = dato.toString(); //NO hace recursion convierte el Objeto A string
   if (!sig.vacia())
    res = res + ", " + sig.resto(); //hacer "Recusion" hasta añadir todos los elementos"
  }
  return res;
 }

 public Object eliminar(int pos) {
  if (vacia())
   return null;
  if (pos == 0) {
   Object res = dato;
   dato = sig.dato;
   sig = sig.sig;
   return res;
  } else {
   return sig.eliminar(pos - 1);
  }
 }

 public void modificar(int pos, Object x) {
  if (vacia() || pos < 0)
   return;
  if (pos == 0) {
   dato = x;
  } else {
   sig.modificar(pos - 1, x);
  }
 }
}

Lista enlazada donble:

El nodo tiene 3 campos, uno es el punto del nodo anterior, el dato y el puntero del siguiente nodo

Lista enlazada circular simple:

Las operaciones de busqueda son mas eficientes
Se dice que se llego al final de la lista cuando se encuentra con el nodo de partida

Codigo de lista Circula Simple

package ListaCircularSimple;
public class ListaC {
 private Nodo inicio;
 private Nodo fin;
 
 public ListaC(){
  inicio = fin = null;
 }
 public boolean vacia(){
  return inicio == null && fin == null;
 }
 
 //Insertar al INicio
 public void insertarAlInicio(Object dato){
  Nodo nuevo = new Nodo(null,dato); 
  if(vacia()){
   this.fin=nuevo;
  }else{
   nuevo.setSiguiente(this.inicio);
  }
  this.inicio=nuevo;
  this.fin.setSiguiente(this.inicio); //enlazo el ultimo con el primero
  
 }
 public void insertarAlFin(Object dato){
  Nodo nuevo = new Nodo(null,dato);
  if(vacia()){
   inicio = nuevo;
  }else{
   fin.setSiguiente(nuevo);
  }
  this.fin = nuevo;
  this.fin.setSiguiente(this.inicio); //enlazo el ultimo con el primero
 }
 public String toStringg(){
  if(vacia()){
   return "";
  }
  String res = inicio.getData() + " ";
  for(Nodo x = inicio.getSiguiente(); x != this.inicio;x = x.getSiguiente()){
   res = res + x.getData() +" ";
   
  }
  return res;
 }

}

Lista enlazada circular Doble

En este tipo de listas el primer nodo el anterior apunta al ultimo nodo y el ultimo el siguiente al primero

package ListaCircularDoble;

public class ListaCDoble {
 private Nodo inicio;
 private Nodo fin;
 
 public ListaCDoble(){
  inicio = fin = null;
 }
 public boolean vacia(){
  return inicio == null && fin == null;
 }
 
 //Insertar al INicio
 public void insertarAlInicio(Object dato){
  Nodo nuevo = new Nodo(dato); 
  if(vacia()){
   this.fin=nuevo;
  }else{
   this.inicio.setAnterior(nuevo);
   nuevo.setSiguiente(this.inicio);
   
  }
  
  this.inicio=nuevo;
  this.fin.setSiguiente(this.inicio); //enlazo el ultimo con el primero
  this.inicio.setAnterior(this.fin);
  
  
 }
 public void insertarAlFin(Object dato){
  Nodo nuevo = new Nodo(dato);
  if(vacia()){
   inicio = nuevo;
  }else{
   fin.setSiguiente(nuevo);
   nuevo.setAnterior(this.fin);   
  }
  
  this.fin = nuevo;
  this.fin.setSiguiente(this.inicio);
  this.inicio.setAnterior(this.fin);

  
 }
 public void eliminarDato(Object dato){
  if(!vacia()){
   
   if(dato.equals(this.inicio.getData())){
    this.inicio=this.inicio.getSiguiente();
    this.fin.setSiguiente(this.inicio);
    this.inicio.setAnterior(this.fin);
    
   }else{
    for(Nodo x = inicio.getSiguiente(); x != this.inicio;x = x.getSiguiente()){
     if(dato.equals(x.getData())){
      x.getAnterior().setSiguiente(x.getSiguiente());
      x.getSiguiente().setAnterior(x.getAnterior());
     }
     
     
    }
   }
   
  }
 }
 public String toStringg(){
  if(vacia()){
   return "";
  }
  String res = inicio.getData() + " ";
 
  for(Nodo x = inicio.getSiguiente(); x != this.inicio;x = x.getSiguiente()){
   res = res + x.getData() +" ";
   
  }
  return res;
 }

}

ArrayList

Utiliza un Array para almacenar los datos
Permite elementos duplicados
No es un estructura sincronizada
Se puede acceder de manera aleatoria
Puede contener valores nulos

LikedList

Utiliza una lista enlazada para almacenar los datos
Puede contener valores duplicados
Mantiene el orden de isersion de los elementos.
No es sincronizada
No permite el acceso aleatorio
Puede contener valores nulos
Pueder ser utiliza como una lista, pila o cola

HashSet

Utiliza HasTable para almacenar los elemento
No permite duplicados
Puede contener valores nulos
No tiene un orden al ingresar el usuario

LikedHashSet

Contiene valores Unicos
Puede almacenar valores nulos
Mantiene el Orden a ingresar los datos

HasMap

Con el hashMap es posible realizar busquedas por valor.

No permite valores duplicado
Puede tener una clave con valor null y multiples valores null
No mantiene orden de insersion

Map

Es una interfaz que permite asignar a un objecto clave un valor u objecto.

Los mapas no pueden terner claves repetidos, ya que funcionana como identificador unico