Какая асимптотика обращения по индексу в list?

Асимптотика обращения по индексу в std::list

std::list — это двусвязный список в C++, и скорость доступа к элементам существенно отличается от массива. Это ключевое отличие, которое влияет на выбор структуры данных при разработке.

Основная характеристика: O(n)

Доступ к элементу по индексу в std::list: O(n)

std::list не поддерживает произвольный доступ, как массив. Для доступа к элементу с индексом i нужно пройти по i узлам в списке:

std::list<int> mylist = {10, 20, 30, 40, 50};

// Доступ: O(n)
int val = mylist[0];        // O(n) - требует поиска
auto it = mylist.begin();   // O(1) - итератор на начало
std::advance(it, 0);        // O(n) - движение по списку на n позиций

Визуально процесс доступа к 3-му элементу:

Список: [10] <-> [20] <-> [30] <-> [40] <-> [50]
         ^
         |
  Начинаем здесь
  
  Шаг 1: перейти к 20 (индекс 1)
  Шаг 2: перейти к 30 (индекс 2)
  Шаг 3: перейти к 40 (индекс 3)  <- вот это элемент
  
  Всего 3 операции перехода = O(3) = O(n)

Почему O(n), а не O(1)?

Структура памяти

std::list — это двусвязный список, где каждый узел содержит:

template<typename T>
struct Node {
    T data;
    Node* next;
    Node* prev;
};

// Визуально:
// ┌─────────┐     ┌─────────┐     ┌─────────┐
// │ data:10 │     │ data:20 │     │ data:30 │
// │ next  ──┼────>│ next  ──┼────>│ next  ──┼──> nullptr
// │ prev  ──┼─────┼─ prev ──┼─────┼─ prev ──┤
// └─────────┘     └─────────┘     └─────────┘
//     ^
//     |
//   begin()

Узлы разбросаны по памяти, нет прямого математического пути к элементу. Единственный способ добраться до элемента — пройти последовательно.

Сравнение с vector

*Если уже есть итератор на позицию

Примеры и детали

Примерное время для разных размеров

std::list<int> mylist;
for (int i = 0; i < 1000; i++) {
    mylist.push_back(i);
}

// Доступ к элементу 500
int val = mylist[500];  // ~500 операций перехода между узлами

// Доступ к элементу 999
auto it = std::next(mylist.begin(), 999);  // ~999 операций

Для N элементов в списке доступ к позиции n требует примерно n операций:

• К элементу 0: 0 шагов O(0)
• К элементу 10: 10 шагов O(10)
• К элементу N-1: N-1 шагов O(N-1)
• В среднем: N/2 шагов = O(N)

Оптимизация: использование итераторов

std::list<int> mylist;
for (int i = 0; i < 1000; i++) {
    mylist.push_back(i);
}

// Медленно: O(n) для каждого доступа
for (int i = 0; i < mylist.size(); i++) {
    auto it = std::next(mylist.begin(), i);  // O(i) для каждого i
    std::cout << *it;                        // O(n^2) всего!
}

// Быстро: O(n) всего
for (auto it = mylist.begin(); it != mylist.end(); ++it) {
    std::cout << *it;  // O(1) для каждого доступа
}

Практические последствия

Почему не использовать std::list[i]?

std::list<int> data(10000);

// Худший вариант: O(n^2)
for (int i = 0; i < data.size(); i++) {
    std::cout << data[i];  // Каждый раз O(n) поиск
}
// Всего: 0 + 1 + 2 + ... + n = O(n^2)

// Хороший вариант: O(n)
for (auto val : data) {
    std::cout << val;  // Один проход
}

Пример из реальной практики

std::list<Task> task_queue;

// НЕПРАВИЛЬНО - O(n) на каждый процесс
while (!task_queue.empty()) {
    Task t = task_queue[0];      // O(n) доступ
    process(t);
    // ...
}

// ПРАВИЛЬНО - O(1) на каждый процесс
while (!task_queue.empty()) {
    Task t = task_queue.front();  // O(1)
    process(t);
    task_queue.pop_front();        // O(1)
}

Когда использовать std::list

Используй std::list когда:

• Частые вставки/удаления в начало или в известную позицию
• Не нужен случайный доступ по индексу
• Нужна стабильность итераторов при вставке/удалении

НЕ используй std::list когда:

• Нужен частый доступ по индексу
• Нужна хорошая кэш-локальность
• Мало вставок/удаления в начало
• Нужна инсправим производительность

Рекомендация

Для большинства backend-приложений используй std::vector:

• O(1) доступ по индексу
• O(1) вставка в конец
• Хорошая работа с кэшем
• Меньше памяти на элемент (нет указателей)

std::list используй только если на 100% уверен, что нужны O(1) вставки/удаления в середину и готов потерять произвольный доступ.