Estructuras de datos concurrentes

1. Implementa una lista concurrente. Ten los siguientes detalles en cuenta:
   • Queremos que varios hilos pueden insertar o borrar al mismo tiempo (claro, en diferentes sitios de la lista).
   • Desarrolla una semántica adecuado para una lista concurrente, entre otras, te debes contestar las siguientes preguntas:
     • ¿Debo mantener la longitud actual de la lista?
     • ¿Qué tipo de inserción uso como base para los demás?
     • ¿En qué orden adquiero los cerrojos necesarios?
     • ¿Cómo trato intentos concurrentes de borrar el mismo elemento al mismo tiempo?
     • ¿Qué hacen los iteradores?
     • ¿Cómo deben interactuar iteradores con los demás operaciones?
     • ¿Cómo implemento un caso de prueba?
2. Ayudas:
   • Busca en la red: Doug Lea (que ha hecho disponible una sugerencia para una librería de Java: java.lang.concurrent)
   • Mira como se ha implementado la cola.
   • Mira la solución del año pasado, cuando ya has pensado cierto tiempo sobre una solución propia.
3. Realiza la implementación usando las nuevas primitivas propuestas por la JSR166, es decir, implementa la lista con Java 1.5.
4. Aumenta la lista concurrente introduciendo también las operaciones con colecciones.

Tarea adicional para los interesados:

1. implementa una clase de lista concurrente en C++ con hilos POSIX o con hilos de la librería glib.
2. implementa una clase de lista concurrente en C# con hilos.

Para los que no quieren parar:

1. Implementa una tabla de dispersión concurrente (hashtable) aprovechando de la lista concurrente.
2. Implementa una tabla de dispersión concurrente (hashtable) con el método de Cuckoo Hashing.
3. Implementa un grafo concurrente (graph), a algunas de operaciones interesantes sobre dicha estructura de datos.
4. Implementa una estructura de datos que te resulta útil para desarrollar programas concurrentes.