tgoop.com/javaproglib/7018
Last Update:
👀 Внутреннее устройство LinkedList
LinkedList — это классическая реализация двусвязного списка. На поверхности он выглядит как обычная коллекция, реализующая интерфейсы List, Deque и Queue. Но под капотом это структура узлов (Node), которые связаны друг с другом через ссылки на предыдущий и следующий элемент.
📦 Базовая структура
Каждый элемент списка хранится в отдельном объекте Node<E>, который содержит:
▪️ E item — сам элемент
▪️ Node<E> next — ссылка на следующий узел
▪️ Node<E> prev — ссылка на предыдущий узел
У LinkedList есть два поля:
▪️ first — голова списка
▪️ last — хвост списка
Это позволяет быстро добавлять элементы в начало и конец.
⚡️ Добавление и удаление
— Добавление в начало (addFirst) или конец (addLast) → O(1): меняем ссылки у пары узлов.
— Удаление головы или хвоста также → O(1).
— Вставка или удаление в середине требует сначала дойти до нужного узла → O(n).
🌊 Поиск элемента
— По индексу: список не хранит массив, значит придётся идти по ссылкам.
— Оптимизация: если индекс ближе к голове, обход идёт с first, если к хвосту — с last.
Сложность в среднем — O(n/2), то есть линейная.
📊 Производительность
— Доступ по индексу → O(n).
— Добавление/удаление в начало или конец → O(1).
— Вставка/удаление в середину → O(n).
— Итерация по списку → O(n), но эффективно, так как используется последовательный проход по ссылкам.
⚖️ Важные нюансы
— В отличие от ArrayList, в LinkedList нет операций с массивами и «ресайзинга».
— Но расходует больше памяти: каждый узел хранит не только элемент, но и две ссылки (prev/next).
— Итераторы fail-fast: изменение списка во время обхода бросает ConcurrentModificationException.
🔄 Итераторы и Deque
LinkedList реализует Deque, что делает его удобным для очередей и стеков. Offer, poll, peek работают за O(1). Push/pop превращают список в стек.
🧮 Когда использовать
На практике ArrayList почти всегда быстрее по времени и эффективнее по памяти.
LinkedList может быть полезен только в редких случаях, когда нужны очень частые вставки/удаления в середину коллекции (без итерации по коллекции) и не важен доступ по индексу. В остальных случаях выбирайте ArrayList.
Ставьте 🔥, если хотите такой же пост по другим коллекциям, например CopyOnWriteArrayList.
#CoreJava
