Java LinkedList

Java 集合框架Java Collections Framework

Связный список — это распространённая базовая структура данных. Это линейный список, но он хранит данные не в линейном порядке; вместо этого каждый узел хранит адрес следующего узла.

Связные списки можно разделить на односвязные списки и двусвязные списки.

Односвязный список содержит два значения: значение текущего узла и ссылку, указывающую на следующий узел.

У двусвязного списка есть три целочисленных значения: значение, ссылка на предыдущий узел и ссылка на следующий узел.

Java LinkedList похож на ArrayList и является часто используемым контейнером данных.

По сравнению с ArrayList LinkedList более эффективен при операциях добавления и удаления, но менее эффективен при операциях поиска и изменения.

Используйте ArrayList в следующих случаях:

  • Частый доступ к определённому элементу списка.
  • Необходимость только добавлять и удалять элементы в конце списка.

Используйте LinkedList в следующих случаях:

  • Вам нужно получать доступ к определённым элементам списка с помощью итерации в цикле.
  • Необходимость часто добавлять и удалять элементы в таких позициях, как начало, середина и конец списка.

LinkedList наследует класс AbstractSequentialList.

LinkedList реализует интерфейс Queue и может использоваться как очередь.

LinkedList реализует интерфейс List и может выполнять операции, связанные со списком.

LinkedList реализует интерфейс Deque и может использоваться как очередь.

LinkedList реализует интерфейс Cloneable и может быть клонирован.

LinkedList реализует интерфейс java.io.Serializable, который поддерживает сериализацию и позволяет передавать данные через сериализацию.

Класс LinkedList находится в пакете java.util. Перед использованием его нужно импортировать. Синтаксис следующий:

// 引入 LinkedList 类
import java.util.LinkedList; 

LinkedList<E> list = new LinkedList<E>();   // 普通创建方法
或者
LinkedList<E> list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表

Создайте простой пример связного списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        System.out.println(sites);
    }
}

Вывод приведенного выше примера:

[Google, Example, Taobao, Weibo]

В большинстве случаев использование ArrayList для доступа к случайным элементам списка более эффективно, но в следующих случаях LinkedList предоставляет более эффективные методы.

Добавление элементов в начало списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        // Используйте addFirst() для добавления элементов в начало
        sites.addFirst("Wiki");
        System.out.println(sites);
    }
}

Вывод приведенного выше примера:

[Wiki, Google, Example, Taobao]

Добавление элементов в конец списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        // Используйте addLast() для добавления элементов в конец
        sites.addLast("Wiki");
        System.out.println(sites);
    }
}

Вывод приведенного выше примера:

[Google, Example, Taobao, Wiki]

Удаление элементов в начале списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        // Используйте removeFirst() для удаления первого элемента
        sites.removeFirst();
        System.out.println(sites);
    }
}

Вывод приведенного выше примера:

[Example, Taobao, Weibo]

Удаление элементов в конце списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        // Используйте removeLast() для удаления хвостового элемента
        sites.removeLast();
        System.out.println(sites);
    }
}

Вывод приведенного выше примера:

[Google, Example, Taobao]

Получите элемент в начале списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        // Используйте getFirst() для получения головного элемента
        System.out.println(sites.getFirst());
    }
}

Вывод приведенного выше примера:

Google

Получите элемент в конце списка:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        // Используйте getLast() для получения хвостового элемента
        System.out.println(sites.getLast());
    }
}

Вывод приведенного выше примера:

Weibo

Итерация по элементам

Мы можем использовать цикл for с методом size() для перебора элементов в списке:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        for (int size = sites.size(), i = 0; i < size; i++) {
            System.out.println(sites.get(i));
        }
    }
}

Метод size() используется для вычисления размера связного списка.

Вывод приведенного выше примера:

Google
Example
Taobao
Weibo

Вы также можете использовать for-each для перебора элементов:

Пример

// Импорт класса LinkedList
import java.util.LinkedList;

public class ExampleTest {
    public static void main(String[] args) {
        LinkedList<String> sites = new LinkedList<String>();
        sites.add("Google");
        sites.add("Example");
        sites.add("Taobao");
        sites.add("Weibo");
        for (String i : sites) {
            System.out.println(i);
        }
    }
}

Вывод приведенного выше примера:

Google
Example
Taobao
Weibo

Общие методы

МетодОписание
public boolean add(E e)Добавляет элемент в конец связного списка, возвращает, успешно ли выполнено действие: true при успехе, false при неудаче.
public void add(int index, E element)Вставляет элемент в указанную позицию.
public boolean addAll(CollectionДобавляет все элементы коллекции в конец связного списка, возвращает, успешно ли выполнено действие: true при успехе, false при неудаче.
public boolean addAll(int index, CollectionДобавляет все элементы коллекции после указанной позиции в связном списке, возвращает, успешно ли выполнено действие: true при успехе, false при неудаче.
public void addFirst(E e)Добавляет элемент в начало.
public void addLast(E e)Добавляет элемент в конец.
public boolean offer(E e)Добавляет элемент в конец связного списка, возвращает, успешно ли это: true — успех, false — неудача.
public boolean offerFirst(E e)Вставляет элемент в начало, возвращает, успешно ли это: true — успех, false — неудача.
public boolean offerLast(E e)Вставляет элемент в конец, возвращает, успешно ли это: true — успех, false — неудача.
public void clear()Очищает связный список.
public E removeFirst()Удаляет и возвращает первый элемент.
public E removeLast()Удаляет и возвращает последний элемент.
public boolean remove(Object o)Удаляет определённый элемент, возвращает, было ли удаление успешным: true при успехе, false при неудаче.
public E remove(int index)Удаляет элемент в указанной позиции.
public E poll()Удаляет и возвращает первый элемент.
public E remove()Удаляет и возвращает первый элемент.
public boolean contains(Object o)</td>Определяет, содержит ли он определённый элемент.
public E get(int index)Возвращает элемент в указанной позиции.
public E getFirst()Возвращает первый элемент.
public E getLast()Возвращает последний элемент.
public int indexOf(Object o)Находит индекс первого вхождения указанного элемента от начала к концу.
public int lastIndexOf(Object o)Находит индекс последнего вхождения указанного элемента.
public E peek()Возвращает первый элемент.
public E element()Возвращает первый элемент.
public E peekFirst()Возвращает первый элемент.
public E peekLast()Возвращает последний элемент.
public E set(int index, E)Устанавливает элемент в указанной позиции.
public Object clone()Клонирует этот список.
public Iterator descendingIterator()Возвращает итератор обратного порядка.
public int size()Возвращает количество элементов в связанном списке.
public ListIterator listIterator(int index)Возвращает итератор, начиная с указанной позиции и до конца.
public Object[] toArray()Возвращает массив, состоящий из элементов связанного списка.
public T[] toArray(T[] a)Возвращает массив, созданный путём преобразования типа элементов связанного списка.

Для дополнительных методов API можно посмотреть:https://www.example.com/manual/jdk11api/java.base/java/util/LinkedList.html

Java 集合框架Java Collections Framework

Другие расширения