Структуры данных и массивы
Во-первых, что такое структура данных?
Это набор значений, которые могут иметь отношения между собой и функции, применяемые к ним. Каждая структура данных хороша и специализирована для решения своей конкретной задачи, а также для быстрого хранения и поиска определенных данных.
Огромный список структур данных можно найти здесь: Все структуры данных.
Однако есть только несколько основных, которые вам действительно нужно знать и которые используются в 90% случаев. Они есть:
- Массивы
- Стеки
- Очереди
- Связанные списки
- Деревья
- Пытается
- Графики
- Хэш-таблицы
Учтите, что у каждого языка свои структуры данных, пример таблицы можно найти здесь. Но если язык, который вы используете, не содержит определенной структуры данных, не беспокойтесь, вы можете ее построить. Например, если в Javascript нет стеков — вы можете их создать.
Массивы
Массивы организуют данные последовательно. Таким образом, они сохраняются в памяти друг за другом. Массивы являются одной из наиболее часто используемых структур данных и имеют наименьший размер среди всех структур данных.
Придя из программирования Bootcamp, я знал, что такое массивы и как их использовать, но изучив основы нотации Big O, которые можно найти в моем предыдущем блоге здесь, я понял, что простые встроенные методы на самом деле имеют множество различных нотаций Big O.
Возьмите этот простой массив ниже и два встроенных метода pop() и unshift():
Каким, по-вашему, должно быть их Большое О? Раньше я никогда бы не подумал об этом, думая… ну, .pop() берет последний элемент массива, а unshift просто вставляет элемент в начало. Простой…
Однако теперь вам нужно посмотреть, КАК этот метод работает.
Почему? Что ж, pop() — это просто. Независимо от длины ввода, метод просто возвращает последний элемент. Поэтому оно постоянно.
Однако unshift добавляет элемент в массив. Но? Это просто каждый раз помещает элемент в начало, так что, конечно же, это тоже константа?
Отчасти это правильно, однако индекс массива нужно изменить. Следовательно:
Unshift должен пройтись по массиву и присвоить каждому элементу новый индекс. Как мы знаем из предыдущего блога, простая функция цикла — это O(n) или линейное время.
Это пример, который должен заставить вас задуматься о том, подходит ли другой тип структуры данных для добавления нового элемента.
Это должно дать вам базовое понимание того, почему поиск чего-то в массиве выполняется быстро O(1), а добавление чего-то в массив медленнее O(n).
Давайте воспользуемся массивом, чтобы решить простую задачу обращения строки.
Здесь мы используем метод .split(). Согласно MDN, «метод split() делит строку на упорядоченный список подстрок, помещает эти подстроки в массив и возвращает массив».
Затем мы используем метод .join(). Который создает и возвращает новую строку путем объединения всех элементов в массиве (или «подобном массиву объекта), разделенных запятыми или указанной строкой-разделителем. Если в массиве только один элемент, то этот элемент будет возвращен без использования разделителя».
Это был всего лишь базовый пример использования структуры данных массива для достижения определенного результата. Мы поместили строку в массив, что позволило нам достичь желаемого результата.
Массивы отлично подходят для быстрого поиска, доступа к тому индексу, который вы хотите найти, или добавления в конец массива или удаления элемента из конца массива, он также упорядочен в памяти. Однако он медленный для вставки и удаления и, наконец, если вы используете статический массив, то он имеет фиксированный размер.
