This will requires knowledge of Doubly Linked List In order to get O(N), you have to use 1.Doubly Linked list (for storing array elements ,cart) You can then perform deletion operation of specific index in O(1) 2. Use array/map to store the index(linked list Node) of first occurrence of element in DLL.

When query comes to delete element, look for Node to be deleted in array/map, go to the Node , delete it, (by linking previous to next node of to be deleted node) When query comes to append element, simply add Node to end;

You have to implement DLL with tail(general implementation says to maintain head) which means traversing DLL starting with tail, that way we you can append data at last (in O(1) rather than traversing whole list from head taking O(N)), you can add node after tail, and update the tail node.