В этой статье мы рассмотрим, как реализовать структуру данных связанного списка в Java, не полагаясь на Collection Framework. Связанные списки — это фундаментальные структуры данных, состоящие из узлов, каждый из которых содержит значение и ссылку на следующий узел в последовательности. Понимая основные принципы и используя базовые концепции Java, мы можем создать собственную реализацию связанного списка.

Содержание:

1. Создание класса узла
2. Создание класса LinkedList
3. Вставка элементов
4. Удаление элементов
5. Поиск элемента
6. Обход связанного списка
7. Заключение

Создание класса узла.
Первым шагом является определение класса узла, который представляет один узел в связанном списке. Каждый узел будет содержать значение и ссылку на следующий узел.

class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
    }
}

Создание класса LinkedList.
Далее нам нужно создать класс LinkedList, который инкапсулирует логику управления связанным списком.

class LinkedList {
    private Node head;

    // LinkedList methods will be implemented here
}

Вставка элементов.
Чтобы вставить элемент в начало связанного списка, нам нужно создать новый узел, присвоить ему значение и обновить ссылки.

public void insertAtBeginning(int value) {
    Node newNode = new Node(value);
    newNode.next = head;
    head = newNode;
}

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

public void insertAtEnd(int value) {
    Node newNode = new Node(value);

    if (head == null) {
        head = newNode;
        return;
    }

    Node current = head;
    while (current.next != null) {
        current = current.next;
    }

    current.next = newNode;
}

Удаление элементов.
Чтобы удалить элемент из связанного списка, нам необходимо соответственно обновить ссылки предыдущего и следующего узлов.

public void remove(int value) {
    if (head == null) {
        return;
    }

    if (head.value == value) {
        head = head.next;
        return;
    }

    Node current = head;
    Node prev = null;

    while (current != null && current.value != value) {
        prev = current;
        current = current.next;
    }

    if (current == null) {
        return;
    }

    prev.next = current.next;
}

Поиск элемента.
Чтобы найти элемент в связанном списке, нам нужно просмотреть список и сравнить значения каждого узла.

public boolean search(int value) {
    Node current = head;

    while (current != null) {
        if (current.value == value) {
            return true;
        }
        current = current.next;
    }

    return false;
}

Обход связанного списка.
Чтобы пройти по связанному списку и распечатать его элементы, мы можем перебирать узлы и выводить их значения.

public void traverse() {
    Node current = head;

    while (current != null) {
        System.out.print(current.value + " ");
        current = current.next;
    }
}

В этой статье мы узнали, как реализовать связанный список в Java без использования Collection Framework. Создав класс Node и класс LinkedList, мы реализовали методы для вставки, удаления, поиска и перемещения элементов в связанном списке. Эта реализация обеспечивает прочную основу для понимания внутренней работы связанных списков и их применения в программировании на Java.