🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
🤔 Вставка значения быстрее в 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) // Медленная вставка в середину
Ставь 👍 и забирай 📚 Базу знаний