Сегодня я расскажу об очень важной структуре данных в компьютерных науках Linked List из моей серии статей о типах структур данных и нотации Big O. Я подробно объясню, какие преимущества и недостатки имеют связанные списки с точки зрения манипулирования данными и нотации Big O.
Прежде чем двигаться дальше, давайте кратко обсудим определение структур данных. Структура данных — это набор значений в своего рода контейнерах, который позволяет нам эффективно хранить, управлять, изменять и манипулировать данными. Существует множество различных типов структур данных, и все они могут работать, чтобы выполнить свою работу. Однако хитрость заключается в том, чтобы выбрать правильную структуру данных для конкретной задачи, чтобы ускорить работу, которая занимает меньше места или памяти, занимаемой алгоритмом для выполнения в виде функции. Различные операции создают различную временную и пространственную сложность; поэтому важно использовать различные структуры данных, чтобы в конечном итоге достичь наилучшего результата.
Связанные списки и их структура
Связанный список — это список, который связан. Хммм.. Это может плохо объяснять это. Давайте обсудим основы связанных списков.
Связанный список — это линейная структура данных, в которой каждый элемент (узел) является отдельным объектом. Другими словами, элементы не хранятся в непрерывном месте памяти. Вместо этого каждый элемент указывает на следующий. Линейная структура — это когда элементы присоединены к своим предыдущим и следующим соседям, что означает, что существует порядок и последовательность того, как они построены и пройдены. Чтобы добраться до конца списка, мы должны последовательно пройтись по каждому элементу списка. Линейная структура — это то, что делает массивы и связанные списки похожими, поэтому порядок в обоих этих случаях имеет значение.
Структура связанного списка
Каждый элемент в связанном списке содержит два элемента — данные (или значение) и ссылку на следующий элемент (также известный как узел). Первый элемент в списке называется Head, который знает только о себе (содержащиеся в нем данные) и следующем элементе. Второй элемент или узел знает только о себе и следующем узле и так далее. Последний узел указывает на нулевое или пустое значение, поскольку после него нет элемента, на который можно было бы указать. Именно из-за этой структуры связанные списки используют динамическую структуру данных для выделения памяти. Динамическая структура данных означает, что она не имеет заранее определенного размера и объема памяти. В то время как статические структуры данных нуждаются в непрерывном блоке памяти. Например, массивы являются статическими, а их память и размер заранее определены. Массивы нуждаются в том, чтобы все их ресурсы были выделены при создании структуры. Это означает, что если мы хотим добавить больше элементов в массив, нам нужно будет воссоздать другой массив с большей памятью, скопировать данные из старой памяти, а затем добавить в него новые элементы. С другой стороны, динамические структуры данных, такие как связанные списки, не имеют фиксированного объема памяти и могут легко увеличиваться в размере и объеме памяти.
Типы связанных списков
Существует три типа связанных списков: одиночные, двойные и циклические. Структура односвязного списка описана выше, при этом первый элемент (заголовок) указывает на второй, а последний элемент указывает на нулевое значение. Двусвязный список имеет две ссылки: одну на следующий узел, а другую на предыдущий узел. Двусвязные списки хороши, если мы хотим перемещаться по структуре данных как вперед, так и назад. Круговые связанные списки также хороши, когда последний узел списка указывает на первый узел (голову) списка.
источник: https://slideplayer.com/slide/1608081/
Связанные списки и Big O Nation
Как правило, связанные списки отлично подходят для добавления и удаления элементов, однако они очень медленны для поиска и доступа к элементам. Из-за линейности скорость доступа к элементу пропорциональна размеру списка, который равен Big O(n) при обходе всего списка. В этом случае массивы представляют собой отличную структуру данных и обходятся дешевле для итерации или доступа к значению индекса. С другой стороны, при добавлении нового узла или элемента в начало списка мы выполняем одну операцию, и Big O будет постоянным временем или Big O(1), аналогично удалению узла.
В конце концов, чтобы сравнить связанные списки с массивами, связанные списки медленнее при поиске, но быстрее при вставке и удалении элементов (узлов). В то время как массивы отлично подходят для произвольного доступа, итерации и обхода списка.
Ресурсы:
