Здравствуйте, netch80, Вы писали:

N>Ну так каждая из этих операций имеет ценой длину списка (равной длине массива).
N>3*O(N) тоже O(N).
Формально так, только O более чем в 3 раза дороже в данном случае. Это же не просто взять значение из соседней ячейки, а сначала получить адрес ноды и уже потом ее значение.