Первый взгляд на структуры данных
Представьте, что вам нужно обыскать склад, чтобы найти важный лист бумаги, скажем, ваш W-2, а на складе царит полный беспорядок… примерно как на картинке ниже.
Как вы думаете, сколько времени вам понадобится, чтобы найти W-2? Да, наверное, довольно долго. Сколько времени это заняло бы, если бы вам также нужно было найти 10 других документов? Наверное, слишком долго, да?
Вот как выглядела бы память компьютера без структур данных, и просить его извлечь что-либо из его памяти, скорее всего, было бы пустой тратой времени.
Итак, что такое структура данных? Структура данных — это способ хранения и упорядочивания данных в памяти компьютера, чтобы к ним можно было эффективно обращаться и обновлять. При наличии надлежащих структур данных компьютер может хранить, обновлять и извлекать данные почти мгновенно.
Теперь, когда у вас есть общее представление о том, что такое структура данных, давайте рассмотрим ту, которую вы, вероятно, использовали, если занимались программированием. Эта структура данных является структурой данных массива.
Массив — это структура данных, которая может хранить в себе множество элементов данных одного типа. Давайте создадим массив очень быстро, чтобы мы могли видеть, о чем мы говорим.
В приведенном выше коде мы создаем массив строк. Затем мы выводим массив в консоль, однако, как видите, то, что мы получаем в консоли, не совпадает с тем, что мы помещаем в массив.
Почему это? Это связано с тем, что структуры данных хранят данные, а язык, на котором компьютер хранит эти данные, состоит из единиц и нулей. Что нужно сделать выше, так это данные, возвращенные с компьютера, должны быть превращены обратно в информацию, которую мы можем использовать. Следует отметить, что данные и информация — это не одно и то же.
Данные — это последовательность символов и битов, которые хранятся и обрабатываются компьютером. Информация — это данные, которые были обработаны таким образом, чтобы они имели для нас значение. В приведенном ниже коде мы теперь выводим информацию на терминал.
Теперь давайте создадим другой массив… скажем, массив целых чисел.
В этом коде мы создаем массив целых чисел длиной 5, а затем используем цикл for для заполнения массива числами от 0 до 4. Теперь давайте попробуем представить этот массив в памяти компьютера.
В этом примере наш массив начинается с ячейки памяти 2000 и заканчивается ячейкой памяти 2004. Теперь давайте попробуем добавить в этот массив число 5 после числа 4.
Как вы думаете, как мы будем хранить 5 в памяти выше? Вы можете подумать, что мы можем просто сохранить 5 в следующем месте, ячейке памяти 2005. Но это не сработает из-за того, как работает память.
Когда мы инициализировали наш массив длиной 5, наш компьютер выделил эти 5 пробелов с 2000 по 2004 год, чтобы мы могли использовать их для нашего массива. Это означает, что места до и после нашего массива в памяти уже могут использоваться для хранения других данных в памяти компьютера.
Так как насчет того, чтобы просто сохранить 5 в следующем открытом месте? Это происходит по двум причинам... 1) чтобы быть массивом, данные внутри него должны быть непрерывными и 2) было бы невозможно извлечь этот элемент из памяти компьютера, потому что, когда вы ищете элемент в массиве, компьютер будет искать только в тех 5 местах, которые он выделил для массива, ячейка памяти 2000–2004.
Если мы не можем добавить элемент до или после массива или в следующем открытом месте, то как нам добавить больше элементов в наш массив?
Что нам нужно сделать, так это создать еще один массив большей длины, скажем, мы удвоим длину массива. Затем вам нужно скопировать все из исходного массива в этот новый массив, а затем добавить новый элемент.
В заключение, структуры данных — это способы, которыми компьютеры хранят, обрабатывают, извлекают и организуют данные в своей памяти. Структура данных массива используется для хранения нескольких данных одного типа.
