Структура данных, которая поддерживает постоянное время для добавления, добавления и произвольного доступа

Question

Я ищу структуру данных, которая поддерживает постоянную производительность по времени для добавления элемента в начало, конец и произвольный доступ.

Я думаю, двусторонняя очередь.Поддерживает ли двусторонняя очередь постоянную производительность по времени для произвольного доступа?Если да, то как это достигается?

Я знаю, что можно использовать двойной связанный список для создания двусторонней очереди.Но как построить индекс по всем элементам для обеспечения произвольного доступа с постоянным временем?

Спасибо за вашу помощь.

Джерри

Answer 1

То, что вы ищете - это двусторонняя очередь по определению, но это просто абстрактная структура данных. Википедия обсуждает несколько стратегий реализации для запросов в терминах динамических массивов; используя их, вы можете получить амортизированные O (1) prepend и append. На первый взгляд стратегия циклического буфера кажется наиболее простой для реализации.