Data structure to represent many to many relationship

Question

If we have Student and Course entity and the relationship between them is many to many i.e a Student can take many courses and a course can be taken by many students. If we have to represent this relationship what is the best data structure through which we can represent this relationship. If we use hashmap with student as the key and list of courses that student took as the value then we need another hashmap through which we can represent course to student relationship. Are there any best ways to represent this relationship so that searching is fast.

Answer 1

I think it's appropriate to use a combination of data structures. Here is a small example:

public class ManyToManyMap<S, C> {
    private Map<S, Set<C>> firstToSecondMap = new HashMap<>();

    private Map<C, Set<S>> secondToFirstMap = new HashMap<>();

    public void put(S first, C second) {
        if (!firstToSecondMap.containsKey(first)) {
            firstToSecondMap.put(first, new HashSet<>());
        }
        firstToSecondMap.get(first).add(second);

        if (!secondToFirstMap.containsKey(second)) {
            secondToFirstMap.put(second, new HashSet<>());
        }
        secondToFirstMap.get(second).add(first);
    }

    public Set<C> getFirst(S first) {
        return firstToSecondMap.get(first);
    }

    public Set<S> getSecond(C second) {
        return secondToFirstMap.get(second);
    }

    public Set<C> removeByFirst(S first) {
        Set<C> itemsToRemove = firstToSecondMap.remove(first);
        for (C item : itemsToRemove) {
            secondToFirstMap.get(item).remove(first);
        }

        return itemsToRemove;
    }

    public Set<S> removeBySecond(C second) {
        Set<S> itemsToRemove = secondToFirstMap.remove(second);
        for (S item : itemsToRemove) {
            firstToSecondMap.get(item).remove(second);
        }

        return itemsToRemove;
    }
}

And here is an example usage:

ManyToManyMap<String, String> mmMap = new ManyToManyMap<>();

mmMap.put("Tom", "Math");
mmMap.put("Tom", "Java");
mmMap.put("Tom", "Java");
mmMap.put("Mary", "Java");

Set<String> coursesByStudent = mmMap.getFirst("Tom"); // Java, Math
Set<String> studentByCourse = mmMap.getSecond("Java"); // Tom, Mary

mmMap.removeByFirst("Tom");
studentByCourse = mmMap.getSecond("Java"); // Mary

Answer 2

A bi-directional graph can be used to implements many-to-many relationship where each node can be connected to many other nodes