Связный список — Основы алгоритмов и структур данных

Прежде чем говорить о списках, давайте вспомним про массивы.
Когда нам нужно что-то перечислить, записать или создать какую-то коллекцию, мы постоянно используем массив. Но правильно ли это? Из урока Массивы в памяти компьютера мы помним, что массив - это статический кусок памяти и динамические массивы существуют уже на уровне самого языка.

Какие плюсы есть у массивов?

const myCats = ['дымка', 'барсик', 'самарик']'

Мы имеем доступ к произвольному элементу myCats[2] // 'самарик'
Массив на уровне железа можно представить как строку в таблице. Представим, что мы имеем массив из 4 кошек, который лежит в нашей памяти, в строке таблицы из 7 ячеек, но 3 последних места уже заняты. Мы добавляем элемент в массив, но рядом для него места нет. Что же произойдет? Компьютеру придется взять все элементы массива, перенести на следующую строку, где есть свободное пятое место, чтобы добавить пятый элемент в этот массив. Перенос всего массива - довольно долгая операция.

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

Но что, если в нашей программе необходимо постоянно сохранять какие-то данные, не требовать доступ к произвольному элементу нашего хранилища и раз в год читать, например, первую запись из этого хранилища? Хотелось бы придумать что-то получше массива.

На ум сразу приходит, что было бы хорошо хранить значения в произвольном месте, в любом доступном куске памяти.

Чтобы понимать, что все эти данные относятся к одному и тому же, их надо как-то связать. Для этого на рисунке сделаны стрелки, которые являются обычными ссылками.

При добавлении нового элемента мы просто проведем стрелку от последнего значения к нашему новому. Такая структура данных называется односвязным списком. Сам список состоит из узлов: в первой части узла находятся данные, а вторая часть - это ссылка на следующий узел.

Для добавления элементов в конец придется обойти весь список, чтобы найти хвост. А если потребуется знать, откуда он начинается, придётся перебрать все узлы и найти узел, на который не ссылается ни один другой узел. Чтобы упростить эту работу, в самом списке мы можем просто всегда хранить ссылку на первый элемент - head, и на последний - tail.

Сравнения скорости работы динамического массива и списка

	поиск	вставка	удаление	взятие элемента по индексу
список	O(n)	O(1)	O(1)	-
динамический массив	O(n)	O(n)	O(n)	O(1)

Итак, мы нарисовали и скоро реализуем нашу первую, простую, но важную абстрактную структуру данных.

Остались вопросы? Задайте их в разделе «Обсуждение»

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

Ошибки, сложный материал, вопросы >

Нашли опечатку или неточность?

Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.

Что-то не получается или материал кажется сложным?

Загляните в раздел «Обсуждение»:

задайте вопрос. Вы быстрее справитесь с трудностями и прокачаете навык постановки правильных вопросов, что пригодится и в учёбе, и в работе программистом;
расскажите о своих впечатлениях. Если курс слишком сложный, подробный отзыв поможет нам сделать его лучше;
изучите вопросы других учеников и ответы на них. Это база знаний, которой можно и нужно пользоваться.

Об обучении на Хекслете

Статья «Как учиться и справляться с негативными мыслями»
Статья «Ловушки обучения»
Статья «Сложные простые задачи по программированию»
Урок «Как эффективно учиться на Хекслете»
Вебинар «Как самостоятельно учиться»

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ

130

курсов

900

упражнений

2000+

часов теории

3200

тестов