С точки зрения времени выполнения big-O, кажется, что обе структуры данных имеют в «среднем» случае:
O(1) вставка / удаление в начале и конце O(n) вставка / удаление в некоторый произвольный индекс O(1) поиск начала и конца
Преимущества кольцевого буфера:
O(1) поиск вместо O(n) некоторого произвольного индекса - Не требуется создавать узлы, поэтому не требуется динамическое распределение при каждой вставке
- Более быстрый обход благодаря лучшему прогнозированию кэша
- Более быстрое удаление из-за векторизации (например, использование
memmove) для заполнения пробела - Как правило, требуется меньше места (поскольку в связанном списке для каждого узла необходимо отсортировать указатели наследующий и / или предыдущий узел)
Преимущества связанного списка:
- Легче получить
O(1) вставку / удаление в определенное место (например, может получить его дляна полпути через связанный список).Циклические буферы могут делать это, но в худшем случае это сложнее O(1), в отличие от циклических буферов, которые O(n) (когда нужно увеличить буфер)
Исходя из этого списка, мне кажется, что циклические буферы - гораздо лучший выбор почти в каждом случае.Я что-то упустил?