Охарактеризуй LinkedList

LinkedList: характеристики и применение

LinkedList — это двусвязный список (doubly-linked list) в Java. Это базовая структура данных, которую должен понимать каждый разработчик.

Структура LinkedList

Каждый элемент (Node) содержит:

• value: сами данные
• next: ссылка на следующий элемент
• prev: ссылка на предыдущий элемент (двусвязность)

[null] ← [prev] ↔ [Node1] ↔ [Node2] ↔ [Node3] ↔ [next] → [null]
         |value|    |value|    |value|

Основные операции и их сложность

Когда использовать LinkedList

Используй LinkedList если:

1. Частые вставки/удаления в начало или конец:

LinkedList<String> queue = new LinkedList<>();
queue.addFirst("Priority task");  // O(1)
queue.addLast("Normal task");     // O(1)

String urgent = queue.removeFirst(); // O(1)

1. Реализация Queue или Deque:

Queue<Integer> queue = new LinkedList<>();
queue.add(1);      // enqueue
queue.poll();      // dequeue - O(1) операции

Deque<String> deque = new LinkedList<>();
deque.addFirst("a");  // O(1)
deque.addLast("b");   // O(1)

1. Реализация Stack:

Stack<String> stack = new LinkedList<>(); // Хотя обычно используют Stack класс
stack.push("item");     // O(1)
stack.pop();            // O(1)

Когда НЕ использовать LinkedList

❌ Избегай LinkedList если нужен случайный доступ:

// ❌ Ужасно!
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < 10000; i++) {
    list.add(i);
}

for (int i = 0; i < list.size(); i++) {
    int value = list.get(i); // O(n) для каждого элемента!
    // Итого: O(n²) сложность!
}

// ✅ Правильно
for (Integer value : list) { // Iterator - O(1)
    // Работаем с value
}

LinkedList vs ArrayList

List<String> arrayList = new ArrayList<>();
List<String> linkedList = new LinkedList<>();

// Добавление в конец
arrow arrayList.add("item");    // O(1) amortized
arrow linkedList.add("item");   // O(1) ✓

// Доступ по индексу
String s = arrayList.get(500);  // O(1) ✓
String s = linkedList.get(500); // O(n) ✗

// Вставка в начало
arrow arrayList.add(0, "first"); // O(n) - сдвиг всех элементов
arrow linkedList.addFirst("first"); // O(1) ✓

// Итератор
arrow arrayList.iterator();  // O(1) доступ
arrow linkedList.iterator(); // O(1) доступ

Практические примеры

Пример 1: Реализация очереди задач

public class TaskQueue {
    private final Queue<Task> tasks = new LinkedList<>();
    
    public void addTask(Task task) {
        tasks.add(task); // O(1)
    }
    
    public Task getNextTask() {
        return tasks.poll(); // O(1)
    }
}

Пример 2: Реверс строки

public String reverseString(String s) {
    Deque<Character> deque = new LinkedList<>();
    for (char c : s.toCharArray()) {
        deque.addFirst(c); // O(1)
    }
    
    StringBuilder result = new StringBuilder();
    for (char c : deque) {
        result.append(c);
    }
    return result.toString();
}

Особенности в Java

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

// Методы, которые есть только в LinkedList:
list.addFirst("Start");    // добавить в начало
list.addLast("End");       // добавить в конец
list.removeFirst();        // удалить первый
list.removeLast();         // удалить последний
list.getFirst();           // получить первый
list.getLast();            // получить последний

// Работает как Queue
list.offer("item");        // добавить
list.poll();               // получить и удалить
list.peek();               // получить без удаления

Память и производительность

• Память: O(n) элементов + extra память на prev/next указатели (на 16 байт больше на элемент, чем ArrayList)
• Cache locality: Плохая! Элементы разбросаны по памяти, что замедляет работу на современных CPU
• GC: Более сложная для сборки мусора из-за множества объектов

Вывод: LinkedList полезен для очередей и стеков (O(1) операции на концах), но для обычных коллекций лучше используй ArrayList. LinkedList часто переоценивают в практических применениях.