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

Средняя

medium , linked list

17 September 2024

Описание задачи #

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

Узел в односвязном списке должен иметь два атрибута: 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 элементов

Примеры #

// псевдокод
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 с инициализирующим конструктором и создадим пустые методы-заглушки. Дальнейший пример написан на TypeScript. В конце главы также есть пример на GO.

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.

Получение элемента из списка #

Метод предназначен для получения значения узла по указанному индексу.

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, возвращается -1, так как такой индекс недопустим.

Далее необходимо пройти по списку от его головы и найти элемент с нужным индексом. Для этого мы запускаем цикл, который выполняется до тех пор, пока i < index. Инициализируем переменную curr, которая изначально равна head то есть ссылке на первый элемент списка. Далее на каждой итерации цикла в переменную curr записывается ссылка на следующий элемент в списке через curr.next.

Если удалось найти нужный элемент в списке, то возвращаем его значение в качестве ответа, иначе возвращаем -1.

Добавление элемента в список по индексу #

В первую очередь нужно проверить корректность индекса. Если он меньше 0 или больше или равен размеру списка size, то выходим из функции и не выполняем вставку.

Следующим шагом увеличиваем внутреннюю переменную size на единицу, так происходит добавление элемента.

Если индекс равен 0, то происходит вставка в начало списка. Это означает, что нам достаточно создать новый элемент, указать в его next ссылку на текущий head списка и заменить текущий head новым элементом, после чего выйти из функции.

Если же индекс не равен 0, то нам нужно добавить элемент перед тем, который находится на позиции равной index. Мы выделили отдельный внутренний метод findPrevNode. Вызвав этот метод мы получаем предшествующий переданному индексу узел prev. Если такой узел существует, то нам достаточно в next нового элемента добавить ссылку из prev.next, а в prev.next положить ссылку на новый элемент. Таким образом новый элемент встраивается в цепочку узлов списка на заданную позицию.

Добавление элемента в начало списка #

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в начало. Для этого просто вызовем метод с нулевым индексом this.addAtIndex(0, val)

Добавление элемента в конец списка #

Так как у нас уже есть универсальный метод для вставки элементов по индексу, мы можем им воспользоваться для вставки в конец. Для этого просто вызовем метод с индексом равным длине списка this.addAtIndex(this.size, val)

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

В первую очередь нужно проверить корректность индекса. Если индекс меньше 0 или больше или равен размеру списка, метод завершает работу, так как такой индекс некорректен.

Далее необходимо уменьшить значение переменной size на единицу, так как происходит удаление.

Если индекс равен нулю, значит происходит удаление первого элемента. В этом случае достаточно изменить head списка на head.next.

Если же индекс не равен нулю, то нужно сначала найти элемент, который находится перед удаляемым. Затем нужно проставить ссылку с предыдущего на следующий элемент prev.next = prev.next.next.

Реализация #

package design_linked_list

type OneWayLinkedListNode struct {
	Val  int
	Next *OneWayLinkedListNode
}

type OneWayLinkedList struct {
	head *OneWayLinkedListNode
	size int
}

func NewOneWayLinkedList() OneWayLinkedList {
	return OneWayLinkedList{
		size: 0,
	}
}

func (l *OneWayLinkedList) Get(index int) int {
	if index >= l.size || index < 0 {
		return -1
	}

	curr := l.head
	for i := 1; i <= index; i++ {
		curr = curr.Next
	}

	return curr.Val
}

func (l *OneWayLinkedList) findPrevNode(index int) *OneWayLinkedListNode {
	curr := l.head

	for i := 0; i < index-1; i++ {
		if curr != nil {
			curr = curr.Next
		}
	}

	return curr
}

func (l *OneWayLinkedList) AddAtHead(val int) {
	l.AddAtIndex(0, val)
}

func (l *OneWayLinkedList) AddAtTail(val int) {
	l.AddAtIndex(l.size, val)
}

func (l *OneWayLinkedList) AddAtIndex(index int, val int) {
	if index > l.size || index < 0 {
		return
	}

	l.size++

	// Если нужно добавить элемент в голову
	if index == 0 {
		l.head = &OneWayLinkedListNode{
			Val:  val,
			Next: l.head,
		}
		return
	}

	prev := l.findPrevNode(index)

	// Создаем новый узел и обновляем связи
	prev.Next = &OneWayLinkedListNode{
		Val:  val,
		Next: prev.Next,
	}
}

func (l *OneWayLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index > l.size-1 {
		return
	}

	l.size--

	if index == 0 {
		l.head = l.head.Next
		return
	}

	prev := l.findPrevNode(index)

	prev.Next = prev.Next.Next
}

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

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

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

    private findPrevNode(index: number): MyLinkedListNode | null {
        let curr = this.head;
        for (let i = 0; i < index - 1; i++) {
            if (curr) {
                curr = curr.next;
            }
        }

        return curr
    }

    get(index: number): number {
        if (index >= this.size || index < 0) {
            return -1;
        }

        let curr = this.head;
        for (let i = 0; i < index; i++) {
            if (curr) {
                curr = curr.next;
            }
        }

        return curr ? curr.val : -1;
    }

    addAtHead(val: number): void {
        this.addAtIndex(0, val);
    }

    addAtTail(val: number): void {
        this.addAtIndex(this.size, val);
    }

    addAtIndex(index: number, val: number): void {
        if (index > this.size || index < 0) {
            return;
        }

        this.size++;

        if (index === 0) {
            this.head = { val, next: this.head };
            return;
        }

        const prev = this.findPrevNode(index)

        if (prev) {
            prev.next = { val, next: prev.next };
        }
    }

    deleteAtIndex(index: number): void {
        if (index < 0 || index >= this.size) {
            return;
        }

        this.size--;

        if (index === 0 && this.head) {
            this.head = this.head.next;
            return;
        }

        const prev = this.findPrevNode(index)

        if (prev && prev.next) {
            prev.next = prev.next.next;
        }
    }
}

Оценка сложности #

По времени

Так как мы разрабатываем структуру данных, оценивать нужно каждый ее метод.

get имеет сложность O(n) так как для поиска нужного узла необходимо перебирать весь список.
addAtIndex имеет сложность O(n) так как для поиска узла, перед которым нужно делать вставку, необходимо перебирать весь список.
addAtTail имеет сложность O(n) аналогично методу addAtIndex.
addAtHead имеет сложность O(1) так как не нужно перебирать весь список.
deleteAtIndex имеет сложность O(n) так как для поиска нужного узла необходимо перебирать весь список. Только удаление первого элемента будет работать за константное время O(1).

По памяти

O(1) — для всех операций.

Оригинал задачи на Leetcode

Algorithmics