Что такое List?

List: упорядоченная коллекция в Java

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

List расширяет интерфейс Collection и добавляет методы для работы с позициями элементов.

Основные характеристики List

1. Упорядоченность — элементы хранятся в определённом порядке
2. Индексирование — доступ по позиции (0, 1, 2, ...)
3. Дубликаты — можно хранить одинаковые элементы
4. Изменяемость — можно добавлять, удалять, обновлять элементы

Иерархия List

Collection
    |
    ├── List (интерфейс)
    |   ├── ArrayList (класс)
    |   ├── LinkedList (класс)
    |   ├── Vector (класс, legacy)
    |   ├── Stack (класс, legacy)
    |   └── CopyOnWriteArrayList (потокобезопасный)
    |
    ├── Set
    |   ├── HashSet
    |   ├── TreeSet
    |   └── LinkedHashSet
    |
    └── Queue
        ├── LinkedList
        ├── PriorityQueue
        └── ...

Основные методы List

List<String> list = new ArrayList<>();

// add(E) - добавить элемент в конец
list.add("Java");
list.add("Python");
list.add("C++");

// add(int, E) - добавить элемент на позицию
list.add(1, "Kotlin"); // [Java, Kotlin, Python, C++]

// get(int) - получить элемент по индексу
String first = list.get(0); // "Java"

// set(int, E) - заменить элемент на позиции
list.set(1, "Go"); // [Java, Go, Python, C++]

// remove(int) - удалить элемент по индексу
list.remove(1); // [Java, Python, C++]

// remove(Object) - удалить первый такой элемент
list.remove("Python"); // [Java, C++]

// size() - количество элементов
int size = list.size(); // 2

// isEmpty() - пуста ли список
boolean empty = list.isEmpty(); // false

// contains(Object) - есть ли элемент
boolean has = list.contains("Java"); // true

// indexOf(Object) - индекс первого вхождения
int index = list.indexOf("Java"); // 0

// subList(int, int) - подсписок
List<String> sub = list.subList(0, 1); // [Java]

// clear() - удалить все элементы
list.clear();

// toArray() - преобразовать в массив
String[] arr = list.toArray(new String[0]);

ArrayList: быстрый доступ по индексу

ArrayList — это реализация List на основе массива. Оптимален для частого чтения и редкого добавления в конец.

List<Integer> list = new ArrayList<>();

// Добавление элементов
for (int i = 0; i < 1000000; i++) {
    list.add(i);
}

// Быстрый доступ - O(1)
int element = list.get(500000); // Мгновенно

// Вставка в начало - O(n)
list.add(0, -1); // Медленно! Сдвигает все элементы

// Внутренняя структура - это обычный массив
// ┌─────┬─────┬─────┬─────┬─────┐
// │  0  │  1  │  2  │  3  │  4  │
// └─────┴─────┴─────┴─────┴─────┘

Характеристики ArrayList:

// Пример: обработка большого списка
public class ArrayListExample {
    public static void main(String[] args) {
        List<String> languages = new ArrayList<>();
        
        // Инициализация
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        languages.add("Kotlin");
        
        // Итерирование с индексом
        for (int i = 0; i < languages.size(); i++) {
            System.out.println(i + ": " + languages.get(i));
        }
        // Вывод:
        // 0: Java
        // 1: Python
        // 2: JavaScript
        // 3: Kotlin
        
        // Фильтрация
        List<String> filtered = languages.stream()
            .filter(lang -> lang.length() > 4)
            .collect(Collectors.toList());
        // filtered: [Python, JavaScript]
        
        // Сортировка
        Collections.sort(languages);
        System.out.println(languages);
        // [Java, JavaScript, Kotlin, Python]
    }
}

LinkedList: быстрое добавление в начало

LinkedList — это двусвязный список. Оптимален для частого добавления/удаления в начало или конец, но медленнее для случайного доступа.

List<String> list = new LinkedList<>();

// Добавление в конец - O(1)
list.add("A");
list.add("B");
list.add("C");

// Вставка в начало - O(1)
list.add(0, "Z"); // [Z, A, B, C] - очень быстро!

// Доступ по индексу - O(n)
String element = list.get(500000); // Медленно! Нужно пройти все элементы

// Внутренняя структура - двусвязный список
//  ┌──────────────────────────────────────────┐
//  │  Z  │  A  │  B  │  C  │
//  ├──┬──┼──┬──┼──┬──┼──┬──┤
//  │←→│ │←→│ │←→│ │←→│
//  └──┴──┴──┴──┴──┴──┴──┴──┘
//  Каждый элемент имеет ссылки на предыдущий и следующий

Характеристики LinkedList:

public class LinkedListExample {
    public static void main(String[] args) {
        List<Integer> queue = new LinkedList<>();
        
        // Добавление в конец
        queue.add(1);
        queue.add(2);
        queue.add(3);
        
        // Удаление с начала (O(1))
        int first = queue.remove(0); // 1
        
        // Использование как Queue
        queue.add(4);
        queue.add(5);
        
        while (!queue.isEmpty()) {
            System.out.println(queue.remove(0)); // FIFO
        }
        // Вывод: 2, 3, 4, 5
    }
}

Операции со списками

Создание списков

// Пустой список
List<String> list1 = new ArrayList<>();

// С начальной ёмкостью (оптимизация)
List<String> list2 = new ArrayList<>(10);

// Инициализация
List<String> list3 = Arrays.asList("A", "B", "C");

// Unmodifiable список (не может быть изменён)
List<String> list4 = List.of("A", "B", "C");

// Копия другого списка
List<String> list5 = new ArrayList<>(list1);

Сортировка

List<Integer> numbers = new ArrayList<>(Arrays.asList(3, 1, 4, 1, 5, 9));

// Сортировка в натуральном порядке
Collections.sort(numbers);
// [1, 1, 3, 4, 5, 9]

// Сортировка в обратном порядке
Collections.sort(numbers, Collections.reverseOrder());
// [9, 5, 4, 3, 1, 1]

// Сортировка с компаратором
List<String> names = new ArrayList<>(Arrays.asList("Bob", "Alice", "Charlie"));
Collections.sort(names, (a, b) -> a.compareTo(b));
// [Alice, Bob, Charlie]

// Сортировка по длине
Collections.sort(names, (a, b) -> Integer.compare(a.length(), b.length()));
// [Bob, Alice, Charlie]

Stream операции

List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

// Map: преобразование
List<Integer> squared = numbers.stream()
    .map(n -> n * n)
    .collect(Collectors.toList());
// [1, 4, 9, 16, 25]

// Filter: фильтрация
List<Integer> evens = numbers.stream()
    .filter(n -> n % 2 == 0)
    .collect(Collectors.toList());
// [2, 4]

// Reduce: агрегация
int sum = numbers.stream()
    .reduce(0, Integer::sum);
// 15

// forEach: итерирование
numbers.forEach(System.out::println);

Поиск в списке

List<String> fruits = new ArrayList<>(Arrays.asList(
    "Apple", "Banana", "Cherry", "Date"
));

// Линейный поиск
int index = fruits.indexOf("Cherry"); // 2

// Проверка наличия
boolean hasApple = fruits.contains("Apple"); // true

// Поиск с условием (Stream)
Optional<String> found = fruits.stream()
    .filter(f -> f.startsWith("B"))
    .findFirst();
// found: "Banana"

// Бинарный поиск (список должен быть отсортирован)
Collections.sort(fruits);
int binaryIndex = Collections.binarySearch(fruits, "Cherry");
// 1

Удаление элементов

List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 2, 4, 2, 5));

// Удаление по индексу
numbers.remove(0); // Удалить первый
// [2, 3, 2, 4, 2, 5]

// Удаление по значению (первое вхождение)
numbers.remove(Integer.valueOf(2)); // Удалить первую двойку
// [3, 2, 4, 2, 5]

// Удаление всех элементов, которые соответствуют условию
numbers.removeIf(n -> n == 2);
// [3, 4, 5]

// Удаление с итератором (безопасный способ)
Iterator<Integer> it = numbers.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) {
        it.remove();
    }
}
// [3, 5]

Thread-Safety и List

// Обычный ArrayList НЕ потокобезопасен
List<String> unsafeList = new ArrayList<>();

// Потокобезопасный вариант
List<String> syncedList = Collections.synchronizedList(new ArrayList<>());

// Или CopyOnWriteArrayList (для частого чтения)
List<String> safeList = new CopyOnWriteArrayList<>();

Сравнение ArrayList vs LinkedList

Выводы:

• Используй ArrayList если нужен частый доступ по индексу
• Используй LinkedList если нужно часто добавлять/удалять в начало
• В 90% случаев ArrayList быстрее благодаря локальности памяти

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