What is the best data structure for removing an element from the middle?

Question

The data stucture must be like a stack. Only with one difference. I want to pop from any index not only last. When I have popped element n, the elements with indexes N > n must swap to N-1. Any ideas?

P.S.

1. Pushing element n into the last index of the stack.
2. Then popping it out.
3. Then deleting stack[n]

is a bad idea.

Answer 1

A linked list (std::list) will allow you to remove an element from the middle with O(1) complexity and automatically "pull" up the elements after it. You can use a linked list like a stack by using push_front. However you need to be aware that accessing an element in a linked list is O(n) as you would need to start at the head of the list and then walk along the links from one element to the next until you have arrived at element n (so there is no O(1) indexing)

Basically you would need to

• Create an iterator
• advance it to position n
• Get the element from the iterator
• erase the element the iterator is currently pointing to

Some example code can be found here.

Answer 2

You need to implement a linked list, but unlike an array, the order in a linked list is determined by a pointer in each object. So, you cannot use indices to access the elements.

Answer 3

I think you're looking for a linked list.