Самая страшная часть программирования стала проще
Структуры данных - самая устрашающая часть программирования. Но они не должны быть такими уж плохими!
В этом руководстве мы собираемся изучить, что такое структуры данных, самые популярные структуры данных, и все время будем использовать простые для понимания примеры.
Что такое структура данных?
Структура данных - это способ организации данных.
Компьютеры должны хранить много данных, чтобы все работало. Только подумайте о том, сколько данных YouTube нужно хранить, обрабатывать и регулярно возвращать пользователям!
Чтобы YouTube работал бесперебойно, им необходимо организовать и отображать данные наиболее эффективным образом.
Есть десятки различных способов отображения данных. У каждого свои плюсы и минусы.
Представим, что у вас есть список всех ваших друзей на листе бумаги. Вы сортируете по алфавиту.
Было бы очень легко просмотреть и найти человека, которого вы ищете. Но было бы кошмаром добавить кого-то нового в список.
У каждой структуры данных есть свои варианты использования. И цель состоит в том, чтобы знать, когда и почему использовать одну структуру данных вместо другой.
Святой Грааль структур данных
Массив - самая распространенная структура данных в информатике. Он хранит данные линейно.
Когда вы создаете массив, каждому элементу присваивается номер, начиная с 0. Этот номер будет использоваться для доступа к этой информации позже.
Мы называем это число индексом.
Есть 2 разных типа массивов. Статичный и динамичный.
Статические массивы не изменяются во время выполнения. Когда вы их создаете, должно быть что-то, что всегда остается неизменным.
Представьте, что у вас есть сайт о вашей личной жизни. Вы бы использовали статический массив для хранения списка всех ваших бывших подруг. Давай будем настоящими. Мы оба знаем, что массив не будет обновляться в ближайшее время.
После определения статического массива его размер останется прежним. И вам нужно будет воссоздать программу, чтобы внести изменения.
С другой стороны, что, если вы хотите создать массив, в котором хранятся все заголовки моих статей, которые вы прочитали? Это все время будет меняться, не так ли?
В этом случае вы должны использовать динамический массив. Эти массивы изменяются всякий раз, когда появляется или исчезает новая информация.
Размер может изменяться, чтобы соответствовать всем данным.
Массивы - это круто. Вы сразу получаете доступ ко всем элементам внутри. Единственное, что вам нужно сделать, это использовать индекс для доступа к тому, что вы хотите.
Связанный список
Связанный список - еще одна важная структура данных, которую программисты постоянно используют.
Они организованы линейно. Очень похоже на массивы. Но разница в том, что в связанных списках используются узлы.
Узел - это тип данных, содержащий данные. А также хранит ссылку на узлы рядом с собой.
Связанные списки используют узлы линейно. Это означает, что каждый узел хранит свои собственные данные и ссылку на узел перед ним.
Представьте себе линию конги.
Обратите внимание, как все держат человека перед собой. Так работает связанный список. Удерживать кого-то здесь - это как узел, ссылающийся на узел перед ним.
Это то, что мы назвали бы односвязным списком. Один, в котором каждый узел содержит только одну ссылку на один узел рядом с ним.
Но есть и двусвязные списки. Это было бы немного иначе.
Каждый узел будет содержать ссылку на 2 разных узла.
Это было бы больше похоже на людей, держащихся за руки в кругу. Каждый будет держаться за руки с двумя разными людьми.
Стек
Структура данных стека хранит данные в стеке. Я знаю, это потрясающе.
Стек позволяет размещать данные вверху. Но первые данные, которые вы получите, - это данные вверху. Если вам нужно что-то еще ниже, вам нужно сначала вывести другие данные.
Представьте себе стопку компакт-дисков Тейлор Свифт. Самый первый компакт-диск, который вы купили у нее, будет внизу стопки компакт-дисков. А самый свежий диск (лучше Folklore) был бы наверху.
Каждый раз, когда вы ходили послушать Тейлор Свифт, вам приходилось вынимать компакт-диск Folklore, если вы хотели перейти к ее другому альбому, Red.
Стек демонстрирует важный принцип структур данных.
LIFO - последний пришел - первым ушел
Стек - полная противоположность нашей следующей структуре данных.
Очередь
Если стек поступает последним - первым выходит, очередь переворачивает его с ног на голову.
FIFO - первым пришел - первым ушел
Если вы хотите удалить что-то из очереди, вы должны удалить самый старый элемент.
Представьте себе работающую техподдержку плохой компании. Сотни клиентов всегда будут звонить с вопросами или просто жаловаться.
Вы бы поставили в приоритет людей, которые ждут дольше всех. Первый, кто позвонит, получит поддержку раньше второго.
Надеюсь, вы узнали все необходимое о структурах данных для начала!
Сначала они пугающие. Но нам просто нужно их разбить и максимально упростить.
Следуйте за мной, чтобы узнать о более простых подобных поломках!