Информатика — это все, что касается манипулирования данными полезными способами, и для этого вам нужно понять, как эти данные структурированы. Мне было довольно комфортно работать со стандартными типами структур, такими как переменные, массивы, хэши, объекты и т. д. Когда я наткнулся на связанные списки в подкасте по программированию, я захотел глубже изучить эту тему, чтобы по-настоящему понять концепцию. Ниже приведено введение в связанные списки с ресурсами для дальнейшего изучения в конце.
Линейный против. Нелинейные структуры данных
Связанные списки похожи на массивы, поэтому их полезно сравнивать. Важным различием между ними является способ их обхода или доступ к каждому элементу. Связанные списки — это то, что называется линейной структурой данных, что означает, что элементы должны проходиться последовательно. Вы не можете случайным образом получить доступ к одному из них посередине, как к массиву. Вместо этого вам нужно начать с самого начала и пройти по пути, чтобы получить доступ к каждому элементу.
Еще один хороший пример нелинейной структуры данных, с которой вы, вероятно, знакомы, — это хэш, иногда называемый словарем. При этом порядок не имеет значения, и к любому значению можно получить доступ, вызвав соответствующий ключ.
Что вообще находится в связанном списке?
Связанные списки можно просматривать последовательно, потому что каждый элемент в списке содержит две вещи: данные и ссылку на своего соседа. Каждый элемент называется узлом, а первый узел называется головным. Голова — это то, как вы узнаете, где начинается связанный список, и вместо конечного узла список заканчивается нулевым значением, как показано ниже.
Выделение памяти
Как и все в программировании и информатике, решения принимаются путем взвешивания компромиссов между двумя вариантами. Связанные списки полезны в одних случаях и неэффективны в других.
Одно из таких отличий заключается в том, что линейные структуры данных (например, массивы) требуют непрерывного распределения данных. Это означает, что все байты информации хранятся непосредственно рядом друг с другом в группе. Если массив хочет увеличиться в размере, в конечном итоге он достигнет размера, при котором он больше не сможет расти без создания новой, большей версии самого себя и копирования своих данных. По этой причине массивы являются так называемой статической структурой.
С другой стороны, связанные списки не требуют непрерывного выделения памяти. Структура удерживается вместе указателями на следующего соседа, содержащимися в каждом узле. Там, где массивы являются статическими структурами, связанные списки являются динамическими структурами данных. Связанные списки выигрывают от этой способности увеличиваться и уменьшаться в размерах в соответствии с потребностями приложения.
Недостатки
Хотя массивы требуют выделения непрерывной памяти, в целом они занимают меньше места, чем связанные списки. Это связано с тем, что каждый узел в списке содержит два элемента, данные и ссылку, по сравнению с одним элементом данных массива. Поиск элементов в связанном списке также сложнее, чем в массиве, поскольку вам нужно сначала пройти по каждому узлу.
Преимущества
Вставка и удаление быстрее со связанным списком по сравнению с массивом. И, как было сказано выше, связанные списки — это динамическая структура данных, которая может легко увеличиваться и уменьшаться. Еще одним преимуществом является то, что память сохраняется только тогда, когда необходимы ресурсы. В основном вы хотите использовать связанный список, если вы не представляете, насколько большим будет ваш список, и можете жить без доступа к случайному элементу. Выбирайте массивы, если вам известен размер, требуется произвольный доступ и важна скорость итерации.
По этой теме можно исследовать больше, чем можно охватить в этом сообщении в блоге, поэтому для дальнейшего чтения ознакомьтесь с источниками ниже. Кроме того, рассмотрите идею нотации Big O. Эта концепция связана с оценкой производительности компьютерных процессов в отношении размера набора данных. Это важно понимать, когда наборы данных становятся действительно очень большими, и вам нужно знать, как функция будет обрабатывать ввод. Спасибо за чтение!
Обновлять
У меня была возможность обсудить тему связанных списков (огромный привет Авни), и она помогла мне реализовать базовый связанный список на Ruby. Ниже приведен код, за которым следуют соответствующие тесты:
дальнейшее чтение
Что такое связанный список? [Часть 1] — Вайдехи Джоши
Что такое связанный список? [Часть 2] — Вайдехи Джоши
Когда использовать связанный список вместо массива/списка массивов? - Переполнение стека
Большая нотация O: использование нескучной математики для измерения эффективности кода
