Класс Node в LinkedList

Question

Прохожу тему коллекции и LinkedList. Прочитала, что список (LinkedList) состоит из звеньев (Nodes), но мне не особо понятно что это за зверь и когда мы используем этот класс. Во время обучения была задача на проверку списка на наличие цикла, где и использовался этот класс, но при добавлении элемента в список мы не используем этот класс. За обьяснения и пример буду очень благодарна.

Answer 1

LinkedList хранит элементы в виде связного списка. Связный список состоит из элементов, которые хранят данные и ссылки на следующий и предыдущий элементы. Допустим у нас в списке 10 элементов, вот как вставить элемент в середину:

Ярко-красным выделены ссылки, которые поменялись – они теперь указывают на новый элемент. Ярко-фиолетовым выделены новые ссылки – ссылки нового элемента на его соседей. Плюсы: коллекция LinkedList может занимать разбросанные области памяти; является ordered (упорядоченной). Минусы: не synchronized коллекция (не поддерживает работу нескольких потоков). Рекомендуется применять когда часто нужно выполнять операции добавления и удаления элементов

Сравнение ArrayList и LinkedList

Answer 2

В нутри LinkedList есть вложенный класс Node, который представляет собой елемент содержащий данные, а также ссылку на слудующий елемент и придыдущий, собственно LinkedList и работает на таких нодах. Код взят из open-source JDK 14:

 private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Вот так выглядит класс Node в нутри LinkedList. На будущие если вас интересуют такие вещи и как они устроенный в нутри то зайдите в основную директорию jdk далее в файл lib там есть архив с названием src, а в нем множество файлов .java из Java.SE

Поэтому можете зайти туда в src найти пакет java.base далее util; и в нем LinkedList и подробно изучить как он работает в нутри. Вообще src это то место где можно посмотреть как "деды Java программировали" и чему нибуть научится.

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

Вот например как устроен метод add():

public boolean add(E e) {
    linkLast(e);
    return true;
}

Ну и метод linkLast(E e) который показывает как-же все таки используется этот Node в LinkeList:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

БЛОГ НА HUSL

Класс Node в LinkedList

Ответы (2 шт):

Сравнение ArrayList и LinkedList