Middle
Wie verhalten sich eine verkettete Liste (LinkedList) und eine ArrayList, wenn ein Element eingefügt wird?
sobes.tech KI
Antwort von AI
Вставка элемента в LinkedList требует обхода списка до нужной позиции, что занимает O(n) в худшем случае. Сама вставка элемента - O(1), так как нужно обновить всего два указателя (текущего и предыдущего элемента).
Вставка элемента в ArrayList в середину требует сдвига всех последующих элементов на одну позицию вправо, что занимает O(n). Вставка в конец списка блиска к O(1) в среднем случае, если есть свободное место. Если массив заполнен, происходит его пересоздание и копирование элементов (аммортизированно O(1)).
| Операция | LinkedList | ArrayList |
|---|---|---|
| Вставка в начало | O(1) | O(n) |
| Вставка в середину | O(n) | O(n) |
| Вставка в конец | O(1) | O(1) (аммортизированно) |