Связанный список только для ограниченного использования?

Question

У меня был хороший взгляд на мои варианты STL сегодня. Тогда я подумал о чем-то.

Кажется, связанный список (std :: list) имеет ограниченное использование. А именно, это только кажется полезно, если

• Последовательный порядок элементов в моем контейнере имеет значение, и

• Мне нужно стереть или вставить элементы посередине.

То есть, если я просто хочу получить много данных и не заботиться о их порядке, мне лучше использовать std :: set (сбалансированное дерево), если я хочу поиск O (log n) или std :: unordered_map (карта хешей), если я хочу O (1) ожидаемый поиск или std :: vector (непрерывный массив) для лучшей ссылочной локализации, или std :: deque (двусторонняя очередь), если я нужно вставить спереди и сзади.

OTOH, если порядок имеет значение, мне лучше использовать std :: vector для лучшей привязки и меньших накладных расходов или std :: deque, если требуется большое изменение размера.

Итак, я что-то упустил? Или связанный список просто не так хорош? За исключением средней вставки / стирания, с какой стати кто-то захочет ее использовать?

Answer 1

Любой вид вставки / удаления - O (1). Даже std :: vector не является O (1) для добавления, он приближается к O (1), потому что в большинстве случаев это так, но иногда вам придется увеличивать этот массив.

Также очень хорошо справляется с массовой вставкой, удалением. Если у вас есть 1 миллион записей и вы хотите добавить 1 миллион записей из другого списка (concat), это O (1). Любая другая структура (при условии, что стандартные / наивные реализации) имеют как минимум O (n) (где n - количество добавленных элементов).

Answer 2

Заказ важен очень часто. Когда это так, связанные списки хороши. Если у вас растущая коллекция, у вас есть опция связанных списков, списков массивов (vector в C ++) и двусторонних очередей (deque). Используйте связанные списки, если вы хотите часто изменять (добавлять, удалять) элементы в любом месте списка. Используйте списки массивов, если важен быстрый поиск. Используйте двусторонние очереди, если вы хотите добавить материал к обоим концам структуры данных, и важен быстрый поиск. Для вопроса deque против vector: используйте vector, кроме случаев, когда вставка / удаление объектов начинается с начала, в этом случае используйте deque. См. здесь для более подробного ознакомления с этим.

Если порядок не важен, связанные списки обычно не идеальны.

Answer 3

std::list примечателен своим методом splice(), который позволяет перемещать еще один элемент из одного списка в другой за постоянное время без копирования или выделения каких-либо элементов или узлов списка.

Answer 4

Связанные списки являются неизменяемыми и рекурсивными структурами данных, тогда как массивы являются изменчивыми и обязательными (= основанными на изменениях). В функциональном программировании обычно нет массивов - вы не изменяете элементы, а превращаете списки в новые списки. Хотя связанные списки здесь даже не нуждаются в дополнительной памяти, это невозможно эффективно с массивами.

Вы можете легко создавать или декомпозировать списки, не изменяя любое значение.

double [] = []
double (head:rest) = (2 * head):(double rest)

В C ++, который является императивным языком, вы не будете часто использовать list s. Одним из примеров может быть список космических кораблей в игре, из которого вы можете легко удалить все космические корабли, которые были уничтожены со времени предыдущего кадра.

Answer 5

std :: list имеет следующие свойства:

• Последовательность
• Передняя Seuqence
• Обратная Seuqence
• Контейнер для пересылки
• Обратный контейнер

Из этих свойств std :: vector не имеет (Обратной Seuqence)
Хотя std :: set не поддерживает какие-либо свойства последовательности или (обратный контейнер)

Так что это значит?
Будет ли обратная последовательность поддерживать O (1) для rend () и rbegin () и т.д.

Для получения полной информации см .:
Каковы гарантии сложности стандартных контейнеров?

Answer 6

Связанный список является фундаментальной структурой данных. Другие структуры данных, такие как хэш-карты, могут внутренне использовать связанные списки.

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

Всякий раз, когда вам нужно что-то сохранить, выполнить итерацию и сделать что-то с кучей данных, структурой данных normal (и быстрой) для этой задачи является связанный список. Более сложные структуры данных предназначены для особых случаев, например, Set подходит, когда вам не нужны повторные значения.

Answer 7

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