Java LinkedList: полное руководство с примерами

Java LinkedList

Узнайте, как использовать Java LinkedList для эффективной манипуляции данными, с практическими примерами кода и лучшими практиками.

Класс LinkedList в Java Collections Framework реализует двусвязный список. Каждый элемент, или узел, содержит три поля:

• prev — ссылка на предыдущий узел (null для первого элемента)
• next — ссылка на следующий узел (null для последнего элемента)
• data — фактическое значение, хранящееся в узле

---

Создание Java LinkedList

Создайте экземпляр LinkedList с конкретным типом элементов:

LinkedList<Type> list = new LinkedList<>();

Примеры:

// Список целых чисел
LinkedList<Integer> numbers = new LinkedList<>();
// Список строк
LinkedList<String> words = new LinkedList<>();

---

Пример: создание LinkedList в Java

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
    }
}

Вывод

LinkedList: [Dog, Cat, Cow]

Этот код демонстрирует базовый LinkedList с именем animals, заполненный тремя элементами через add().

---

Как работает Java LinkedList

В отличие от массивов, узлы разбросаны в памяти и связаны вместе. На диаграмме ниже изображены три узла и их связи.

• Dog — первый узел, prev = null, next = Cat
• Cat — средний узел, prev = Dog, next = Cow
• Cow — последний узел, prev = Cat, next = null

Для более глубокого понимания см. статью Linked List.

---

Ключевые методы LinkedList

Ниже приведены наиболее часто используемые операции:

• Добавление элементов
• Доступ к элементам
• Обновление элементов
• Удаление элементов

---

1. Добавление элементов

Используйте add() для добавления узла в конец, опционально указывая индекс:

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
        animals.add(1, "Horse");
        System.out.println("Updated LinkedList: " + animals);
    }
}

Вывод

LinkedList: [Dog, Cat, Cow] Updated LinkedList: [Dog, Horse, Cat, Cow]

Второй add() вставляет "Horse" в индекс 1, сдвигая последующие элементы.

---

2. Доступ к элементам

Получите элемент по индексу с помощью get():

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Python");
        languages.add("Java");
        languages.add("JavaScript");
        System.out.println("LinkedList: " + languages);
        String str = languages.get(1);
        System.out.print("Element at index 1: " + str);
    }
}

Вывод

LinkedList: [Python, Java, JavaScript] Element at index 1: Java

Итерацию также можно выполнять через iterator() или listIterator() для продвинутого обхода.

---

3. Обновление элементов

Замените элемент в конкретном индексе с помощью set():

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        languages.add("Java");
        System.out.println("LinkedList: " + languages);
        languages.set(3, "Kotlin");
        System.out.println("Updated LinkedList: " + languages);
    }
}

Вывод

LinkedList: [Java, Python, JavaScript, Java] Updated LinkedList: [Java, Python, JavaScript, Kotlin]

---

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

Удалите элемент по индексу с помощью remove():

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> languages = new LinkedList<>();
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        languages.add("Kotlin");
        System.out.println("LinkedList: " + languages);
        String removed = languages.remove(1);
        System.out.println("Removed Element: " + removed);
        System.out.println("Updated LinkedList: " + languages);
    }
}

Вывод

LinkedList: [Java, Python, JavaScript, Kotlin] Removed Element: Python New LinkedList: [Java, JavaScript, Kotlin]

---

Другие полезные методы

Метод	Описание
contains()	Проверяет наличие значения
indexOf()	Индекс первого вхождения
lastIndexOf()	Индекс последнего вхождения
clear()	Удаляет все элементы
iterator()	Предоставляет Iterator

---

LinkedList как Queue и Deque

Поскольку LinkedList реализует Queue и Deque, он поддерживает операции FIFO и LIFO. Часто используемые методы:

Метод	Описание
addFirst()	Добавить в начало
addLast()	Добавить в конец
getFirst()	Посмотреть начало
getLast()	Посмотреть конец
removeFirst()	Удалить из начала
removeLast()	Удалить из конца
peek()	Посмотреть голову без удаления
poll()	Получить и удалить голову
offer()	Поставить в хвост

Пример: LinkedList как Queue

import java.util.LinkedList;
import java.util.Queue;
class Main {
    public static void main(String[] args){
        Queue<String> languages = new LinkedList<>();
        languages.add("Python");
        languages.add("Java");
        languages.add("C");
        System.out.println("LinkedList: " + languages);
        String first = languages.peek();
        System.out.println("Accessed Element: " + first);
        String removed = languages.poll();
        System.out.println("Removed Element: " + removed);
        System.out.println("LinkedList after poll(): " + languages);
        languages.offer("Swift");
        System.out.println("LinkedList after offer(): " + languages);
    }
}

Вывод

LinkedList: [Python, Java, C] Accessed Element: Python Removed Element: Python LinkedList after poll(): [Java, C] LinkedList after offer(): [Java, C, Swift]

Пример: LinkedList как Deque

import java.util.LinkedList;
import java.util.Deque;
class Main {
    public static void main(String[] args){
        Deque<String> animals = new LinkedList<>();
        animals.add("Cow");
        System.out.println("LinkedList: " + animals);
        animals.addFirst("Dog");
        System.out.println("LinkedList after addFirst(): " + animals);
        animals.addLast("Zebra");
        System.out.println("LinkedList after addLast(): " + animals);
        animals.removeFirst();
        System.out.println("LinkedList after removeFirst(): " + animals);
        animals.removeLast();
        System.out.println("LinkedList after removeLast(): " + animals);
    }
}

Вывод

LinkedList: [Cow] LinkedList after addFirst(): [Dog, Cow] LinkedList after addLast(): [Dog, Cow, Zebra] LinkedList after removeFirst(): [Cow, Zebra] LinkedList after removeLast(): [Cow]

---

Итерация по LinkedList

Улучшенный for-цикл предлагает лаконичный способ обхода элементов:

import java.util.LinkedList;
class Main {
    public static void main(String[] args){
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);
        System.out.println("Accessing linked list elements:");
        for(String animal: animals){
            System.out.print(animal + ", ");
        }
    }
}

Вывод

LinkedList: [Cow, Cat, Dog] Accessing linked list elements: Cow, Cat, Dog,

---

LinkedList против ArrayList

Оба класса реализуют List, но отличаются характеристиками производительности:

LinkedList	ArrayList
Реализует List, Queue, Deque	Реализует List
Узел хранит prev, data, next	Один элемент на слот массива
Двусвязная структура	Изменяемый массив
Вставки/удаления O(1) при известной позиции	Вставки после индекса требуют сдвига O(n)
Случайный доступ требует обхода O(n)	Прямой доступ по индексу O(1)

---

Примечание: Вы можете создать LinkedList через любой из его интерфейсов:

// через List
List<String> animals1 = new LinkedList<>();
// через Queue
Queue<String> animals2 = new LinkedList<>();
// через Deque
Deque<String> animals3 = new LinkedList<>();

При использовании ссылки интерфейса доступны только методы, определённые этим интерфейсом.