Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй? ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними. ArrayList: • доступ к произвольному элементу по индексу за константное время O(1); • доступ к элементам по значению за линейное время O(N); • вставка в конец в среднем производится за константное время O(1); • удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется); • вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку вправо; • минимум накладных расходов при хранении. LinkedList: • на получение элемента по индексу или значению потребуется линейное время O(N); • на добавление и удаление в начало или конец списка потребуется константное O(1); • вставка или удаление в/из произвольного место константное O(1); • требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка. В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список.