Область информатики и программирования включает в себя как теоретические, так и прикладные области знаний. Будучи студентом Lighthouse Labs, мы в основном изучали практическую сторону информатики и веб-разработки, уделяя особое внимание современным инструментам и технологиям, а также передовому опыту в командной среде. Однако время от времени в ходе программы мы изучали фундаментальные концепции, такие как нотация Big O и временная сложность, алгоритмы поиска, двоичные деревья и объектно-ориентированное программирование. В этой статье я рассмотрю структуру данных, называемую связным списком, объясню ее важность и обобщу ее связь с другими часто используемыми структурами данных.

Что такое структуры данных?

Структуры данных имеют решающее значение для программирования и компьютерных наук, поскольку они обеспечивают способы эффективного хранения данных и доступа к ним, а также обеспечивают структуру для отношений между частями данных и функций, которые можно применять к отдельным компонентам данных. Некоторые примеры структур данных включают массивы, стеки, очереди, кучи, деревья, графики и связанные списки. Структуры данных не следует путать с типами данных, которые уникальны для каждого языка программирования и могут рассматриваться как «встроенные» структуры данных. Например, в JavaScript есть восемь типов данных, семь из которых являются примитивными и могут содержать только одну часть данных (например, тип String или Number), а восьмой — тип Object, который может содержать наборы данных. Таким образом, JavaScript по своей сути не включает, например, стековую структуру данных, а скорее должен быть построен из других типов данных, таких как объекты или массивы.

Связанные списки в их самой простой форме представляют собой набор узлов, где каждый узел хранит как данные, так и адрес следующего узла. Таким образом, связанные списки напоминают роман «Выбери себе приключение», где на странице 1 есть история и она указывает на страницу 5, которая продолжает историю и указывает на страницу 43, которая продолжается и указывает на страницу 11, и скоро. Первый узел связанного списка называется HEAD для обозначения начального узла, а последний узел называется NULL для обозначения конечного узла.

Связанные списки важны и имеют определенные преимущества при рассмотрении распределения памяти и временной сложности. Как разработчики, работающие с современными технологиями, мы не часто задумываемся о том, сколько памяти использует веб-приложение или сколько времени требуется для загрузки (если только это не занимает невероятно много времени). Мы бы предпочли сосредоточиться на дизайне, макете или способах доступа к данным и их визуализации. Давно прошли те времена, когда программисты были более или менее вынуждены использовать такие языки программирования, как C или C++, из-за их скорости и эффективности использования памяти. Однако, если бы в программе имел значение каждый бит или байт, возможно, из-за аппаратных ограничений, программисту действительно пришлось бы принимать важные решения о том, как лучше хранить, получать доступ и обновлять данные.

Как связанные списки сравниваются с массивами?

Эффективность связанного списка лучше всего проявляется при сравнении с очень похожей структурой данных: массивом. В массиве фрагменты данных хранятся со ссылкой на их индекс — первый элемент имеет индекс 0, второй — индекс 1 и так далее. Эти значения также последовательно сохраняются в памяти (упрощение, но для описательных целей мы продолжим использовать эту модель). Конечно, во многих случаях массивы инициализируются, не зная их окончательной длины; массив может начинаться с трех элементов, а затем увеличиваться до 300 или, возможно, просто увеличиваться до пяти элементов. Это заранее не известно компьютеру и, возможно, даже программисту. Следовательно, компьютер должен выделить определенный объем памяти для использования массивом, который может вообще никогда не нуждаться в таком большом объеме памяти, таким образом занимая память, которая затем не может использоваться другими данными. Для сравнения, связанный список хранится в памяти не последовательно, а в тех слотах памяти, которые открыты для использования, если предыдущий узел может указывать на расположение следующего узла.

Так зачем использовать массив, если связанные списки более эффективны с точки зрения использования памяти? Что ж, преимущества и недостатки очевидны, если учесть временную сложность чтения и вставки данных. В массиве вам нужно знать только номер индекса, чтобы прочитать элемент. Однако чтение элемента в связанном списке зависит от размера списка, так как вы должны прочитать элемент перед тем, как получить адрес памяти для следующего. Вам может повезти, и элемент, который вы ищете, будет самым первым, но он также может быть последним в списке, и вам придется прочитать все элементы перед ним. Таким образом, временная сложность чтения элемента массива составляет O(1) постоянное время, потому что чтение не зависит от размера массива, а чтение связанного списка занимает O(n)линейное время, где n — размер списка. Для сравнения, вставка элемента в массив занимает O(n)линейное время, так как все элементы должны сместиться, чтобы вместить новый элемент. Однако вставка в связанный список занимает O(1)постоянное время, поскольку единственное, что нужно изменить, — это указать, на что указывает предыдущий элемент, и убедиться, что вставленный элемент указывает на следующий элемент. — и этот процесс занимает одинаковое количество времени независимо от длины списка. Таким образом, связанные списки лучше всего подходят там, где много вставок, обновлений или удалений данных, и не оптимальны для чтения данных. По этой причине считается, что связанные списки допускают последовательный доступ, а массивы допускают произвольный доступ. В заключение, сравнение различных структур данных и того, как они работают с данными, может позволить программисту принять наилучшее решение о том, какую структуру данных использовать. Связанный список — это один из возможных способов представления набора данных, который имеет множество преимуществ, особенно в плане эффективности использования памяти.

Ссылки: