# 85ms solution from Insert Delete GetRandom O(1) - Duplicates not allowed

• the main idea of `Insert Delete GetRandom O(1) - Duplicates not allowed` is to keep the vector continuous，using the hashmap to keep the position of value. when it comes to `Insert Delete GetRandom O(1) - Duplicates allowed`，use the hashmap to keep the position of link list's head，when remove the value，update the hashmap and vector to keep vector continuous.

``````struct Node {
int val;
int next;

Node() : val(0), next(-1) {};

Node(int v, int n) : val(v), next(n) {};

};

class RandomizedCollection {
public:
vector<Node> vec;

/** Initialize your data structure here. */
RandomizedCollection() {
srand(time(nullptr));
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
Node t(val, -1);
if (!ret) t.next = linkb[val];
vec.push_back(t);
return ret;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
int pos = linkb[val];
if (vec[pos].next == -1) linkb.erase(val);
else linkb[val] = vec[pos].next;

int p = vec.size() - 1;
if(p==pos) {
vec.pop_back();
return true;
}
while (vec[p].next != -1 && vec[p].next > pos)
p = vec[p].next;
vec[pos].val = vec.back().val;
vec[pos].next = vec[p].next;
vec[p].next = pos;