Если вы похожи на меня, недавнего выпускника учебного лагеря по веб-разработке без опыта программирования, вы можете почувствовать, что вам не хватает определенных основ CS, которые могут возникнуть на техническом собеседовании. Быстрый поиск в Google «лучших материалов для подготовки к собеседованию» неизбежно приведет вас к списку тем, начиная от хэш-таблиц и заканчивая нотацией BigO, и, вероятно, оставит у вас ощущение, что вы только коснулись поверхности того, что нужно, чтобы быть наемный разработчик. В этой статье мы рассмотрим одну из (многих) тем, которые могут возникнуть: структура данных связанного списка. Предполагается, что у читателя есть некоторые базовые знания основ программирования, но вам не нужно быть экспертом, чтобы получить что-то из этого. Я покажу вам, что такое связанные списки и что они делают, с точки зрения одного начинающего веб-разработчика другому, с целью дать вам достаточное понимание того, что, если эта тема все же возникнет на вашем следующем TI, вы может чувствовать себя достаточно уверенно, обсуждая это.

Так что же такое связанные списки?

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

  • Обязательное определение Википедии

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

Давайте разобьем это определение из Википедии на более простые термины:

связный список – это линейный набор элементов данных, порядок которых не определяется их физическим размещением в памяти.

Это начинает иметь больше смысла, если вы рассматриваете это в контексте того, как массивы хранятся в памяти компьютера:

Массивы хранятся непрерывно, что означает, что элементы, которые они содержат, хранятся рядом друг с другом внутри массива, при этом этот массив фиксируется на месте в памяти компьютера. Это то, что позволяет нам получить доступ к любому элементу массива по его индексу. Используя изображение выше, если бы мы хотели получить доступ к элементу со значением 68, мы бы сделали что-то вроде console.log(array[5])используя индекс элемента 5. Это одно из преимуществ последовательно хранимых структур данных: доступ к любому элементу, содержащемуся в нем, произвольный и быстро.

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

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

O.K., теперь это начинает иметь смысл! Давайте посмотрим на следующую часть:

Для чего они используются?

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

Здесь можно сделать два ключевых вывода: во-первых, связанные списки удобны тем, что позволяют относительно легко вставлять или удалять новую ссылку. Я говорю относительный, потому что есть еще некоторый контекст от нашего дорогого друга массива; добавление и удаление элементов из массива может включать множество дорогостоящих внутренних операций, а операции требуют времени, ценного ресурса для управления в крупномасштабных проектах. Добавьте к этому, что в некоторых языках программирования, таких как C++, ожидается, что массивы будут инициализированы заданной длиной, например длиной 5 в этом примере: int MyArray[5] = {0,1,2,3,4};и вы начнете видеть, где действительно эффективны связанные списки. С помощью связанных списков мы можем просто перейти от одного узла к другому, а затем разорвать связь в нужной точке, вставить туда новый узел и перековать связь. Существует множество видеороликов, таких как это от HackerRank, в которых более подробно рассматривается этот процесс, если вы так склонны, но сейчас вам просто нужно знать, что этот процесс проще со связанными списками, чем на самом деле. обычно с массивами (и особенно в таких языках, как C++).

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

Для чего они не используются?

Недостатком связанных списков является то, что время доступа является линейным (и его трудно конвейеризировать). Более быстрый доступ, такой как произвольный доступ, невозможен. Массивы имеют лучшую локальность кеша по сравнению со связанными списками.

Теперь это относится к нотации BigO, увлекательной и сложной теме, которая иногда бывает забавной, но чаще всего вызывает мигрень, так что вот TLDR BigO: все, что делает ваш код, требует времени для выполнения, и вы можете вычислить это количество времени довольно точно с использованием BigO. Выше упоминается, что время доступа линейно. Это относится к основной слабости связанного списка: вы не можете получить доступ к узлу (или элементу, или ссылке…) произвольно, как если бы вы использовали элемент в массиве, используя его индекс. Вместо этого вы должны начать с первого узла (называемого головным) и последовательно проходить через каждый узел и ссылку, пока не доберетесь до нужного фрагмента данных. Теперь, в небольшом связанном списке, это не большая проблема, и это не будет стоить вам много сладкого, сочного времени. Но представьте, если бы у вас был связанный список, содержащий примерно 10 000 узлов, и вы хотели бы получить доступ к 9 826-му узлу; вам нужно начать с головы и пройти (также известное как «переход») 9825 узлов, пока не достигнете желаемых данных. В BigO это называется задачей линейного масштабирования, обозначаемой символом O(n). Кроме того, более сложные версии связанных списков занимают больше места в памяти из-за множества указателей. Это может заставить вас спросить:

Зачем мне их использовать?

Это вопрос с подвохом, потому что вы, вероятно, используете связанные списки несколько раз в день, даже не подозревая об этом. Каждый щелчок назад или вперед на вашем смартфоне или в браузере, каждое нажатие клавиш CTRL+Z или CTRL+Y на клавиатуре и другие действия на основе состояния, с которыми мы регулярно сталкиваемся при использовании таких программ, как Photoshop, Spotify или Word, часто зависят от связанных списки функционируют так, как мы ожидаем. Как программист, который в основном работает с Javascript, я имею дело со связанными списками, чтобы придать моему стеку вызовов его функциональность (включение последним пришел — первым обслужен), и его можно использовать для последовательных графиков, хэш-таблиц и других сложных тем. У них есть свои недостатки, как обсуждалось ранее, но они все еще существуют и будут существовать еще какое-то время.

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

Ресурсы: