Связный список
Связный список — интерактивный эксперимент из приложения «Структуры данных», бесплатной симуляции StudyFi Lab, которая работает прямо в браузере.
Каждый узел хранит значение и ссылку next на следующий узел; последний указывает на null, а список начинается с указателя head. Вставка в начало стоит O(1), но чтобы дойти до позиции i или найти значение, приходится идти узел за узлом — O(n). В отличие от массива ничего не сдвигается, меняются только ссылки; так устроены плейлисты, истории действий и списки свободной памяти.
Попробуй: Найди последнее значение и посчитай шаги указателя, затем вставь число в начало — это всегда один шаг.
Частые вопросы
Что показывает эксперимент «Связный список»?
Каждый узел хранит значение и ссылку next на следующий узел; последний указывает на null, а список начинается с указателя head. Вставка в начало стоит O(1), но чтобы дойти до позиции i или найти значение, приходится идти узел за узлом — O(n). В отличие от массива ничего не сдвигается, меняются только ссылки; так устроены плейлисты, истории действий и списки свободной памяти.
Как попробовать «Связный список»?
Найди последнее значение и посчитай шаги указателя, затем вставь число в начало — это всегда один шаг.
Готовишься к контрольной?
Загрузи свои конспекты, и StudyFi превратит их в карточки, тесты и подкасты.