Проектирование связанного списка

Привет, друзья. Теперь мы с вами закрепим теорию, которую узучили ранее и реализуем связанный список с нуля.

Сложность: 🟡 Средняя

ℹ️ Описание

Разработайте свою реализацию связанного списка. Вы можете использовать одно- или двусвязный список.

Узел в односвязном списке должен иметь два атрибута: val и next.

val — значение текущего узла
next — указатель/ссылка на следующий узел

Если вы хотите использовать двусвязный список, вам понадобится еще один атрибут prev, чтобы указать на предыдущий узел в связанном списке.
Учтите, что отсчет порядка узлов в связанном списке начинается с нуля.

Реализуйте класс MyLinkedList:

— MyLinkedList() инициализирует объект MyLinkedList.
— int get(int index) метод позволяет получить значение узла в списке по его индексу. Если индекс неверный, метод должен возвращать -1.
— void addAtHead(int val) метод позволяет добавлять узел со значением val в начало списка.
— void addAtTail(int val) метод позволяет добавлять узел со значением val в конец списка.
— void addAtIndex(int index, int val) метод позволяет добавлять узел со значением val на место элемента с индексом index. Если индекс равен длине связанного списка, узел будет добавлен в его конец. Если индекс больше длины списка, то его добавлять не нужно.
— void deleteAtIndex(int index) метод позволяет удалить элемент под индексом index из списка.

⚠️ Ограничения

— Значения каждого элемента списка находятся в диапазоне от 0 до 1000
— В списке может быть от 0 до 1000 элементов

1️⃣ Пример

// псевдокод
myLinkedList = MyLinkedList();
myLinkedList.addAtHead(1);        // [1]
myLinkedList.addAtTail(3);        // [1, 3]
myLinkedList.addAtIndex(1, 2);    // [1, 2, 3]
myLinkedList.get(1);              // 2
myLinkedList.deleteAtIndex(1);    // [1, 3]
myLinkedList.get(1);              // 3

✅ Реализация односвязного списка

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

Для начала опишем простой класс MyLinkedList с инициализирующим конструктором и создадим пустые методы-заглушки.

type MyLinkedListNode = {
    val: number;
    next: MyLinkedListNode | null;
}

export class MyLinkedList {
    head: MyLinkedListNode | null;
    size: number;

    constructor() {
        this.head = null;
        this.size = 0;
    }

    get(index: number): number {
        return 0
    }

    addAtIndex(index: number, val: number): void {}

    addAtHead(val: number): void {}

    addAtTail(val: number): void {}

    deleteAtIndex(index: number): void {}
}

Здесь мы сразу описали тип MyLinkedListNode для одной ноды списка и сам класс.

Во-первых, в классе мы завели переменную head, которая по умолчанию равна null. Это и есть ссылка на голову списка, то есть на его первый элемент.

Во-вторых, нельзя просто так получить размер связанного списка, так как для подсчета количества нод нужно обойти весь список от его головы до хвоста. Чтобы упростить нам жизнь и дальнейшие вычисления мы завели внутреннюю переменную size в классе, которая инициализируется нулем при создании класса и показывает размер списка. При выполнении операций добавления переменная будет увеличиваться на 1, а при удалении - уменьшаться на 1.