LinkedList: примеры (JAVA)

Короткие примеры использования

Создание и базовые операции:

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("one");
list.addFirst("zero");
list.addLast("two");
System.out.println(list);
System.out.println(list.get(1));

[zero, one, two]
one

Очередь и дек операции:

LinkedList<Integer> q = new LinkedList<>();
q.offer(10);
q.offer(20);
int head = q.poll();
Integer peeked = q.peek();
System.out.println(head + ", " + peeked);

10, 20

Удаление по объекту и по индексу (особенность с Integer):

LinkedList<Integer> nums = new LinkedList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.remove(Integer.valueOf(2)); // удаляет элемент со значением 2
System.out.println(nums);
nums.remove(0); // удаляет элемент по индексу 0
System.out.println(nums);

[1, 3]
[3]

Похожие коллекции в Java

Краткий обзор альтернатив и особенности:

• ArrayList - динамический массив. Быстрый произвольный доступ по индексу O(1), медленные вставки/удаления в середине O(n). Предпочтителен для частых чтений.
• ArrayDeque - эффективный двусторонний буфер на базе массива. Лучше для реализации очередей и стеков, чем LinkedList, если требуется быстрый доступ к краям и экономия памяти.
• Vector - синхронизированный вариант ArrayList. Устаревшая опция, обычно используют коллекции из java.util.concurrent для многопоточности.
• CopyOnWriteArrayList - предназначен для сценариев с частыми чтениями и редкими изменениями; дорого при модификации.
• PriorityQueue - очередь с приоритетом, не упорядочивает элементы в списке, используется когда нужен приоритетный порядок.

Выбор: если нужны частые вставки/удаления в середине - LinkedList; для произвольного доступа и плотной памяти - ArrayList; для дек-операций с высокой производительностью и малым потреблением памяти - ArrayDeque.

Аналоги в других языках

Краткие сравнения и примеры.

PHP: SplDoublyLinkedList - двусвязный список.

$list = new SplDoublyLinkedList();
$list->push('a');
$list->unshift('b');
echo $list->pop();

a

JavaScript: нет встроенного LinkedList; обычно используются массивы (Array) или реализуют собственную структуру.

// простой пример на массивах
let arr = [];
arr.push(1);
arr.unshift(0);
console.log(arr);

[0,1]

Python: collections.deque - эффективный для операций на краях; списки (list) эффективны для случайного доступа.

from collections import deque
d = deque()
d.append(1)
d.appendleft(0)
print(d.popleft())

0

C#: System.Collections.Generic.LinkedList<T> - двусвязный список, похож на Java LinkedList, но методы и итераторы отличаются по API.

var list = new LinkedList<int>();
list.AddLast(1);
list.AddFirst(0);
Console.WriteLine(list.First.Value);

0

Go: пакет container/list предоставляет двусвязный список.

import "container/list"

l := list.New()
l.PushBack(1)
front := l.Front()
fmt.Println(front.Value)

1

Kotlin: использует коллекции Java, можно применять java.util.LinkedList или интерфейсы Kotlin MutableList. Отличие - синтаксический сахар и расширения.

В других языках особенности: в некоторых есть готовые двусвязные списки (PHP, C#, Go), в JavaScript и Lua обычно используют массивы/таблицы или реализуют структуру вручную; поведение методов (возврат null или исключение) и экономия памяти отличаются от Java.

Типичные ошибки и ошибки новичков

Частые проблемы и примеры:

• IndexOutOfBoundsException при обращении по некорректному индексу:

LinkedList<String> a = new LinkedList<>();
System.out.println(a.get(0));

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

• NoSuchElementException при использовании remove() или getFirst() на пустом списке:

LinkedList<Integer> l = new LinkedList<>();
l.remove();

Exception in thread "main" java.util.NoSuchElementException

• Ошибки при итерации: модификация коллекции вне итератора вызывает ConcurrentModificationException.

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
for (Integer x : list) {
    list.add(2); // приведет к ConcurrentModificationException
}

Exception in thread "main" java.util.ConcurrentModificationException

• Неправильное использование перегруженных методов: remove(Object) и remove(int) у LinkedList<Integer> могут быть перепутаны. Для удаления по значению использовать Integer.valueOf().

LinkedList<Integer> n = new LinkedList<>();
n.add(1);
n.add(2);
n.remove(1); // удалит элемент по индексу 1, а не значение 1

[1]

• Производительность: попытки использовать LinkedList для частого произвольного доступа (много вызовов get(i)) приводят к O(n^2) поведению; рекомендуется использовать ArrayList для подобных задач.

Изменения и эволюция API

За последние версии Java сам класс LinkedList API не подвергался существенным изменениям. Основные изменения экосистемы были связаны с добавлением в интерфейсы коллекций следующих возможностей:

• Java 8: появление default-методов в интерфейсах коллекций, таких как removeIf, stream, parallelStream - LinkedList наследует эти реализации.
• Появление утилит в Collections и Stream API улучшило интеграцию LinkedList с функциональным стилем, но структура данных и её характеристики остались прежними.

В новых релизах JDK не было декларируемых деактиваций методов LinkedList; предпочтения по использованию коллекций регулируются рекомендациями по производительности (например, предпочитать ArrayDeque для дек-операций в большинстве случаев).

Расширенные и нестандартные примеры

1) Использование ListIterator для обхода и модификации во время итерации:

LinkedList<String> names = new LinkedList<>();
names.add("Alice");
names.add("Bob");
ListIterator<String> it = names.listIterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("Bob")) {
        it.set("Bobby"); // безопасная модификация текущего элемента
        it.add("Charlie"); // вставка перед следующей позицией
    }
}
System.out.println(names);

[Alice, Bobby, Charlie]

Пояснение: ListIterator позволяет безопасно менять список без ConcurrentModificationException.

2) Реализация двусторонней очереди с таймаутом (псевдокод): использование циклов и poll - реализация простого потребителя/производителя без блокировок.

LinkedList<String> buffer = new LinkedList<>();
// producer
buffer.offer("task1");
// consumer
String task = buffer.poll(); // если null, задач нет

(в зависимости от состояния buffer возвращается строка или null)

3) Конвертация и потоковые операции:

LinkedList<Integer> list = new LinkedList<>();
list.add(1); list.add(2); list.add(3);
int sum = list.stream().mapToInt(Integer::intValue).sum();
System.out.println(sum);

6

4) Объединение двух списков с сохранением порядка и без копирования элементов вручную:

LinkedList<String> a = new LinkedList<>();
a.add("x");
LinkedList<String> b = new LinkedList<>();
b.add("y");
a.addAll(b);
System.out.println(a);

[x, y]

5) Использование descendingIterator() для прохода в обратном порядке без разворачивания списка:

LinkedList<Integer> nums = new LinkedList<>();
nums.add(1); nums.add(2); nums.add(3);
Iterator<Integer> desc = nums.descendingIterator();
while (desc.hasNext()) System.out.print(desc.next() + " ");

3 2 1 

6) Применение как база для простой реализации LRU-кэша (демонстрация идеи; для производительности предпочтительнее LinkedHashMap):

int capacity = 3;
LinkedList<String> cache = new LinkedList<>();
void access(String key) {
    cache.remove(key);
    cache.addFirst(key);
    if (cache.size() > capacity) cache.removeLast();
}
// пример вызовов
access("a"); access("b"); access("c"); access("a"); // теперь порядок a,c,b

(последовательность в cache: [a, c, b])

7) Эффективное удаление по условию removeIf, избегая явной итерации:

LinkedList<Integer> nums2 = new LinkedList<>();
nums2.addAll(java.util.Arrays.asList(1,2,3,4,5));
nums2.removeIf(n -> n % 2 == 0); // удаляет четные
System.out.println(nums2);

[1, 3, 5]

Пояснение: некоторые шаблонные решения (LRU, двусторонние очереди, комбинированные операции с потоками) применяют LinkedList, но при высоких требованиях к производительности следует сравнить с ArrayDeque или специализированными структурами.