Что такое связанный список

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

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

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

Пример на Java:

class Node {
    int data;
    Node next;

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

class LinkedList {
    Node head;

    void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
    }
}

Плюсы:

• Динамическое добавление/удаление элементов (O(1) для головы).
• Не требует непрерывной памяти.

Минусы:

• Доступ к элементу — O(n).
• Дополнительная память для хранения ссылок.