Односвязный список (Singly Linked List)

Односвязный список — это структура данных, которая позволяет делать последовательность элементов, где каждый элемент имеет указатель на следующий элемент в списке.

Вот пример типичной структуры узла односвязного списка.

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

type MyLinkedListNode struct {
    Val  int
    Next *MyLinkedListNode
}

У связанных списков всегда есть первый элемент списка, который называется head (голова) и последний элемент — tail (хвост). Чтобы предоставить весь список достаточно иметь ссылку на его голову, так как путем последовательного перебора узлов черерз next можно проитерироваться по всему списку.

В нашем примере ниже в качестве головного выступает элемент со значением 1. От него можно перейти по ссылке к следующему элементу со значением 2 и уже от него к хвостовому элементу со значением 3.

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

1. Вставка элемента в начало выполняется за константное время, так как для этого нужно всего лишь переписать ссылку у head на новый элемент, а в его next добавить ссылку на старый head.

2. Еще проще работает удаление первого элемента и тоже за константное время. Для удаления достаточно переписать ссылку на head ссылкой на head.next. Соответственно, это тоже работает за константное время.

3. Все остальные операции удаления, добавления и редактирования элементов в списке работают за линейное время, так как для поиска нужного элемента нужно перебрать весь список, начиная с head. В худшем случае это занимает N итераций.

4. Все операции в связном списке имеют константную сложность по памяти, так как для их выполнения достаточно оперировать ссылками на элементы.

#linked_list