import java.util.LinkedList;
import java.util.List;

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

        // Добавление элементов
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        // Получение элемента
        System.out.println("First element: " + linkedList.get(0)); // Apple

        // Вставка элемента
        linkedList.add(1, "Orange");
        System.out.println("After insertion: " + linkedList); // [Apple, Orange, Banana, Cherry]

        // Удаление элемента
        linkedList.remove("Banana");
        System.out.println("After removal: " + linkedList); // [Apple, Orange, Cherry]

        // Итерация по элементам
        for (String fruit : linkedList) {
            System.out.println(fruit);
        }
    }
}

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

transient Node<E> first;
transient Node<E> last;

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

linkedList.add("Apple");
linkedList.add(1, "Orange");

linkedList.remove(1);
linkedList.remove("Apple");

String first = linkedList.getFirst();
String element = linkedList.get(1);

int size = linkedList.size();
linkedList.clear();
boolean containsApple = linkedList.contains("Apple");

javaimport java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("Задача 1");  // Добавление в конец
        queue.offer("Задача 2");
        queue.offer("Задача 3");
        System.out.println(queue);  // [Задача 1, Задача 2, Задача 3] — FIFO порядок

        System.out.println(queue.peek());  // Задача 1 (просмотр)
        System.out.println(queue.poll());  // Задача 1 (извлечение)
        System.out.println(queue);         // [Задача 2, Задача 3]

        queue.offer(null);  // Разрешен null
        System.out.println(queue.poll());  // Задача 2
    }
}

Вывод: Показывает FIFO — элементы извлекаются в порядке добавления, null разрешен.

javaimport java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(3);
        queue.offer(1);
        queue.offer(2);
        System.out.println(queue);  // [1, 3, 2] — min в начале, но итерация не sorted

        System.out.println(queue.peek());  // 1 (минимальный)
        System.out.println(queue.poll());  // 1
        System.out.println(queue);         // [2, 3]

        // Max-heap с Comparator
        Queue<Integer> maxQueue = new PriorityQueue<>((a, b) -> b - a);
        maxQueue.offer(3);
        maxQueue.offer(1);
        maxQueue.offer(2);
        System.out.println(maxQueue.poll());  // 3 (максимальный)

        // queue.offer(null);  // NPE
    }
}

Вывод: Элементы извлекаются по приоритету, не по порядку добавления.

javaimport java.util.LinkedList;
import java.util.Queue;

public class TaskProcessor {
    private Queue<String> tasks = new LinkedList<>();

    public void addTask(String task) {
        tasks.offer(task);
    }

    public void processTasks() {
        while (!tasks.isEmpty()) {
            String task = tasks.poll();
            System.out.println("Обработка: " + task);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        TaskProcessor processor = new TaskProcessor();
        processor.addTask("Задача 1");
        processor.addTask("Задача 2");
        processor.processTasks();  // Обработка: Задача 1\nОбработка: Задача 2
    }
}

Вывод: Задачи обрабатываются FIFO.

javaimport java.util.PriorityQueue;
import java.util.Queue;

class Request implements Comparable<Request> {
    private String name;
    private int priority;  // 1 - высокий, 10 - низкий

    public Request(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    @Override
    public int compareTo(Request other) {
        return Integer.compare(this.priority, other.priority);  // Min-heap по приоритету
    }

    public String getName() {
        return name;
    }
}

public class Main {
    public static void main(String[] args) {
        Queue<Request> requests = new PriorityQueue<>();
        requests.offer(new Request("Заявка A", 5));
        requests.offer(new Request("Заявка B", 1));  // Высокий приоритет
        requests.offer(new Request("Заявка C", 3));

        while (!requests.isEmpty()) {
            System.out.println("Обработка: " + requests.poll().getName());  // Заявка B, Заявка C, Заявка A
        }
    }
}

Вывод: Заявки обрабатываются по приоритету.

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        // FIFO: Очередь
        deque.offerLast("Элемент 1");  // Добавление в конец
        deque.offerLast("Элемент 2");
        System.out.println(deque.pollFirst());  // Элемент 1 (извлечение из начала)
        System.out.println(deque.peekFirst());  // Элемент 2 (просмотр)

        // LIFO: Стек
        deque.offerFirst("Элемент 3");  // Добавление в начало
        deque.offerFirst("Элемент 4");
        System.out.println(deque.pollFirst());  // Элемент 4 (LIFO)

        // Обратный итератор
        for (String elem : deque.descendingIterator()) {
            System.out.println(elem);  // С конца к началу
        }
    }
}

Вывод: Показывает FIFO и LIFO, операции O(1).

import java.util.LinkedList;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.addLast("Элемент 1");
        deque.addLast("Элемент 2");
        System.out.println(deque.removeFirst());  // Элемент 1

        deque.addFirst("Элемент 3");
        System.out.println(deque.removeFirst());  // Элемент 3 (LIFO)
    }
}

Вывод: То же, что и ArrayDeque, но с List-возможностями.

// Примерно так выглядит внутри ArrayList
public class ArrayList<E> {
    private Object[] elementData; // Внутренний массив
    private int size; // Текущее количество реальных элементов
    // ...
}

// Примерная структура узла
private static class Node<E> {
    E item;        // Данные
    Node<E> next;  // Ссылка на следующий узел
    Node<E> prev;  // Ссылка на предыдущий узел
    // ...
}

// Внутренняя логика ArrayList.get(index)
public E get(int index) {
    // ... проверка индекса ...
    return (E) elementData[index]; // Прямое обращение по индексу массива
}

// Примерная логика (упрощенно). Чтобы найти узел с индексом 5:
Node<E> x = first;
for (int i = 0; i < 5; i++) { // Нужно сделать 5 итераций
    x = x.next;
}
return x.item;

// При вставке в середину/начало в ArrayList
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = newElement;
size++;

// Вставка `newNode` между `prevNode` и `currentNode`
newNode.prev = prevNode;
newNode.next = currentNode;
prevNode.next = newNode;
currentNode.prev = newNode;