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

Связанный список (Linked List)

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

Основные компоненты

Каждый узел (node) связанного списка содержит:

1. Данные (value) — значение или объект, хранящийся в узле
2. Ссылка на следующий узел (next) — указатель на следующий элемент списка
3. В двусвязном списке еще есть ссылка на предыдущий узел (prev)

Однонаправленный связанный список

// Определение узла
public class Node<T> {
    T value;
    Node<T> next;
    
    public Node(T value) {
        this.value = value;
        this.next = null;
    }
}

// Простая реализация связанного списка
public class LinkedList<T> {
    private Node<T> head;
    
    // Добавление элемента в конец
    public void add(T value) {
        Node<T> newNode = new Node<>(value);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    
    // Удаление элемента
    public boolean remove(T value) {
        if (head == null) return false;
        
        if (head.value.equals(value)) {
            head = head.next;
            return true;
        }
        
        Node<T> current = head;
        while (current.next != null) {
            if (current.next.value.equals(value)) {
                current.next = current.next.next;
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    // Поиск элемента
    public boolean contains(T value) {
        Node<T> current = head;
        while (current != null) {
            if (current.value.equals(value)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    // Получение размера
    public int size() {
        int count = 0;
        Node<T> current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

Двусвязный список

// Узел двусвязного списка
public class DoublyNode<T> {
    T value;
    DoublyNode<T> next;
    DoublyNode<T> prev;
    
    public DoublyNode(T value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedList<T> {
    private DoublyNode<T> head;
    
    public void addFirst(T value) {
        DoublyNode<T> newNode = new DoublyNode<>(value);
        if (head != null) {
            newNode.next = head;
            head.prev = newNode;
        }
        head = newNode;
    }
    
    public void addLast(T value) {
        DoublyNode<T> newNode = new DoublyNode<>(value);
        if (head == null) {
            head = newNode;
            return;
        }
        
        DoublyNode<T> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }
    
    // Удаление в двусвязном списке эффективнее благодаря prev
    public void remove(DoublyNode<T> node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        
        if (node.next != null) {
            node.next.prev = node.prev;
        }
    }
}

Использование LinkedList в Java

import java.util.LinkedList;
import java.util.Iterator;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        
        // Добавление элементов
        list.add("Alice");
        list.add("Bob");
        list.addFirst("Charlie");  // добавить в начало
        list.addLast("David");      // добавить в конец
        
        // Удаление элементов
        list.remove("Bob");
        list.removeFirst();
        list.removeLast();
        
        // Итерирование
        for (String name : list) {
            System.out.println(name);
        }
        
        // Обратное итерирование
        Iterator<String> iterator = list.descendingIterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

Сравнение со значком (LList) и массивом

Циркулярный связанный список

// В циркулярном списке последний узел указывает на первый
public class CircularLinkedList<T> {
    private Node<T> head;
    
    public void add(T value) {
        Node<T> newNode = new Node<>(value);
        if (head == null) {
            head = newNode;
            head.next = head;  // указываем на себя
        } else {
            Node<T> current = head;
            while (current.next != head) {
                current = current.next;
            }
            current.next = newNode;
            newNode.next = head;  // новый узел указывает на head
        }
    }
}

Преимущества и недостатки

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

• Динамический размер — не нужно заранее знать количество элементов
• Эффективное добавление/удаление в начале и конце
• Нет фрагментации памяти в отличие от массива

Недостатки:

• Нет прямого доступа по индексу — требуется O(n) времени
• Требует дополнительную память на хранение ссылок
• Меньше кэша-эффективен, чем массив
• Сложнее в реализации и отладке

Когда использовать LinkedList

• Часто добавляете/удаляете элементы в начале
• Не нужен случайный доступ по индексу
• Память фрагментирована, а связанный список более гибок
• Нужна реализация стека (Stack) или очереди (Queue)

Связанный список — это фундаментальная структура данных, которая критична для понимания алгоритмов и структур данных в Java.