Нашел список в аналогичном вопросе, ранее на StackOverflow:
Хеш-таблица - используется для быстрого поиска данных - таблица символов для компиляторов, индексация базы данных, кеши, уникальное представление данных.
Trie - словарь, например, найденный в мобильном телефоне для автозаполнения и проверки орфографии.
Дерево суффиксов - быстрый полнотекстовый поиск, используемый в большинстве текстовых процессоров.
Стек - отмена \ повтор операции в текстовых процессорах, оценка выражений и синтаксический анализ, многие виртуальные машины, такие как JVM, ориентированы на стек.
Очереди - исследование транспорта и операций, в котором различные объекты хранятся и предназначены для обработки позже, т.е. очередь выполняет функцию буфера.
Приоритетные очереди - планирование процессов в ядре
Деревья - парсеры, файловая система
Основное дерево - таблица IP-маршрутизации
BSP tree - 3D компьютерная графика
Графики - Связи / отношения в социальных сетях, маршрутизация, сети связи, организация данных и т. Д.
Куча - динамическое выделение памяти в lisp
Это ответ, первоначально опубликованный RV Pradeep
Некоторые другие, менее полезные ссылки:
Приложения указаны только для некоторых структур данных
Не ориентировано на приложение, хорошее резюме и актуальное
Я в той же лодке, что и ты. Мне нужно подготовиться к техническим собеседованиям, но запоминание списка бесполезно. Если у вас есть 3-4 часа в запасе, и вы хотите совершить более глубокое погружение, я рекомендую проверить
mycodeschool
Я просмотрел Coursera и другие ресурсы, такие как блоги и учебники, но считаю, что они либо недостаточно полны, либо находятся на другом конце спектра, слишком насыщены необходимой терминологией по информатике.
Чувак в видео прочитал кучу лекций о структурах данных. Не обращайте внимания на глупые рисунки или легкий акцент. Вы должны понимать не только, какую структуру данных выбрать, но и некоторые другие моменты, которые следует учитывать, когда люди думают о структурах данных:
Я также разместил заметки на github, если вам интересно.
источник
Насколько я понимаю, структура данных - это любые данные, находящиеся в памяти любой электронной системы, которыми можно эффективно управлять. Часто это игра памяти или более быстрого доступа к данным. Что касается памяти, то при управлении данными приходится идти на компромиссы, основанные на стоимости конечного продукта для компании. Эффективное управление говорит нам, как наилучшим образом можно получить доступ к данным, исходя из основных требований конечного продукта. Это объяснение очень высокого уровня, но структуры данных - обширная тема. Большинство интервьюеров погружаются в структуры данных, которые они могут позволить себе обсуждать на собеседовании в зависимости от имеющегося у них времени, которые представляют собой связанные списки и связанные темы.
Теперь эти типы данных можно разделить на примитивные, абстрактные, составные в зависимости от способа их логического построения и доступа.
Надеюсь, это поможет вам погрузиться в жизнь.
источник
Прекрасная книга Скиенны «Руководство по проектированию алгоритмов» содержит огромный репозиторий алгоритмов и структур данных.
Для множества проблем описываются, сравниваются структуры данных и алгоритмы, а также обсуждается практическое использование. Автор также предоставляет ссылки на реализации и оригинальные исследовательские работы.
Если вы ищете лучшую структуру данных для решения вашей проблемы, удобно иметь ее у себя на столе. Это также очень полезно для подготовки к собеседованию.
Еще один отличный ресурс - Словарь структур данных и алгоритмов NIST .
источник
Еще несколько примеров практического применения структур данных
Красно-черные деревья (используются при частых вставках / удалениях и небольшом количестве поисков) - К-среднее кластеризация с использованием красно-черного дерева, базы данных, простая база данных, поиск слов в словарях, поиск в Интернете
Деревья AVL (больше поиска и меньше вставки / удаления) - Анализ данных и интеллектуальный анализ данных, а также приложения, которые включают больше поисков
Мин. Куча - алгоритмы кластеризации
источник
Любое ранжирование различных структур данных будет хотя бы частично привязано к контексту проблемы. Это помогло бы научиться анализировать производительность алгоритмов во времени и пространстве. Как правило, используется «большая нотация O», например, двоичный поиск выполняется за время O (log n), что означает, что время для поиска элемента - это журнал (в базе 2, неявно) количества элементов. Интуитивно понятно, поскольку каждый шаг отбрасывает половину оставшихся данных как несущественные, удвоение количества элементов увеличивает время на 1 шаг. (Двоичный поиск довольно хорошо масштабируется.) Производительность по пространству связана с увеличением объема памяти для больших наборов данных. Также обратите внимание, что нотация big-O игнорирует постоянные коэффициенты - для меньших наборов данных алгоритм O (n ^ 2) может быть быстрее, чем алгоритм O (n * log n), который имеет более высокий постоянный коэффициент.
Помимо времени и пространства, к другим характеристикам относятся: отсортирована ли структура данных (деревья и скиплисты отсортированы, хэш-таблицы - нет), постоянство (двоичные деревья могут повторно использовать указатели из более старых версий, в то время как хеш-таблицы изменяются на месте) и т. Д.
Хотя вам нужно изучить поведение нескольких структур данных, чтобы иметь возможность сравнивать их, один из способов понять, почему они различаются по производительности, - это внимательно изучить несколько. Я предлагаю сравнить односвязные списки, бинарные деревья поиска и списки пропуска , которые относительно просты, но имеют очень разные характеристики. Подумайте, сколько работы требуется, чтобы найти значение, добавить новое значение, найти все значения по порядку и т. Д.
Существуют различные тексты по анализу производительности алгоритмов / структур данных, которые люди рекомендуют, но что действительно имело смысл для меня, так это изучение OCaml. Работа со сложными структурами данных - сильная сторона ML, и их поведение становится намного яснее, когда вы можете избежать указателей и управления памятью, как в C. (Однако изучение OCaml только для понимания структур данных почти наверняка является долгим путем. :))
источник