Вступление
Существует множество различных типов структур данных, которые могут быть реализованы в компьютерной программе, например массивы и связанные списки. У каждого типа структуры данных есть свои сильные и слабые стороны. По этим причинам важно понимать преимущества и недостатки различных типов структур данных, когда дело касается проектирования, оптимизации и масштабирования программ.
Массивы
Начнем с определения массива. Проще говоря, массив - это, по сути, структура данных, подобная списку значений одного и того же типа данных. Еще одно свойство массивов состоит в том, что элементы массива хранятся в непрерывных ячейках памяти. Кроме того, массивы имеют фиксированный размер, который определяется при инициализации. На основании этих свойств можно ли увидеть преимущества и недостатки массивов?
Преимущества массивов
Время поиска:
Как упоминалось ранее, массивы хранят элементы в постоянных ячейках памяти. Это означает, что к любому элементу можно получить доступ, добавив смещение к базовому значению массива или местоположению первого элемента. На следующих рисунках более подробно показано, что я имею в виду.
Хотя адреса памяти на рисунке 2 кажутся разделенными на четыре, на самом деле они идут подряд. Это означает, что любой элемент в массиве может быть расположен, пока известен индекс элемента, путем добавления смещения к адресу первого элемента. Поскольку нет разницы во времени между поиском второго или последнего элемента в массиве, массивы имеют постоянное время поиска или Big O, равное единице (O (1)), что очень быстро. По сути, наилучшая возможная сложность времени выполнения - O (1).
Недостатки массивов
Потраченная впустую память:
Одним из недостатков массивов является то, что память может быть потрачена впустую. Чтобы объяснить этот момент, я опишу сценарий. Как программист, вы не всегда знаете, сколько памяти выделить. Например, вы создаете приложение, которое будет запрашивать у пользователей входные данные, которые затем будут сохранены в массиве. Поскольку вы не знаете, сколько вводов сделает пользователь, вы инициализируете массив с одним миллионом индексов, поскольку вы предполагаете, что одного миллиона вводов будет достаточно для любого пользователя. Что, если пользователь вводит в массив только сотни тысяч элементов? Тогда 90% выделенного места тратится.
Медленное время вставки / удаления:
Массивы имеют медленное время вставки и удаления. Начнем с вставки. Чтобы вставить элемент в начало или в середину массива, первым делом необходимо убедиться, что в массиве есть место для нового элемента, в противном случае необходимо изменить размер массива. Следующий шаг - освободить место для нового элемента, сдвинув каждый элемент после желаемого индекса. Точно так же для удаления требуется смещение после удаления элемента. Это означает, что время вставки для массивов составляет Big O of n (O (n)), поскольку n элементов должны быть сдвинуты. Однако вставка и удаление с конца массива - это O (1).
Связанные списки
Связанный список - это еще один подход к сбору аналогичных данных. Однако, в отличие от массива, элементы связанного списка не находятся в последовательных ячейках памяти. Связанный список состоит из узлов, которые связаны друг с другом с помощью указателей. На рисунке 3 ниже показан связанный список.
Как показано на рисунке 3, односвязный список состоит из заголовка и набора узлов. Обратите внимание, что существует много типов связанных списков, таких как односвязные и двусвязные списки, но пока мы сосредоточимся на односвязных списках. Чтобы объяснить, как работает односвязный список, я должен сначала определить указатель. Указатель - это переменная, которая содержит адрес другой переменной или структуры. На рисунке 3 заголовок - это указатель, который содержит адрес первого узла в связанном списке. Переменная head позволяет компьютеру найти первый узел в памяти и получить доступ к его данным. После того, как начальное местоположение (первый узел) обнаружено, легко выполнить итерацию по связному списку, поскольку каждый узел содержит указатель на следующий узел.
Преимущества связанного списка
Лучшее использование памяти:
С точки зрения распределения памяти связанные списки более эффективны, чем массивы. В отличие от массивов, размер связанного списка не определен заранее, что позволяет связному списку увеличиваться или уменьшаться в размере по мере выполнения программы. Это возможно, потому что для вставки или удаления из связанного списка указатели необходимо соответствующим образом обновить.
Как правило, вставка узла в связанный список требует, чтобы указатели обновлялись после инициализации нового узла. На рисунках 4-6 показано, как вставлять узлы в начало, середину или конец связанного списка.
Еще проще, чем вставка, - это удаление из связанного списка. Единственный шаг - обновить указатели. На рисунках 7-9 показан процесс удаления узлов в начале, середине или конце связанного списка.
Как показано на рисунках выше, вставка и удаление из списка ссылок довольно просты. Кроме того, структуры связанных списков предотвращают нерациональную трату памяти, поскольку узлы вставляются в список при их инициализации.
Время быстрой вставки / удаления:
Как показано на рисунке 4, вставка нового узла в начало или конец связанного списка занимает постоянное время (O (1)), поскольку единственными шагами являются инициализация нового узла и последующее обновление указателей. Точно так же, если бы был указатель хвоста (аналогичный указателю заголовка), вставка в конец связанного списка также была бы O (1). Однако вставка в середину связанного списка занимает линейное время (O (n)), поскольку требуется итерация по n элементам, чтобы добраться до правильного места перед вставкой узла. Точно так же удаление узлов в начале и конце связанного списка занимает постоянное время, в то время как удаление узла в середине связанного списка занимает линейное время.
Недостатки связанного списка
Более медленное время поиска:
Связанный список имеет более медленное время поиска, чем массивы, поскольку произвольный доступ не разрешен. В отличие от массивов, где элементы можно искать по индексу, связанный список требует итерации. Это означает, что если вы хотите получить данные о десятом узле, указатель заголовка можно использовать для перехода к первому узлу, указатель на первом узле можно использовать для перехода ко второму узлу и так далее до десятого. узел достигнут. Это означает, что чем больше узлов необходимо повторить при поиске узла, тем больше будет время поиска. Это означает, что время поиска для связанного списка равно линейному времени или Big O of n (O (n)).
Заключение
В заключение есть много разных структур данных. У каждой структуры данных есть сильные и слабые стороны, которые влияют на производительность в зависимости от задачи. Сегодня мы исследовали две структуры данных: массивы и связанные списки. Массивы допускают произвольный доступ и требуют меньше памяти на каждый элемент (не требуют места для указателей), при этом им не хватает эффективности для операций вставки / удаления и выделения памяти. Напротив, связанные списки являются динамическими и требуют более быстрой вставки / удаления. Однако связанный список имеет более медленное время поиска, а указатели требуют дополнительной памяти для каждого элемента в списке. На рисунке 10 ниже показаны сильные и слабые стороны массивов и связанных списков.
Если вы хотите узнать, как реализовать связанный список, ознакомьтесь с моим руководством по связному списку здесь.
