но при этом читается за O(1), а в книге "Грокаем алгоритмы" написано, что чтение списков выполняется за O(n), в чём тогда вообще преимущество массива над ArrayList, если ArrayList имеет такое же время выполнения, но предоставляет ещё дополнительные методы для работы? Ниже оставил ссылку на статью с Хабра, откуда и прочитал про ArrayList и его время
https://habr.com/ru/articles/128269/
а вот загляни в реализацию ArrayList и поймешь, почему он за О(1) обращается к элементам. в книге же скорее всего рассматривался односвязный список, типа LinkedList, поэтому сложность другая
на картинке, кстати, вставка в список за константное время только для головы или хвоста гарантируется, потому что если надо вставить элемент в середину, то будет н пополам, а это уже, как не крути, линейное время
на картинке про линкедлист
у тебя итератор может уже стоять на нужном месте.
Хорошо, что он бесплатно туда встаёт
Обсуждают сегодня