Какова лучшая структура данных для удаления элемента из середины?

Question

Структура данных должна быть подобна стеку.Только с одним отличием.Я хочу выскочить из любого индекса не только последний.Когда я вытолкнул элемент n, элементы с индексами N > n должны поменяться на N-1.Есть идеи?

PS

1. Вставка элемента n в последний индекс стека.
2. Тогда выкинуть.
3. Тогда удаление stack[n]

- плохая идея.

Answer 1

Я думаю, что вы ищете связанный список.

Answer 2

Связанный список (std::list) позволит вам удалить элемент из середины со сложностью O(1) и автоматически «вытянуть» элементы после него. Вы можете использовать связанный список как стек, используя push_front. Однако вы должны знать, что доступ к элементу в связанном списке - это O(n), так как вам нужно начать с начала списка, а затем идти по ссылкам от одного элемента к следующему, пока вы не достигнете элемента n (так что нет O(1) индексации)

В основном вам нужно будет

• Создать итератор
• advance в позицию n
• Получить элемент из итератора
• erase элемент, на который в данный момент указывает итератор

Некоторые примеры кода можно найти здесь .

Answer 3

Вам необходимо реализовать связанный список, но в отличие от массива, порядок в связанном списке определяется указателем в каждом объекте.Таким образом, вы не можете использовать индексы для доступа к элементам.