O(1) Data Structure Using Double Linked List

Problem Create a data structure whose supported operations each run in O(1) time. Use a doubly linked list as part of the implementation. The structure must provide these operations: insert(val): Add an element containing val in O(1) time. remove(val): Delete an element containing val in O(1) time. If no such element is present, leave the structure unchanged. getRandom(): Return one element chosen uniformly from the elements currently stored, in O(1) time. Examples Example 1…