Каковы преимущества использования структуры данных Bag над другими, например, Set или Linkedlist для API-интерфейса графа.

Question

Вот пример кода, который можно задать с вопросом. Этот API пытается реализовать граф с представлением списка смежности в виде массива пакетов, индексированных каждой из вершин на графике.

public class Graph{ 

private final int V;   //no. of vertices 
private Bag<Integer>[] adj; // A bag for each vertex to store all adjacent vertices 
. 
. 
. 
} 

Есть ли какие-либо преимущества использования Сумки здесь по связанным спискам или набору. Я знаю, что сумки неупорядочены, но зачем идти с неупорядоченным списком, когда они не спасают нас от времени или пространства?

Answer 1

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

A Набор позволяет использовать только уникальные элементы, поэтому, если вам нужно хранить дубликаты, вам нужна сумка. TreeSet или HashSet в библиотеке Java Collections даст нам O (log n) или O (1) поиск соответственно.

В целом интерфейсы Set или Bag будут более подходящими, когда вам часто приходится выполнять операции поиска или удаления. Если вам просто нужно добавить в конец коллекции и перебрать ее, то не будет большой разницы.

Answer 2

Каждая структура данных может быть использована при различных обстоятельствах:

Set (в частности HashSet) может быть список уникальных неупорядоченных элементов. С другой стороны, Bags являются мультимножествами (неупорядоченные коллекции, которые могут содержать повторяющиеся элементы).

Что касается LinkedList, они обеспечивают более легкую манипуляцию ссылками, то есть добавление элементов в разные места, намного проще (постоянное время).