Структура данных LinkedList в Java

🔥 🚀 Важно для всех, кто работает с Java! 🔥
На JavaRocks ты найдешь уникальные туториалы, практические задачи и редкие книги, которых не найти в свободном доступе. Присоединяйся к нашему Telegram-каналу JavaRocks — стань частью профессионального сообщества! 

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

Если заглянуть в исходный код класса LinkedList (начиная с Java 8 и выше его можно найти на сайте Oracle или прямо в IDE, например в IntelliJ IDEA по Ctrl+B на имени класса), то можно увидить следующую конструкцию:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Здесь ключевым моментом является тот факт, что LinkedList реализует интерфейсы List и Deque.

Интерфейс List сохраняет последовательность добавления элементов и позволяет получить доступ к элементу по индексу. Обычная очередь (Queue) поддерживает добавление элементов в конец и извлечение с начала. Deque — это двусторонняя очередь: она поддерживает добавление и удаление элементов с обеих сторон. По сути, ее можно рассматривать как комбинацию стека и очереди.

Итак, LinkedList реализует эти два интерфейса и позволяет создавать двустороннюю очередь, состоящую из любых объектов, включая null. LinkedList – это коллекция элементов. Это видно в исходном коде класса, где стоит обратить внимание на поля:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Каждый элемент (обычно его называют узлом / Node) содержит сам объект и ссылки на два соседних — предыдущий и следующий. Из-за этого использование памяти у LinkedList не самое эффективное.

Поскольку LinkedList по сути является двусвязной структурой, можно легко добавлять или удалять элементы с обеих сторон.

Конструкторы LinkedList

Из исходного кода видно, что у LinkedList есть два конструктора:

• LinkedList() без параметров используется для создания пустого списка.
• >LinkedList(Collection<? extends E> c) предназначен для создания списка, содержащего элементы указанной коллекции в порядке, в котором их возвращает итератор этой коллекции.

Объявление LinkedList

По сути, связный список (в Java или в любом другом языке) состоит из последовательности узлов. Каждый узел предназначен для хранения объекта определенного типа. Поэтому создать LinkedList в Java можно так:

LinkedList<Integer> myList = new LinkedList<>();

Мы получили объект, способный хранить последовательность чисел и ссылки на соседей. Но в данный момент он пустой.

Основные операции LinkedList

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

Основные методы:

• add(E element) — добавляет указанный элемент в конец списка;
• add(int index, E element) — вставляет элемент в указанную позицию;
• get(int index) — возвращает элемент по индексу;
• remove(int index) — удаляет элемент по индексу;
• remove(Object o) — удаляет первое вхождение указанного элемента, если он есть;
• remove() — возвращает и удаляет первый элемент списка.

Реализация LinkedList в Java: добавление и удаление элементов. Пример

Давайте попробуем выполнить эти операции на практике. Сначала — реализация LinkedList в Java: создать список строк, добавить туда 3 элемента, потом удалить один и вставить новый в середину.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Вот что получится в результате:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList является частью фреймворка Collection. Для удаления элементов можно использовать Iterator, а для списков — ListIterator. Более того, работа через итератор раскрывает главное преимущество LinkedList: высокую скорость операций вставки/удаления. С итератором такие операции выполняются за постоянное время. Дальше в статье напишем код для сравнения ArrayList и LinkedList+Iterator

• Iterator.remove() — удаляет последний элемент, возвращенный этим итератором;
• ListIterator.add(E element) — вставляет элемент в список.

Пример LinkedList в Java: работа итератора

Ниже приведем пример, в котором мы добавляем и удаляем элементы через Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);

       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);

   }
}

Результат работы программы:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Дополнительные операции LinkedList:

• addFirst(), addLast() — добавляют элемент в начало/конец списка;
• clear() — удаляет все элементы из списка;
• contains(Object o) — возвращает true, если список содержит элемент o;
• indexOf(Object o) — возвращает индекс первого вхождения o, либо -1, если элемент отсутствует;
• set(int index, E element) — заменяет элемент по индексу на указанный;
• size() — возвращает количество элементов в списке;
• toArray() — преобразует список в массив, содержащий все его элементы от первого до последнего.

Кроме того, так как LinkedList является двусторонней очередью, он имеет свойственные для стека операции:

• pop() — который извлекает элемент из стека (представленного списком);
• push(E e) — который помещает элемент в стек (представленный этим списком).

Как развернуть LinkedList: пример

В качестве примера разберем популярную, но довольно простую задачу для начинающих. У нас есть список LinkedList, и его нужно развернуть. Самый простой алгоритм — пройти по LinkedList в обратном порядке и добавить каждый элемент в новый список. А может есть более эффективный способ? Вот пример кода:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Результат:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

К этому моменту идея LinkedList в Java должна быть уже вполне понятна. Но знаете ли вы, что существует не один тип связанного списка? Верно! Списки тоже делятся на разные виды: односвязные, двусвязные и кольцевые. Давайте остановимся на каждом из них подробнее.

1. Односвязный список

Начнем с простого. Односвязный список — это самая базовая форма связанного списка. В этой структуре каждый узел состоит из двух частей:

• Data — хранимое значение,
• Next — ссылка (или указатель) на следующий узел в списке.

Последний узел в списке указывает на null, что означает конец списка. Это как улица с односторонним движением — можно двигаться только вперед, но не назад.

Пример:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    Node head;

    // Adding a new node to the end
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Display the list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.display();  // Output: 10 -> 20 -> 30 -> null
    }
}

Основные выводы:

• Простой и удобный способ для последовательного хранения данных.
• Перемещаться можно только в одном направлении.
• Добавление элементов в начало или конец списка легко реализуется.

2. Двусвязный список

Поднимемся на уровень выше и перейдем к двусвязному списку. В отличие от односвязного, у каждого узла тут не одна, а целых две ссылки:

• Data — хранимое значение,
• Next — ссылка на следующий элемент,
• Prev — ссылка на предыдущий элемент.

Это значит, что можно двигаться вперед и назад по списку. Это уже похоже на дорогу с двусторонним движением.

Пример:

class DNode {
    int data;
    DNode next;
    DNode prev;

    DNode(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedList {
    DNode head;

    // Add a new node to the end
    public void append(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }

    // Display the list forward
    public void displayForward() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.displayForward();  // Output: 10 <-> 20 <-> 30 <-> null
    }
}

Основные выводы:

• По списку можно двигаться в обоих направлениях.
• Требует больше памяти из-за дополнительной ссылки.
• Вставка и удаление элементов более гибкие.

3. Кольцевой список

Представьте себе гоночную трассу, где финишная линия соединяется со стартом. Именно так работает кольцевой список.

В этом типе списка:

• последний узел указывает не на null, а на первый элемент,
• это может относиться как к односвязным, так и к двусвязным спискам.

Пример:

class CNode {
    int data;
    CNode next;

    CNode(int data) {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList {
    CNode head;

    public void append(int data) {
        CNode newNode = new CNode(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
            return;
        }
        CNode current = head;
        while (current.next != head) {
            current = current.next;
        }
        current.next = newNode;
        newNode.next = head;
    }

    public void display() {
        if (head == null) return;
        CNode current = head;
        do {
            System.out.print(current.data + " -> ");
            current = current.next;
        } while (current != head);
        System.out.println("(back to head)");
    }

    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();
        list.append(10);
        list.append(20);
        list.append(30);
        list.display();  // Output: 10 -> 20 -> 30 -> (back to head)
    }
}

Основные выводы:

• Эффективен для задач, требующих бесконечного цикла данных.
• У списка нет “конца” — отлично подходит для систем реального времени.

Какой список выбрать?

Так какой же связанный список лучше? На самом деле все зависит от задачи.

• Односвязный список: простой, эффективный для выполнения базовых операций.
• Двусвязный список: оптимален, если нужно перемещаться в обе стороны.
• Циклический список: отлично подходит для систем, где требуется непрерывный цикл.

LinkedList vs ArrayList: когда использовать первый

И LinkedList, и ArrayList являются реализациями интерфейса List.

• LinkedList реализован с помощью двусвязного списка.
• ArrayList реализован с помощью динамически изменяемого массива.

Как уже известно, каждый элемент LinkedList содержит объект и две ссылки на соседей. Это означает дополнительные затраты памяти. В случае ArrayList используется массив, который автоматически изменяет размер.
Некоторые операции у LinkedList и ArrayList выглядят одинаково, но работают по-разному: в ArrayList — с массивом, в LinkedList — со ссылками.

ArrayList — самая популярная реализация List. Точно стоит использовать ArrayList, если важен быстрый доступ по индексу, поскольку эти операции выполняются за постоянное время. Добавление в конец списка в среднем также выполняется за постоянное время. Более того, у ArrayList нет дополнительных затрат на хранение ссылок. Недостатком можно назвать лишь скорость вставки и удаления элементов, если это делается не в конце списка.

LinkedList более удобен в случаях, когда важна производительность операций вставки и удаления: при работе через итераторы они выполняются за постоянное время. Доступ к элементам по индексу выполняется путем поиска от начала или конца (в зависимости от того, что ближе) до нужного элемента. Но не стоит забывать о дополнительных затратах памяти на хранение ссылок между элементами.

Здесь представлены стандартные операции LinkedList и ArrayList вместе с их алгоритмической сложностью.
N — это количество элементов, которые уже есть в списке.
O(N) означает, что в худшем случае необходимо “пройтись” по всему списку до нужной позиции, например, при вставке нового элемента.
O(1) означает, что операция выполняется за постоянное время, независимо от количества элементов.

Временная сложность операций LinkedList

Временная сложность операций ArrayList

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

ArrayList, безусловно, самая популярная реализация List. Однако бывают ситуации, когда операции добавления/удаления элементов требуются слишком часто. В этом случае LinkedList в сочетании с Iterator может быть выгоднее. Пример: есть длинный список, из которого нужно удалить все элементы. Попробуем решить эту задачу с помощью ArrayList и с помощью LinkedList вместе с Iterator. Сравним время выполнения операций и выведем результаты в консоль.
Вот код:

import java.util.*;
import java.util.function.BiPredicate;

public class ListTest2 {

   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());

       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }

   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);

           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }

   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }

   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }

           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Результат для ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Результат для LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Как видите, в данном случае LinkedList гораздо эффективнее.

Если честно, в реальной разработке LinkedList используется довольно редко. Тем не менее, профессионал должен знать о существовании этой структуры данных и ее преимуществах. Даже если LinkedList редко встречается в реальном коде, на собеседованиях для Junior Java-разработчиков этот вопрос задают часто.

Дополнение: Односвязный список на Java

В стандартной библиотеке Java нет односвязного списка. Односвязный список — это структура, в которой каждый узел содержит объект и ссылку на следующий узел, но не на предыдущий. LinkedList в Java — двусвязный, но никто не запрещает создать свою собственную структуру данных, например, односвязный список (Singly ,code>Linked List).

Как это сделать:

1. Создайте класс Node с двумя полями, data и next (где next — это ссылка на следующий узел).
2. Создайте класс FirstLast с двумя полями, head и tail.
3. Реализуйте метод add() для добавления нового узла в список. Сначала проверьте, пуст ли список (head == null). Если да, то head и tail ссылаются на новый узел. Если список не пуст, новый узел будет добавлен в конец: next текущего tail указывает на новый узел, а новый узел становится tail.

Кстати, в качестве упражнения можно попробовать создать свой собственный LinkedList. Удачи в обучении!

Перевод статьи «Linked List Data Structure in Java».