Kotlin | Вопросы собесов

🤔 Вставка значения быстрее в Linked list или в Array list? 🚩Вставка в `ArrayList` ArrayList реализован на основе массива. 🟠Вставка в конец Амортизированное O(1). Если массив не заполнен, элемент добавляется в конец списка. В случае, если массив заполнен, требуется выделение нового массива и копирование элементов, что занимает O(n) времени. val arrayList = ArrayList() arrayList.add(1) // Быстрая вставка в конец 🟠Вставка в начало или середину O(n). Необходимо сдвинуть все элементы, начиная с позиции вставки, чтобы освободить место для нового элемента. Это требует времени, пропорционального количеству элементов после позиции вставки. arrayList.add(0, 2) // Медленная вставка в начало arrayList.add(1, 3) // Медленная вставка в середину 🚩Вставка в LinkedList LinkedList реализован на основе узлов, где каждый узел содержит ссылку на следующий и/или предыдущий узел (в случае двусвязного списка). 🟠Вставка в начало: O(1). Для добавления элемента в начало достаточно изменить ссылки первого узла и нового узла. val linkedList = LinkedList() linkedList.addFirst(1) // Быстрая вставка в начало 🟠Вставка в конец O(1) (если есть ссылка на последний узел) или O(n) (если необходимо пройти весь список). Если список двусвязный и хранится ссылка на последний элемент, вставка в конец осуществляется за O(1). В противном случае, требуется пройти весь список до конца. linkedList.addLast(2) // Быстрая вставка в конец, если есть ссылка на последний узел 🟠Вставка в середину O(n). Необходимо пройти список до нужной позиции и изменить ссылки узлов. linkedList.add(1, 3) // Медленная вставка в середину Ставь 👍 и забирай 📚 Базу знаний