Что такое связный список (LinkedList)?

Связный список - это линейная структура данных, в которой элементы не хранятся в смежных ячейках памяти. Вместо этого каждый элемент, называемый узлом, содержит данные и ссылку (или указатель) на следующий узел в последовательности.

Существуют различные типы связных списков:

• Односвязный список: Каждый узел содержит ссылку только на следующий узел.
• Двусвязный список: Каждый узел содержит ссылки как на следующий, так и на предыдущий узел.
• Циклический связный список: Последний узел ссылается на первый узел, образуя цикл.

Основные операции над связным списком:

• Вставка: Добавление нового узла в список.
• Удаление: Удаление узла из списка.
• Поиск: Поиск узла по значению.
• Обход: Последовательный доступ ко всем узлам списка.

Преимущества:

• Гибкость вставки и удаления элементов в любой позиции.
• Эффективное управление памятью, так как элементы не требуют непрерывных блоков.

Недостатки:

• Медленный произвольный доступ к элементам (требуется последовательный обход).
• Требуется дополнительная память для хранения ссылок.

Пример структуры узла в односвязном списке:

class Node {
    int data;
    Node next;

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