В этом параграфе вы познакомитесь с односвязным списком — одной из базовых структур данных. Эта структура лежит в основе многих других: стека, очереди и даже более сложных реализаций. Мы разберём её устройство и научимся работать с элементами списка, чтобы увидеть, почему иногда списки оказываются удобнее массивов.
Ключевые вопросы параграфа
- Как устроен односвязный список и чем он отличается от массива?
- Какие операции можно выполнять со списком и какова их сложность?
- Когда стоит использовать односвязный список вместо других структур?
Элементы односвязного списка
Односвязный список (иногда «связный список») — базовая структура данных, представляющая собой соединённые узлы с однотипными данными. Каждый узел состоит из элемента и ссылки на следующий элемент (см. рисунок).
Самый первый элемент списка называют головой (head) односвязного списка, а последний — хвостом (tail). Последний элемент односвязного списка в качестве ссылки содержит null-значение.
Остановитесь и подумайте:
Какие достоинства и недостатки по сравнению с обычным массивом у односвязного списка?
В отличие от классического массива, где данные в памяти расположены строго последовательно, в односвязном списке, наоборот, данные расположены хаотично и связывание узлов списка происходит посредством ссылок. За счёт этой особенности в односвязный список можно добавлять произвольное число элементов, однако доступ будет осуществляться только последовательно. Произвольного доступа к элементам в односвязном списке нет.
Со списком можно производить ряд операций:
- Добавить элемент (add).
- Удалить элемент (remove).
- Найти элемент (find).
- Посчитать количество элементов по условию (count).
Операция добавления элемента (add) может быть представлена в нескольких вариантах.
- Элемент можно добавить в начало списка, в конец списка или после определённого элемента.
- Перед добавлением элемента необходимо создать узел, положив в него заданное значение, затем связать ссылку со списком.
- В случае добавления в начало списка ссылка нового узла будет указывать на голову списка, а голова списка должна быть перемещена на новый узел.
- Если добавление идёт в конце списка, то ссылка хвоста списка должна указывать на новый узел, а после должна быть перемещена на новый узел. Сложность этих операций — .
Удаление элемента (remove) предполагает, что будет найден заданный элемент и следом он будет удалён. Нахождение узла требует прохода по односвязному списку, после чего необходимо ссылку с элемента перед удаляемым перенаправить на элемент после удаляемого. Сложность операции — , где — число элементов в списке.
Нахождение элемента (find) предполагает простой однократный проход по списку с нахождением ссылки на заданный элемент. Сложность операции — , где — число элементов в списке.
Подсчёт числа элементов по условию (count) предполагает проход по списку и сравнение всех элементов с заданным с подсчётом количества удовлетворяющих условию элементов. Сложность операции — , где — число элементов в списке.
Что дальше
Теперь вы знаете, как устроен односвязный список и как с ним работать: добавлять, удалять, искать и считать элементы. Вы поняли, чем он отличается от массива и в каких случаях может быть полезен.
Далее — ещё одна важная структура данных: множество. Вы увидите, как оно позволяет хранить уникальные элементы и выполнять быстрые проверки на принадлежность.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Односвязный список состоит из узлов, где каждый узел хранит значение и ссылку на следующий элемент.
- В отличие от массива, доступ к элементам возможен только через последовательный обход списка.
- Основные операции (добавление, удаление) могут выполняться эффективно при работе с началом списка, но поиск элемента занимает больше времени.
- Односвязный список удобен, когда важнее динамическое изменение структуры, чем быстрый доступ по индексу.