🤔 Базовые отличия между List и Linked List?

В Java List — это интерфейс, а его самые популярные реализации — ArrayList и LinkedList. Они имеют разную структуру данных, что влияет на производительность и область применения.

🚩Структура данных

ArrayList использует динамический массив, который хранит элементы в непрерывной области памяти.
LinkedList — это двусвязный список, где каждый элемент (Node) содержит ссылку на предыдущий и следующий элементы.

🚩Использование памяти

ArrayList требует непрерывного блока памяти, что может быть проблемой при нехватке места.
LinkedList требует дополнительной памяти на хранение ссылок (prev и next), что увеличивает общий размер.

Пример кода: разница в скорости вставки в середину списка

import java.util.*;

public class ListComparison {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>();
        List<Integer> linkedList = new LinkedList<>();

        int size = 100000;
        
        // Заполнение списков
        for (int i = 0; i < size; i++) {
            arrayList.add(i);
            linkedList.add(i);
        }

        // Вставка в середину
        long start = System.nanoTime();
        arrayList.add(size / 2, 999);
        long end = System.nanoTime();
        System.out.println("ArrayList вставка в середину: " + (end - start) + " нс");

        start = System.nanoTime();
        linkedList.add(size / 2, 999);
        end = System.nanoTime();
        System.out.println("LinkedList вставка в середину: " + (end - start) + " нс");
    }
}

Ставь 👍 и забирай 📚 Базу знаний