Структура данных используется для структурирования наших данных таким образом, чтобы у нас был легкий доступ к данным для управления ими. Наиболее часто используемыми структурами данных в реальном времени, а также в интервью являются массивы, связанные списки, стек и очередь, хэш-таблица, график, деревья.
В зависимости от того, какую структуру данных мы используем, сложность и гибкость нашего кода различаются.
1 – Массив:
Это для непрерывного хранения элементов одного и того же типа. Мы можем использовать массив в следующих случаях.
- Если вы знаете размер массива до определения памяти
- Если объем данных небольшой и предсказуемый, вы хотите получить доступ к элементам через индексы.
- Работает быстро при переборе всех элементов в последовательности.
- Массив занимает меньше памяти, чем связанный список.
2 - Связанный список:
В связанном списке есть ссылки между каждым узлом на следующий узел (односвязный список) и на их предыдущий узел (двухсвязный список). Мы можем использовать связанный список в следующих случаях.
- Когда нам нужно постоянное время для вставки и удаления в нашей программе.
- Где нам дается большой и непредсказуемый объем данных, т.е. когда данные динамично растут.
- Нужно вставить или удалить элемент в любой позиции (т.е. в середине) списка.
- Когда нам не нужен произвольный доступ к любым элементам списка.
Algorithm Array List --------- ----- ----
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)3 - Стек:
Стек — это структура данных по принципу «последним пришел — первым обслужен» (LIFO). Итак, мы можем использовать стек в следующих случаях.
- Оценка выражения и разбор синтаксиса.
- Необходимость функции рекурсии.
- Найдите правильный путь в лабиринте, используя поиск с возвратом.
- Управление оперативной памятью.
4 - Очередь:
Очередь — это структура данных по принципу «первым поступил — первым обслужен» (FIFO). Мы можем использовать Queue в следующих случаях.
- При необходимости вставки или удаления с обоих концов они могут использовать очередь или двустороннюю очередь.
- Используйте очередь, когда нам нужен заказ.
- Мы можем приоритизировать процесс, который будет следующим, используя очередь приоритетов, когда процесс с высоким приоритетом запускается перед задачами с низким приоритетом.
- Выполняет задачи в порядке «первым пришел – первым обслужен».
Operation Stack Queue
--------- ----- ----- Access O(N) O(N)
Insertion O(1) O(1)
Deletion O(1) O(1)
Search O(N) O(N)5 - Хэш-таблица:
Хеш-таблицы используются для реализации ассоциативного массива, структуры, которая может отображать ключи в значения. Мы можем использовать хеш-таблицу в следующих случаях.
- Все основные операции имеют постоянное время.
- Хеширование используется для более эффективного поиска в базе данных.
- Когда у нас есть большой объем данных и нам нужна быстрая операция поиска и вставки, мы можем использовать хэш-таблицу.
6 - График:
Граф — это абстрактный тип данных, предназначенный для реализации концепций графа и ориентированного графа из математики. Что мы можем использовать Graph в следующих случаях.
- Найти кратчайший путь между городами.
- Решить лабиринт игры.
- Найти оптимизированный маршрут между городами.
- Сети имеют множество применений в практической части теории графов.
7 - Двоичное дерево поиска:
Двоичное дерево поиска — это древовидная структура данных, в которой корневой узел меньше или равен левому поддереву и больше или равен правому поддереву. Что мы можем использовать бинарное дерево поиска в следующих случаях.
- когда данные нужно отсортировать.
- Поиск может быть выполнен для диапазона значений.
- Когда нам нужно упорядоченное распределение данных.
- Балансировка по высоте помогает сократить время работы.
Operation BST Hash-table
--------- ----- ---------- Access O(logN) O(N)
Insertion O(logN) O(N)
Deletion O(logN) O(N)
Search O(logN) O(N)— Если вам понравилась статья, поделитесь ею с другом, чтобы поднимать вместе…😊😊
