Estrutura de dados: Insert-Delete-Contains-GetRandom

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);
}
}