Эти знания будут полезны любому, кого интересует область Data Science.
#data_scientist
#data_structures
Связный список (Linked List)
Чаще всего люди учат стихотворение, запоминая одну строфу за другой. В процессе у читателя появляются ассоциации, которые вытягивают из памяти следующую строчку, пока человек не вспомнит весь стих. Это пример работы со связным списком, где каждый элемент (узел) связан со следующим, что позволяет перемещаться по структуре от одного блока к другому.
Эту конструкцию также можно сравнить с поездом: у него каждый вагон связан с двумя своими соседями. Два исключения — первый и последний вагоны, у которых по одной связи (ссылке). Если вы пройдёте поезд насквозь, вы фактически совершите путешествие по связному списку сидящих в нем пассажиров (согласно купленным билетам). В последнем вагоне выходная дверь будет закрыта — для оператора работы со списком это сигнал о достижении финального элемента.
Метод связных списков применяется при низкоуровневом управлении памятью: компьютер записывает данные в ячейки, запоминая порядок в цепочке, и обращается к нужным блокам по известному ему порядку.
Если на собеседовании на вакансию data scientist вас спросят, чем такая структура уступает массиву данных, скажите, что простые связные списки затрудняют случайный доступ к данным, равно как и их эффективное индексирование. В некоторых случаях базовые операции вроде определения последней ячейки занимают излишние ресурсы — ведь для этого нужно пройти по всей структуре.
С другой стороны, элементы связного списка можно легко добавлять и удалять без необходимости перестраивать весь объём данных. Поэтому эта структура активно используется в динамических операциях вроде отслеживания объекта, который постоянно меняет свое положение.