CODEWITHSUNDEEP
javadata-structurescollections
Vaishu13
Vaishu13

Reputation: 455

Data structure to represent many to many relationship

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.

Upvotes: 18

Views: 9051

Answers (2)

dim
dim

Reputation: 1032

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

Upvotes: 8

Dhruv Singh
Dhruv Singh

Reputation: 2243

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

Upvotes: 1

Related Questions