Какова наилучшая сложность времени bigO для перемещения и удаления элемента головки?

Question

Допустим, у меня есть структура данных, состоящая из трех элементов: {1,2,3}

, какая структура данных и какие временные сложности дадут мне наилучшие результаты, если я захочу выполнить только следующие операции?

-Перемещение последнего элемента на «переднюю часть» структуры данных -Снятие (сейчас) последнего элемента

Я нашел эту страницу: http://essays.hexapodia.net/datastructures/ и там написано двойноесвязанный список имеет O (1) для некоторых операций?

Однако мне нужно каждый раз сохранять порядок элементов, чтобы я мог сделать сдвиг.Если бы у меня было {1,2,3}, я бы захотел сдвинуться, получить 3,1,2, а затем удалить, оставив 3,1, а затем удалить, оставив 1

Если бы я использовал двойной связанный списокбыла бы моя сложность O (1) ???

Answer 1

Да, удаление и добавление элементов на обоих концах - это O (1) в двойном списке, который держит указатели на голову и хвост. Поскольку сдвиг может быть реализован с помощью этих двух операций, это тоже O (1).

В циклически связанном списке вы могли бы даже реализовать свою собственную операцию сдвига (по-прежнему O (1), но быстрее), выполнив

head = tail
if (tail != null) tail = tail.prev

Answer 2

По моему мнению, если вращение - единственная операция, которую вы хотите сделать, тогда используйте круговой массив (обычный массив, в котором голова может идти после хвоста)

С круговой вы сэкономите на 1. Удаление 2. Вставка

Все, что вам нужно сделать, это изменить указатель головы и хвоста.

Answer 3

Используйте deque , то есть O(1) для вставки или удаления на любом конце.

Answer 4

Большинство реализаций двусвязного списка имеют указатель на голову и хвост. Поскольку вы хотите сместить конец вперед, это тривиально O (1), потому что у вас есть указатели на эти места. Удаление их также тривиально O (1), потому что это просто вопрос установки указателя хвоста на предыдущую ссылку.

ОДНАКО, если у вас нет хвостового указателя и связанный список не является круглым, тогда удаление и сдвиг НЕ будут O (1). Обязательно проверьте реализацию.