Яка складність доступу до елемента за індексом?

Складність доступу до елемента за індексом у зв'язаному списку - O(n) (лінійна).

У зв'язаному списку елементи не лежать поспіль у пам'яті, як у масиві. Кожен елемент (вузол) зберігає тільки:

свої дані,
посилання на наступний вузол (або ще й на попередній - у двозв'язному списку).

Тому, щоб дістатися до вузла з індексом i, програма має почати з head і пройти всі попередні вузли:

javascript

head → [0] → [1] → [2] → [3]
          ↑ потрібно пройти все до цього, щоб дістатися до [3]

Якщо список містить 1 000 елементів, і потрібно отримати елемент з індексом 900, алгоритм має пройти 900 кроків.

Операція	Складність
Доступ до першого елемента	O(1)
Доступ до останнього (через tail)	O(1) - якщо `tail` зберігається окремо
Доступ до елемента за індексом i	O(n)
Середня складність	O(n/2) ≈ O(n)

Структура	Доступ за індексом
Масив	O(1) - миттєво (адреса обчислюється)
Зв'язаний список	O(n) - потрібно пройти всі попередні вузли

Підсумок:

У зв'язаному списку доступ до елемента за індексом виконується за O(n), тому що потрібно пройти всі попередні вузли, починаючи з head.

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.