Что такое связанный список как структура данных?

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

Основные типы:

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

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

• Эффективная вставка и удаление элементов (O(1)), если известен узел или его предшественник.
• Динамический размер, не требует выделения фиксированного объема памяти заранее.

Недостатки:

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

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

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null; // Ссылка на следующий узел
    }
}