Какую структуру данных вы можете использовать для динамического хранения элементов и эффективного доступа к ним?

Question

Какую структуру данных вы можете использовать для динамического хранения элементов и эффективного доступа к ним? Это вопрос интервью. Должен ли я ответить std::list (я имею в виду C ++)? или другие?

В качестве дополнительного вопроса, какова сложность поиска любого элемента в связанном списке в худшем случае?

Спасибо за все ваши мнения.

Answer 1

Этот вопрос довольно расплывчатый.Причина, по которой мы имеем несколько структур данных, заключается в том, что все они поддерживают разные шаблоны доступа более или менее эффективно, чем другие.Например:

• Связанный список является хорошим выбором, если весь доступ осуществляется с начала списка вперед.
• Динамический массив является хорошим выбором, если доступы случайные ивставка / удаление в конце.
• Стек является хорошим выбором, если доступ всегда FIFO.
• Очередь является хорошим выбором, если доступ всегда LIFO.
• Deque - хороший выбор, если доступы всегда на концах.
• Приоритетная очередь - хороший выбор, если доступы всегда к наименьшему элементу.
• Хеш-таблица хорошаесли доступ полностью случайный и упорядочение не требуется.
• Сбалансированное двоичное дерево поиска хорошо, если доступ полностью случайный и требуется упорядочение.
• Три хорошо, если элементы хранятсяявляются строками или иным образом цифровыми.
• KD-дерево хорошо, если элементы являются точками в пространстве, и вы хотите поддерживать запросы диапазона или поиск ближайшего соседа.
• Структура поиска объединения iХорошо, если вы хотите знать, как элементы связаны друг с другом.
• Дерево Ван Эмда Боаса хорошо, если значения целые, доступы случайные, и вы хотите, чтобы они были в порядке.
• Квадрат хорош, если вы хотите сохранить элементы в виде геометрической структуры и хотите получить доступ к точкам и ребрам возле определенных граней (или наоборот)
• и т. Д.

Есть множество хороших ответов на этот вопрос в зависимости от того, что вы пытаетесь сделать с данными.Этот список является лишь небольшой выборкой того, какие структуры данных существуют, и все они могут быть правильным ответом в зависимости от обстоятельств.Они также могут быть неправильным ответом 1034 * в зависимости от обстоятельств.Помните - при выборе структуры данных убедитесь, что вы знаете, какую проблему вы пытаетесь решить!

Что касается вашего второго вопроса: в худшем случае это может занять O (n) время, чтобы найти элемент в связанном списке.Это происходит либо в том случае, если искомый элемент отсутствует в связанном списке, либо в конце.В этом случае вам нужно сканировать весь связанный список по одному элементу за раз, прежде чем вы сможете решить, содержится ли соответствующий элемент в списке.

Надеюсь, это поможет!

Answer 2

Первый вопрос, я бы сказал, хэш-таблица.Помещение и получение элементов с использованием хеш-таблицы в среднем составляет O (1).Связанный список имеет худший случай сохранения в O (n) и худший случай доступа в O (n).Массив имеет худший случай хранения O (1) и худший случай доступа в O (1).Связанный список может динамически расти очень быстро, так как массив должен будет выделять новый и больший массив и копировать существующий элемент для достижения динамически растущей способности.

Для вопроса 2 сложность поиска элемента в связанном списке составляет O (n), так как в худшем случае вам придется перебирать все элементы в списке (рассмотрим случай, когда элемент отсутствует всписок).

Answer 3

Я думаю, что ответ полностью зависит от того, что вы храните и каковы шаблоны доступа:

• Какой доступ вам нужен? Случайные? Последовательная?
• Являются ли вставки / обновления частыми или нечастыми?
• Сколько элементов?
• Какого типа элементы?
• .. и т.д ..

Если бы мне задали ваш вопрос в интервью, я бы начал с того, чтобы ответить на эти уточняющие вопросы. Иногда интервьюеры задают смутные, открытые вопросы, чтобы понять, как вы думаете: узнать, можете ли вы распознать не полностью определенную проблему, и задать вопросы, чтобы получить необходимый контекст для ответа.

Answer 4

Доступ к элементам в списке не эффективен.Вы должны по умолчанию использовать вектор, это произвольный доступ.

Answer 5

Если бы я спросил это, я бы ответил так коротко и просто, как

Нет частого удаления - хэш-карта. (Все О (1))
Частое удаление - Rb tree (Everything O (logN))

Answer 6

Это зависит от модели использования:

например, для вектора быстрый доступ к случайным элементам происходит за счет добавления новых элементов,

со списком вы будете эффективны при добавлении новых элементов, тогда как произвольный доступ к элементам невозможен - вам придется пройти весь список (в худшем случае), чтобы получить доступ к нужному элементу, то есть сложности O (n). 1005 *

Информацию о сложности для различных операций с контейнерами stl можно найти здесь: http://www.cplusplus.com/reference/stl/