Динамический массив (с возможностью расширения) – как работает изменение размера.

В этом видео я пошагово объясню, что такое динамические массивы и как изменять их размер. Динамические массивы, также известные как расширяемые массивы, являются одной из важнейших структур данных в информатике. Если вы когда-либо использовали ArrayList в Java, вектор в C++ или список в Python, вы уже использовали динамический массив, даже не подозревая об этом. В этом уроке мы создадим динамический массив (также называемый расширяемым массивом) с нуля, чтобы вы полностью поняли, как работает изменение размера внутри. Обычный массив имеет фиксированный размер. После создания его емкость не может измениться. Это основное ограничение традиционного массива. Если массив заполняется и вам нужно больше места, вы не можете просто «увеличить» его. Вместо этого вы должны создать новый массив и скопировать в него элементы. Динамический массив решает эту проблему, автоматически изменяя размер, когда в нем заканчивается место. Именно поэтому динамические массивы также называются расширяемыми массивами или массивами с изменяемым размером. Они расширяются по мере необходимости. В этом видео мы подробно рассмотрим полную реализацию динамического массива. Вы увидите, как именно работает изменение размера, как изменяется емкость, чем размер отличается от емкости и почему изменение размера не происходит за постоянное время. Мы обсудим, как растет динамический массив, почему в большинстве реализаций емкость удваивается и как копирование элементов влияет на производительность. Понимание динамических массивов на этом уровне имеет решающее значение, если вы серьезно занимаетесь структурами данных и алгоритмами. Мы начнем с обзора того, что такое массив и как работает доступ по индексу. Одним из самых больших преимуществ динамического массива является доступ по индексу за постоянное время. Доступ к элементу по индексу занимает O(1), что делает динамические массивы чрезвычайно мощными для быстрого извлечения и обновления данных. Именно поэтому динамические массивы широко используются в алгоритмах, соревновательном программировании и на технических собеседованиях. Далее мы рассмотрим вставку. При вставке в неполный динамический массив операция проста. Однако, когда динамический массив заполнен, необходимо изменить его размер. Изменение размера динамического массива включает в себя создание нового массива с большей емкостью, копирование всех существующих элементов в новый массив, а затем обновление ссылки таким образом, чтобы старый массив больше не использовался. Именно этот процесс изменения размера делает динамические массивы мощными, но также приводит к снижению производительности. Ключевым понятием, которое мы рассмотрим в этом руководстве по динамическим массивам, является разница между размером и емкостью. Размер динамического массива представляет собой количество элементов, хранящихся в данный момент. Емкость представляет собой общее количество доступных слотов. Многие студенты путают эти два понятия, но понимание разницы между размером и емкостью имеет важное значение при реализации динамического массива. Когда размер достигает емкости, происходит изменение размера. Мы также рассмотрим удаление в реализации динамического массива. Как и динамический массив, он может увеличиваться в размерах, так и уменьшаться. Когда слишком много слотов остаются неиспользованными, динамический массив может уменьшить свою емкость для экономии памяти. Такое поведение при изменении размера предотвращает нерациональное использование пространства и повышает эффективность использования памяти. В этом видео я объясню, когда происходит уменьшение размера и почему во многих реализациях происходит уменьшение размера, когда динамический массив заполняется менее чем наполовину. Еще одна важная тема, которую мы обсудим, — это временная сложность. Динамические массивы обеспечивают доступ по индексу за O(1) и обновление по индексу за O(1). Однако вставка и удаление могут занимать время O(n) из-за сдвига элементов. Кроме того, изменение размера требует копирования всех элементов, что также занимает O(n). Понимая эти компромиссы, вы поймете, когда следует использовать динамический массив, а когда может быть более подходящей другая структура данных, например, связанный список. Этот учебник по реализации динамического массива предназначен для студентов, изучающих структуры данных и алгоритмы. Независимо от того, готовитесь ли вы к собеседованиям по программированию, изучаете Java или изучаете основы информатики, освоение динамического массива имеет важное значение. Многие вопросы на собеседованиях косвенно проверяют ваше понимание того, как работает изменение размера. Если вы не понимаете, как динамический массив изменяет свой размер внутри, у вас могут возникнуть трудности с более глубокими алгоритмическими концептами. Мы будем реализовывать динамический массив шаг за шагом. Вы увидите код для insertAt, insertAtBeginning, insertAtEnd, deleteAt, get, set и indexOf. Вы также увидите, как работает изменение размера внутри во время вставки. Вместо тог...