Класс LinkedList

1. Введение
2. Конструкторы класса
3. Структура LinkedList
4. Разница между LinkedList и ArrayList
5. Пример использования LinkedList

1. Введение

Мы продолжаем рассматривать Collection Framework и темой нашего сегодняшнего урока будет класс LinkedList. Класс LinkedList реализует сразу два интерфейса - List, Deque. LinkedList – это двусвязный список. С его помощью можно организовать стек, очередь, двойную очередь, а также список. Этот класс позволяет добавлять любые значения, в том числе и null.

2. Конструкторы класса LinkedList

• LinkedList() - первый конструктор без параметров, мы создаём пустую коллекцию.
• LinkedList(Collection<? extends Е> с) - на вход мы можем передать другую коллекцию.

3. Структура LinkedList

Класс LinkedList достаточно часто используют, поэтому необходимо чётко понимать как он устроен внутри. Давайте посмотрим на часть внутренней структуры класса LinkedList. Внутри класса LinkedList существует статический внутренний класс Entry. Кстати, это хороший пример статического внутреннего класса. Внутри класса Entry будет содержаться сам элемент, а также ссылки на следующий элемент next и предыдущий элемент - prev:

private static class Entry<E>
{
    E element;
    Entry<E> next;
    Entry<E> prev;
    
    Entry(E element, Entry<E> next, Entry<E> prev)
    {
        this.element = element;
        this.next = next;
        this.prev = prev;
    }
}

Графически структуру LinkedList можно представить таким образом: 

На этом изображении LinkedList содержит четыре элемента: элементы А, B, C и D.  Например, у элемента B есть ссылка на предыдущий элемент и на последующий элемент. Ссылки представлены стрелочками. 

4. Разница между LinkedList и ArrayList

Очень часто класс LinkedList сравнивают с ArrayList. В чём различие между ними? И с помощью ArrayList, и с помощью LinkedList можно организовать список, но ArrayList - это динамический массив. Внутри ArrayList все элементы хранятся в массиве, а здесь, как вы видите, структура несколько другая. Зачем это нужно? Представьте, что нам необходимо удалять либо добавлять элементы внутрь этой структуры. При удалении элемента B, просто перезаписываются ссылки у соседних элементов. Теперь элемент А ссылается не на элемент B, а на элемент C. Точно также в элементе C мы просто перезаписываем ссылку. Теперь она указывает на элемент А: 

Возьмем другую задачу - мы хотим получить какой-то элемент по индексу. Допустим нам нужен элемент с индексом 2. Что нам нужно сделать, чтобы его найти? Мы идём по ссылкам (стрелочкам) и перебираем все элементы. Мы перебираем А, потом мы находим B и только потом мы находим С, что достаточно долго. Поэтому для такой операции класс LinkedList не предназначен. В этом случае лучше использовать класс ArrayList. На получение элемента по индексу или значению потребуется сложность операции - О(n). Однако на добавление и удаление из середины списка нам потребуется сложность О(1). Это будет работать достаточно быстро.

В каком случае лучше использовать LinkedList? Допустим у вас есть задача, в которой вы знаете что вам нужно перебрать все элементы. Вы будете идти от начала коллекции до конца, просматривать элементы, может быть проверять их по какому-то критерию, удалять либо добавлять новые элементы внутрь коллекции. Для таких задач подойдёт класс LinkedList. Если же вы знаете, что у вас есть задача, в которой вам нужно быстро получить элемент по индексу, в этом случае используйте класс ArrayList.

5. Пример использования LinkedList

Давайте посмотрим на пример использования класса LinkedList. В следующем классе объявляется переменная list, которая указывает на коллекцию LinkedList. Обратите внимание, что здесь переменная объявлена как класс LinkedList. Это не очень хорошо, обычно всё-таки используется интерфейс - либо List, либо интерфейс Queue. Но в этом случае это сделано специально, чтобы показать в этой программе, что мы можем работать с LinkedList как со списком, так и с очередью: 

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();

        list.add("F");
        list.add("B");
        list.add("D");
        list.add("E");
        list.add("C");
        list.addLast("Z");
        list.addFirst("A");
        list.add(1, "A2");
        System.out.println("Содержимое: " + list);

        list.remove("F");
        list.remove(2);
        list.removeFirst();
        list.removeLast();
        System.out.println("Содержимое после удаления: " + list);

        String val = list.get(2);
        list.set(2, val + "+");
        System.out.println("Содержимое после изменения: " + list);
    }
}

Итак, сначала мы добавляем в список несколько элементов - F B D E C - с помощью метода add(). Они будут добавляться в таком же порядке - и в списке, и в очереди элементы по умолчанию добавляются в конец. Дальше с помощью метода addLast() мы добавляем элемент в конец списка и с помощью метода addFirst() в начало списка. Также в программе показано использование метода add() с индексом - элемент А2 добавляется в позицию единица.

Также в этой программе используются методы remove(), с помощью которого удаляется объект F и элемент в позиции два. Есть также методы removeFirst() и removeLast(), с помощью которых мы удаляем первый и последний элемент в списке. 

В последнем кусочке нашей программы используется метод get(), для получения элемента по индексу. Мы получили этот элемент и записали в переменную val. Дальше, мы хотим модифицировать этот элемент, для чего используем метод set(), указывая позицию два. 

И давайте посмотрим на результат программы:

Содержимое: [A, A2, F, B, D, E, C, Z]
Содержимое после удаления: [A2, D, E, C]
Содержимое после изменения: [A2, D, E+, C]

Элемент А был добавлен в начало, элемент Z в конец и элемент А2 был добавлен в позицию 1 (индексация начинается с нуля).  

Давайте посмотрим, на содержимое после удаления -  удалились элемент F, элемент из позиции 2, а также удалились первый (элемент А) и последний элемент (элемент C). 

Содержимое после изменения - изменился элемент в позиции два, мы добавили к нему плюс.