Массивы и связанные списки являются популярными структурами данных, и их довольно легко реализовать. Конечно, у обоих есть свои предостережения, и к концу статьи я надеюсь осветить большинство из них.
Во-первых, что такое массивы и связанные списки? Короче говоря, массив — это структура данных, которая непрерывно хранит данные в памяти и организована по расположению индексов. Каждый индекс соответствует элементу в массиве, и количество элементов в массиве должно быть объявлено перед компиляцией. Также важно отметить, что массивы имеют фиксированный размер, то есть у вас не может быть больше элементов, чем уже объявлено. Исключением является динамический массив, который умножает массив на два каждый раз, когда вам не хватает места.
Связанный список, с другой стороны, представляет собой структуру данных, которая хранит элементы в так называемых узлах. Эти узлы не являются смежными, и нет фиксированного размера количества узлов, которые вы можете иметь. Это делает список динамическим по своей природе. Эти узлы, кроме того, связаны друг с другом через ссылки. Посмотрим, как это работает в памяти…
Выше массив. Каждый индекс в массиве имеет определенный адрес памяти и следует за предшествующим элементом. В этом примере показан массив значений char, что означает, что каждый элемент содержит один байт памяти.
Выше приведен односвязный список. Каждый узел содержит два значения: данные и указатель на следующий узел. Указатели занимают восемь байтов в памяти, а символы — один байт. Вместе каждый узел содержит девять байтов в памяти. Это увеличивает пространственную сложность связанного списка. Связанные списки также не являются непрерывными, что означает отсутствие последовательности в том, как хранятся узлы. Первый узел мог храниться по адресу 1000, второй по 1001, а третий по 3500. Нет порядка!
Итак, теперь, когда мы знаем, как обе они работают под капотом, давайте проанализируем временную сложность каждой структуры.
Найти()
Чтобы найти или получить доступ к любому элементу в массиве, требуется постоянное время или Big O (1). Это связано с тем, что массивы представляют собой непрерывную структуру данных. Если я знаю свой базовый адрес, то для доступа к n-му элементу в массиве мне потребуется умножить n-й индекс на объем памяти (символы будут одним байтом, целые числа будут четыре байта и т. д.), а затем добавить произведение на исходный базовый адрес. Поскольку поиск элемента не зависит от количества элементов в моем массиве, мое время выполнения всегда будет постоянным.
Чтобы найти или получить доступ к элементу в связанном списке, который не является значением head, используется линейная среда выполнения или Big O (n). Поскольку значение заголовка является первым элементом в списке, мое время выполнения для доступа к нему будет постоянным. Однако, поскольку связанные списки не являются смежными, мне пришлось бы пройти весь список, чтобы найти определенный элемент. Время выполнения зависит от количества элементов в списке.
Вставить()
Время выполнения для вставки в массив обычно линейно, если только я не вставляю в конец. Вставка в конце требует от меня использования формулы, которую я описал ранее, и установки этого значения внутри индекса. Это приведет к постоянному времени выполнения. Однако, чтобы вставить что-то в начало или середину массива, мне потребовалось бы сдвинуть элементы. Это связано с тем, что массивы являются смежными, поэтому вставка элемента в третью позицию будет означать, что я сдвигаю каждый индекс справа от него на единицу. Чем больше элементов у меня есть, тем больше времени потребуется для перехода, поэтому у меня будет время выполнения Big O(n).
Время выполнения для вставки в связанный список является постоянным (если предположить, что мы уже находимся в той позиции, которую хотим вставить). Это связано с тем, что связанные списки имеют указатели на следующие, а иногда и на предыдущие узлы. Следовательно, вставка элемента требует изменения указателей, а не смещения всех элементов перед ним. Однако, если бы мы еще не были в позиции, в которую хотели вставить, то вставка была бы постоянной во времени в начале, но линейной в конце или любой n-й позиции. Хотя в связанном списке нет смещения, вставка значения в конце или n-й позиции все равно потребует от меня прохождения списка. Чем больше элементов мне нужно пройти, тем дольше мое время выполнения. Поэтому у нас будет линейное время выполнения.
Эта логика применима и к методу delete()!
И массивы, и связанные списки легко реализуются структурами данных. Однако, в зависимости от объема памяти, который вы хотите использовать, или от того, насколько быстро должен работать ваш алгоритм, связанный список или массив имеют свои сильные и слабые стороны. Итак, кто побеждает в вашей программе?
