2.1. Односвязный список

Автор: Мария Горденко

В этой статье вы познакомитесь с односвязным списком — одной из базовых структур данных. Эта структура лежит в основе многих других: стека, очереди и даже более сложных реализаций. Мы разберём её устройство и научимся работать с элементами списка, чтобы увидеть, почему иногда списки оказываются удобнее массивов.

Ключевые вопросы статьи

• Как устроен односвязный список и чем он отличается от массива?
• Какие операции можно выполнять со списком и какова их сложность?
• Когда стоит использовать односвязный список вместо других структур?

Элементы односвязного спискаЭлементы односвязного списка

Односвязный список (иногда «связный список») — базовая структура данных, представляющая собой соединённые узлы с однотипными данными. Каждый узел состоит из элемента и ссылки на следующий элемент (см. рисунок).

Самый первый элемент списка называют головой (head) односвязного списка, а последний — хвостом (tail). Последний элемент односвязного списка в качестве ссылки содержит null-значение.

В отличие от классического массива, где данные в памяти расположены строго последовательно, в односвязном списке, наоборот, данные расположены хаотично и связывание узлов списка происходит посредством ссылок. За счёт этой особенности в односвязный список можно добавлять произвольное число элементов, однако доступ будет осуществляться только последовательно. Произвольного доступа к элементам в односвязном списке нет.

Со списком можно производить ряд операций:

• Добавить элемент (add).

• Удалить элемент (remove).

• Найти элемент (find).

• Посчитать количество элементов по условию (count).

Операция добавления элемента (add) может быть представлена в нескольких вариантах.

• В случае добавления в начало списка ссылка нового узла будет указывать на голову списка, а голова списка должна быть перемещена на новый узел. Сложность этого варианта — .

• Если добавление идёт в конце списка, то ссылка хвоста списка должна указывать на новый узел, а после должна быть перемещена на новый узел. Сложность этого варианта — .

• Вставка промежуточного элемента предполагает, что будет найдена позиция после которой будет вставлено новое значение. Сложность этого варианта — , где n число элементов в списке.

Удаление элемента (remove) предполагает, что будет найден заданный элемент и следом он будет удалён. Нахождение узла требует прохода по односвязному списку, после чего необходимо ссылку с элемента перед удаляемым перенаправить на элемент после удаляемого. Сложность операции — , где — число элементов в списке.

Нахождение элемента (find) предполагает простой однократный проход по списку с нахождением ссылки на заданный элемент. Сложность операции — , где — число элементов в списке.

Подсчёт числа элементов по условию (count) предполагает проход по списку и сравнение всех элементов с заданным с подсчётом количества удовлетворяющих условию элементов. Сложность операции — , где — число элементов в списке.

Что дальшеЧто дальше

Теперь вы знаете, как устроен односвязный список и как с ним работать: добавлять, удалять, искать и считать элементы. Вы поняли, чем он отличается от массива и в каких случаях может быть полезен.

Далее — ещё одна важная структура данных: множество. Вы увидите, как оно позволяет хранить уникальные элементы и выполнять быстрые проверки на принадлежность.

Ключевые выводы статьи

• Односвязный список состоит из узлов, где каждый узел хранит значение и ссылку на следующий элемент.
• В отличие от массива, доступ к элементам возможен только через последовательный обход списка.
• Основные операции (добавление, удаление) могут выполняться эффективно при работе с началом списка, но поиск элемента занимает больше времени.
• Односвязный список удобен, когда важнее динамическое изменение структуры, чем быстрый доступ по индексу.