Пример на классах

Задача - Создание связного списка

Реализуйте класс LinkedList с методами:

• addLast(data): Добавляет новый элемент в конец списка.
• printList(): Выводит на консоль все элементы списка.

Реализация каждого узла - класс NodeOne

class NodeOne {
    #data; // Приватное свойство для хранения данных узла
    #next; // Приватное свойство для хранения ссылки на следующий узел

    constructor(data, next = null) {
        this.#data = data; // Инициализация данных узла
        this.#next = next; // Инициализация ссылки на следующий узел, по умолчанию null
    }

    getData() {
        return this.#data; // Возвращает данные узла
    }

    setNext(next) {
        this.#next = next; // Устанавливает следующий узел
    }

    getNext() {
        return this.#next; // Возвращает следующий узел
    }

}

Реализация самого списка - класс LinkedListOne

class LinkedListOne {
    #head; // Приватное свойство для хранения головного узла списка
    #tail; // Приватное свойство для хранения хвостового узла списка
    #size; // Приватное свойство для хранения размера списка

    constructor() {
        this.#head = null; // Инициализация головного узла как null
        this.#tail = null; // Инициализация хвостового узла как null
        this.#size = 0; // Инициализация размера списка как 0
    }

    addLast(data) {
        const node = new NodeOne(data); // Создание нового узла с переданными данными

        if (!this.#head) { // Если головы нет, то списка нет - он пустой
            this.#head = node; // Устанавливаем новый узел как голову
            this.#tail = node; // Устанавливаем новый узел как хвост
        } else {
            this.#tail.setNext(node); // Устанавливаем новый узел как следующий для текущего хвоста
            this.#tail = node; // Обновляем хвост, устанавливая новый узел как последний элемент
        }

        this.#size++; // Увеличиваем размер списка на 1
    }

    printList() {
        let current = this.#head; // Начинаем с головного узла
        while (current) { // Пока текущий узел не равен null
            console.log(current.getData()); // Печатаем данные текущего узла
            current = current.getNext(); // Переходим к следующему узлу
        }
    }
}

const superList = new LinkedListOne(); // Создаем новый экземпляр связного списка
superList.addLast(10); // Добавляем элемент со значением 10 в конец списка
superList.addLast(20); // Добавляем элемент со значением 20 в конец списка
superList.addLast(30); // Добавляем элемент со значением 30 в конец списка
superList.addLast(40); // Добавляем элемент со значением 40 в конец списка
superList.printList(); // Печатаем все элементы списка

Удаление элемента

Расширьте класс односвязного списка из первой задачи, добавив метод remove(data), который удаляет первое вхождение элемента в списке, соответствующее предоставленным данным. Если элемент не найден, метод должен вернуть false; в противном случае true.

Решение

remove(data) {
    if (!this.#head) { // Если список пуст, возвращаем false
        return false;
    }

    if (this.#head.getData() === data) { // Если данные головного узла совпадают с искомыми
        this.#head = this.#head.getNext(); // Удаляем головной узел
        this.#size--; // Уменьшаем размер списка
        return true;
    }

    let current = this.#head; // Начинаем с головного узла
    while (current.getNext() && current.getNext().getData() !== data) {
        current = current.getNext(); // Переходим к следующему узлу
    }

    if (current.getNext() && current.getNext().getData() === data) { // Если нашли узел с искомыми данными
        current.setNext(current.getNext().getNext()); // Удаляем узел
        if (current.getNext() === null) { // Если удалили последний узел, обновляем хвост
            this.#tail = current;
        }
        this.#size--; // Уменьшаем размер списка
        return true;
    }

    return false; // Если элемент не найден, возвращаем false

}

// Пример использования
const superList = new LinkedListOne();
superList.addLast(10);
superList.addLast(20);
superList.addLast(30);
superList.addLast(40);
console.log("Before removing:");
superList.printList();
console.log("Removing 20:", superList.remove(20));
console.log("After removing:");
superList.printList();
console.log("Removing 50:", superList.remove(50)); // Элемент не найден

Метод reverse для связного списка

Добавьте метод reverse() в ваш класс односвязного списка, который изменяет порядок элементов в списке на обратный. Например, список элементов [1, 2, 3, 4] после реверсии должен выглядеть как [4, 3, 2, 1].

Решение

reverse() {
    let prev = null; // Инициализация переменной для хранения предыдущего узла
    let current = this.#head; // Начинаем с головного узла
    let next = null; // Инициализация переменной для хранения следующего узла

    while (current) { // Пока текущий узел не равен null
        next = current.getNext(); // Сохраняем следующий узел
        current.setNext(prev); // Меняем ссылку текущего узла на предыдущий узел
        prev = current; // Обновляем предыдущий узел
        current = next; // Переходим к следующему узлу
    }

    this.#tail = this.#head; // Обновляем хвостовой узел на старый головной узел
    this.#head = prev; // Обновляем головной узел на новый головной узел (бывший хвостовой узел)
}

// Пример использования
const superList = new LinkedListOne();
superList.addLast(10);
superList.addLast(20);
superList.addLast(30);
superList.addLast(40);
console.log("Before reversing:");
superList.printList();
superList.reverse();
console.log("After reversing:");
superList.printList();