Вивчайте Реалізація LinkedList у Java | Основні Структури Даних у Java

Настав час випробувати себе у виконанні дійсно складних завдань.

Ми реалізуємо нашу спрощену структуру даних — а саме, SinglyLinkedList.

Почнемо з реалізації класу Node, який зберігатиме значення та посилання на наступний Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Реалізація класу Node у SinglyLinkedList вже була продемонстрована в попередньому розділі, тому детально на цьому зупинятися не будемо.

Далі створимо клас SinglyLinkedList, у якому визначимо всю логіку для нашої структури даних:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Ми створили поле Node head, яке зберігатиме перший елемент нашої структури даних.

У звичайному LinkedList також є head і tail, які зберігають перший і останній елементи структури даних. Оскільки під час ініціалізації структура даних повинна бути порожньою, це поле встановлюється у null у конструкторі.

Наша структура даних повинна підтримувати всі операції CRUD.

Створення

Розглянемо покроково написання методу для додавання елемента в кінець списку, що відповідає операції створення (Create):

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

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

        current.next = newNode;
    }
}

Вище наведено реалізацію методу для додавання елемента в кінець списку. Розглянемо, як працює цей метод:

Створюється об'єкт класу Node — newNode, який ініціалізується через конструктор із передачею data з параметрів методу append();
Далі перевіряється, чи список порожній. Якщо так, перший елемент списку (head) замінюється на newNode шляхом переприсвоєння;
Потім додається оператор return для виходу з методу;
Якщо список не порожній, у цьому методі створюється новий об'єкт current, який представляє Node head у цьому контексті;
За допомогою циклу while проходимо по всьому списку, поки current.next не стане null, тобто поки не визначимо, що наступний елемент у списку відсутній;
Коли знаходиться останній непорожній елемент у списку, його посилання встановлюється на newNode, таким чином елемент додається до списку.

Іншими словами, мета методу append — встановити посилання останнього елемента на новий елемент. Таким чином, новий елемент додається до списку.

Читання

Переходимо далі; тепер необхідно реалізувати операцію читання.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Операція читання є досить простою. Необхідно проітерувати кожен елемент списку та вивести їх на екран. У нашому випадку також використовується змінна current, яку ініціалізуємо як Node head;
Далі встановлюємо умову для циклу while як current != null і виводимо поле data на екран;
Для ітерації по списку використовуємо зміну посилання шляхом переназначення current, що виглядає як current = current.next;;
Це виконується до тих пір, поки Node current не стане порожнім. Після цього виходимо з циклу та переходимо до наступного рядка.

До речі, подумайте, як можна замінити цей цикл while на цикл do-while. Чи можливо це взагалі?

Оновлення

Тепер перейдемо до методу оновлення, який є цікавішим у своїй реалізації:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Спочатку перевіряємо, чи знаходиться цей index у нашому списку за допомогою оператора if. Якщо ні, виводимо повідомлення "Invalid index" і завершуємо виконання методу. Це робиться для уникнення помилок;
Якщо індекс знаходиться в межах нашого списку, переходимо до знайомого алгоритму. Спочатку створюємо об'єкт класу Node з назвою current, який ініціалізуємо як head;
Замість циклу while використовуємо цикл for, який тут більш доречний, оскільки ми знаємо точну кількість ітерацій, яку потрібно виконати. Кількість ітерацій дорівнює значенню параметра index;
Наш цикл виглядає так:
for (int i = 0; i < index; i++). У цьому циклі знаходимо потрібний елемент за допомогою знайомої операції: current = current.next;
Коли знайдено потрібний елемент, присвоюємо його атрибуту data нове значення, виконуючи операцію
current.data = newData. Значення newData беремо з параметрів цього методу.

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 6

Запитати АІ

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

Свайпніть щоб показати меню

Настав час випробувати себе у виконанні дійсно складних завдань.

Ми реалізуємо нашу спрощену структуру даних — а саме, SinglyLinkedList.

Почнемо з реалізації класу Node, який зберігатиме значення та посилання на наступний Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

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

Далі створимо клас SinglyLinkedList, у якому визначимо всю логіку для нашої структури даних:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Ми створили поле Node head, яке зберігатиме перший елемент нашої структури даних.

Наша структура даних повинна підтримувати всі операції CRUD.

Створення

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

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

        current.next = newNode;
    }
}

Вище наведено реалізацію методу для додавання елемента в кінець списку. Розглянемо, як працює цей метод:

Створюється об'єкт класу Node — newNode, який ініціалізується через конструктор із передачею data з параметрів методу append();
Далі перевіряється, чи список порожній. Якщо так, перший елемент списку (head) замінюється на newNode шляхом переприсвоєння;
Потім додається оператор return для виходу з методу;
Якщо список не порожній, у цьому методі створюється новий об'єкт current, який представляє Node head у цьому контексті;
За допомогою циклу while проходимо по всьому списку, поки current.next не стане null, тобто поки не визначимо, що наступний елемент у списку відсутній;
Коли знаходиться останній непорожній елемент у списку, його посилання встановлюється на newNode, таким чином елемент додається до списку.

Читання

Переходимо далі; тепер необхідно реалізувати операцію читання.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

Операція читання є досить простою. Необхідно проітерувати кожен елемент списку та вивести їх на екран. У нашому випадку також використовується змінна current, яку ініціалізуємо як Node head;
Далі встановлюємо умову для циклу while як current != null і виводимо поле data на екран;
Для ітерації по списку використовуємо зміну посилання шляхом переназначення current, що виглядає як current = current.next;;
Це виконується до тих пір, поки Node current не стане порожнім. Після цього виходимо з циклу та переходимо до наступного рядка.

До речі, подумайте, як можна замінити цей цикл while на цикл do-while. Чи можливо це взагалі?

Оновлення

Тепер перейдемо до методу оновлення, який є цікавішим у своїй реалізації:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Спочатку перевіряємо, чи знаходиться цей index у нашому списку за допомогою оператора if. Якщо ні, виводимо повідомлення "Invalid index" і завершуємо виконання методу. Це робиться для уникнення помилок;
Якщо індекс знаходиться в межах нашого списку, переходимо до знайомого алгоритму. Спочатку створюємо об'єкт класу Node з назвою current, який ініціалізуємо як head;
Замість циклу while використовуємо цикл for, який тут більш доречний, оскільки ми знаємо точну кількість ітерацій, яку потрібно виконати. Кількість ітерацій дорівнює значенню параметра index;
Наш цикл виглядає так:
for (int i = 0; i < index; i++). У цьому циклі знаходимо потрібний елемент за допомогою знайомої операції: current = current.next;
Коли знайдено потрібний елемент, присвоюємо його атрибуту data нове значення, виконуючи операцію
current.data = newData. Значення newData беремо з параметрів цього методу.

Все було зрозуміло?

Дякуємо за ваш відгук!

Секція 1. Розділ 6