Если вы знакомы с такими языками программирования, как Ruby или JavaScript, то, вероятно, у вас есть опыт работы с массивами. Массивы - это очень универсальные структуры данных. В Ruby есть множество встроенных методов, которые могут выполняться с массивом. Например, push, pop, shift и unshift - это все методы, которые включают добавление или удаление из массива. Несмотря на то, что массивы кажутся лучшим вариантом для хранения коллекции схожих типов данных, все же есть некоторые недостатки, которые можно решить с помощью структуры данных, называемой связным списком.

При подготовке к техническим собеседованиям в качестве разработчика важно знать различные структуры данных, такие как массивы и связанные списки, а также плюсы и минусы работы с каждой из них. Следует принять во внимание объем памяти, выделенной для каждого, а также временную сложность каждого из них. Один из способов взглянуть на скорость - использовать нотацию Big O Notation.

Большая нотация

Что такое нотация Big O? Big O - это способ описания эффективности или сложности алгоритмов.

График выше представляет диаграмму сложности Big O. Чтобы понять различия и сходства между массивами и связным списком, мы должны сначала понять Big O и некоторые из различных возможностей временной сложности. Ниже приведены три различных варианта скорости алгоритма.

  1. O (1): выполняется одновременно, независимо от размера входных данных.
  2. O (n): выполняется линейно и пропорционально размеру ввода.
  3. O (n²): производительность прямо пропорциональна квадрату размера ввода (например: вложенные итерации, циклы)

Теперь, когда мы знакомы с Big O, теперь мы можем погрузиться в сходство связанных списков с точки зрения временной сложности и распределения памяти.

Массивы

Что такое массив? Массив - это набор элементов, которые в идеале относятся к одному типу данных. При создании массива размер массива указывается во время объявления, что означает, что это фиксированный размер. Массивы также хранятся как один большой непрерывный блок памяти, начиная с нулевого индекса. Это означает, что элементы сохраняются в последовательных слотах памяти. Например, при доступе к массиву с индексом 2 мы получаем третий элемент.

Поскольку размер массива указывается во время объявления, часть массива содержит данные, а другая часть массива пуста, поэтому в ней могут храниться новые элементы, если мы захотим добавить к ней. Если массив становится слишком большим, необходимо создать новый массив, который копирует исходные данные, а затем удваивается в размере, чтобы создать больше пустого пространства для хранения будущих данных. В массиве часто выделяется память для фактических хранимых данных, а память выделяется для пустых слотов, которые могут быть заполнены в будущем.

Изображение выше представляет собой массив. При использовании массива обычно требуется получить доступ к элементу в определенной точке, удалить элементы или добавить элемент. Однако эти разные действия требуют затрат времени. Для массива доступ к элементам по указанному индексу имеет постоянное время Big O (1).

Вставка или удаление из массива может происходить в трех различных формах: вставка / удаление из существа, вставка / удаление с конца или вставка / удаление из середины. Чтобы добавить элемент в начало массива, мы должны сдвинуть каждый следующий элемент после него на более высокий индекс. Например, если бы мы хотели добавить 2 к началу вышеприведенного, чтобы теперь он находился в нулевом индексе, теперь 10 было бы первым, 9 было бы вторым и так далее. Затраченное время будет пропорционально размеру списка или Big O (n), где n - размер списка.

Добавление в конец массива намного проще с точки зрения скорости. Он включает добавление элемента к следующему наивысшему индексу массива. Это означает, что это постоянное время и Big O (1), если массив еще не заполнен. Однако, если массив заполнен, потребуется создать новый массив, а затем скопировать содержимое оригинала в новый массив, который будет O (n). Третий случай вставки - это добавление к позиции между началом и концом массива, которая будет Big O (n). Такая же временная сложность верна и для удаления из массива.

Связанные списки

Что такое связанный список? Связанный список состоит из узлов, каждый из которых содержит данные и ссылку на следующий узел в списке. В отличие от массива данные не хранятся в одном непрерывном блоке памяти и не имеют фиксированного размера. Вместо этого он состоит из нескольких блоков памяти по разным адресам. Это означает, что размер является переменным, поскольку элементы выделяют память во время выполнения. Мы можем создавать и освобождать узлы, когда мы хотим или когда нам нужно, не беспокоясь о памяти. Чтобы получить доступ к любому узлу или элементу списка, нам нужен адрес головного узла, а затем необходимо пройти весь список, чтобы добраться до нужного элемента. В отличие от массива здесь нет зарезервированной или неиспользуемой памяти. Однако дополнительная память используется для хранения адресов следующего узла. Указатель адреса последнего узла будет неопределенным или нулевым, поскольку он является последним узлом цепочки и не будет иметь ничего, что идет после него.

При доступе к элементам связанного списка скорость пропорциональна размеру списка с Big O (n). Поскольку мы должны пройти весь список, чтобы добраться до нужного элемента, это более затратно по сравнению с доступом к элементам массива.

При вставке узла в начало списка необходимо только создать новый узел с адресом, указывающим на старую голову. Время, необходимое для этого, не зависит от размера списка. Это означает, что это будет постоянное время или Big O (1). Вставка элемента в конец списка включает обход всего списка, затем создание нового узла и корректировку адреса предыдущего узла для следующего узла. Затраченное время будет пропорционально размеру списка и Big O (n). Когда мы вставляем узел в позицию между началом и концом связанного списка, нам придется пройти по списку до определенной точки, а затем настроить указатели с помощью Big O (n). Такая же временная сложность также актуальна для удаления узлов из связанного списка.

Сравнение массивов и связанных списков

График, показанный выше, представляет различную временную сложность выполнения различных действий с массивами и связанными списками. Не обязательно лучше использовать одну структуру данных вместо другой. Однако вы должны учитывать, какие действия вы будете с ними выполнять.