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