2

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

1

2 ответа 2

4

В нутри 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++;
}
7
  • Спасибо!! посмотрю, но правильно ли я понимаю, что этот класс обязательно используется если мы делаем какие-либо манипуляции с линкедлистом? Меня смущало следующее : есть метод add ``` LinkedList list = new LinkedList(); list.add("Geeks"); list.add("for"); System.out.println("The list is:" + list); ``` и здесь мы не используем нод, а просто добавляем, а в другой версии add мы уже используем ссылки и нам необходим класс node
    – bhxbr922
    9 окт 2020 в 10:43
  • @bhxbr922, в какой это версии add() мы не используем Node для добавления? Манипулирование вложенными классами Node не зависит от вас вы можете добавлять что угодно и как угодно, но LinkedList полностью работает по принципу связывания и любая операция добавленя использует Node.
    – DevJ
    9 окт 2020 в 11:07
  • 1
    @bhxbr922, Node это вложенный класс и он используется лишь в нутри для реализации эфекта связывания. Поэтому тот кто пользуется LinkedList даже и не знает о том как в нутри все работает, таким образом разработчики отделили внешний интерфейс класса (public методы) от реализации (тот же вложенный класс Node), вы бы никогда не узнали на основе чего он работает если бы не посмотрели в исходники, а зачастую это и не нужно. Операции добавления работают именно с Node и никак по другому, внешне вы никак это не определите, все работает на уровне реализации
    – DevJ
    9 окт 2020 в 11:12
  • @bhxbr922, если в друг я не правильно понял вопроса, постарайтесь сформулировать его немного по другому
    – DevJ
    9 окт 2020 в 11:15
  • @bhxbr922, Вообще если вам настолько интересно полистайте source там все поймете
    – DevJ
    9 окт 2020 в 11:18
0

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

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

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

введите сюда описание изображения

2
  • 1
    Ответ, несомненно, полезный, но он ведь не отвечает на поставленный вопрос. Автора ведь интересует конкретная имплементация, то есть код.
    – tym32167
    8 окт 2020 в 16:47
  • спасибо за разьяснения, но это я понимаю) Меня интересует кокнкретно класс Node и когда он используется, вот это не понятно
    – bhxbr922
    9 окт 2020 в 6:18

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.