Вивчайте Реалізація 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

Запитати АІ

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

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

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

Ми реалізуємо нашу спрощену структуру даних — а саме, 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