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

Question

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Пожалуйста, посетите https://algs4.cs.princeton.edu/13stacks/ для точного описания и сравнения пакетов с другими структурами данных.

Answer 4

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

Сумка - это коллекция, удаление предметов из которой не поддерживается. Цель мешков - предоставить клиентам возможность собирать предметы, а затем перебирать их.

Пакет API (Java)

public class Bag<Item> implements Iterable<Item>
    Bag() // creates an empty bag
    void add(Item item)
    boolean isEmpty()
    int size()

Bag.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;
    private int n;

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    public Bag() {
        first = null;
        n = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void add(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}