Estrutura de dados simples, mas útil, escrita em Java. Fornece Insert, Delete, Contains e GetRandom em O (1).
Ele pode ser facilmente estendido para fornecer Get (int index), Pop (), Push (), etc., se necessário.
O importante é que os objetos estão sendo armazenados apenas na lista, enquanto o HashMap simplesmente mapeia o objeto para seu índice na lista.
import java.util.HashMap;
import java.util.ArrayList;
import java.util.Random;
/**
* A Data Structure that implements Insert, Contains, Delete, and GetRandom in O(1)
*
* @author dkirby
*
*/
public class Insert_Contains_Delete_GetRandom
{
private HashMap<Object, Integer> _hash;
private ArrayList<Object> _list;
public Insert_Contains_Delete_GetRandom()
{
_hash = new HashMap<>();
_list = new ArrayList<>();
}
public void insert(Object object)
{
int index = _list.size();
_hash.put(object, index);
_list.add(object);
}
public boolean contains(Object object)
{
return _hash.containsKey(object);
}
public void delete(Object object)
{
if (_hash.containsKey(object))
{
// get the index of the specified object in the list
int index = _hash.get(object);
// get the index of the last element in the list
int end = _list.size() - 1;
// get the element at the 'end' position
Object o = _list.get(end);
// copy the 'end' element into position 'index'
_list.set(index, o);
// drop the last element from the list
_list.remove(end);
// update the hash of the object that was moved
_hash.put(o, index);
// remove the specified object from the hash
_hash.remove(object);
}
}
public Object getRandom()
{
Random rand = new Random();
int index = rand.nextInt(_list.size());
return _list.get(index);
}
}