Multilists
Our last example shows a more complicated use of linked lists. A university with 40,000 students and 2,500 courses needs to be able to generate two types of reports. The first report lists the class registration for each class, and the second report lists, by student, the classes that each student is registered for.
The obvious implementation might be to use a two-dimensional array. Such an array would have 100 million entries. The average student registers for about three courses, so only 120,000 of these entries, or roughly 0.1 percent, would actually have meaningful data.
What is needed is a list for each class, which contains the students in the class. We also need a list for each student, which contains the classes the student is registered for. Figure 3.27 shows our implementation.
As the figure shows, we have combined two lists into one. All lists use a header and are circular. To list all of the students in class C3, we start at C3 and traverse its list (by going right). The first cell belongs to student S1. Although there is no explicit information to this effect, this can be determined by following the student's linked list until the header is reached. Once this is done, we return to C3's list (we stored the position we were at in the course list before we traversed the student's list) and find another cell, which can be determined to belong to S3. We can continue and find that S4 and S5 are also in this class. In a similar manner, we can determine, for any student, all of the classes in which the student is registered.
/**
* Created by Labunsky on 24.03.2017.
*/
public class MultiListEntry<S, C> {
private MultiListEntry<S, C> nextStudentEntry = null;
private MultiListEntry<S, C> nextCourseEntry = null;
private S student;
private C course;
MultiListEntry(S student, C course) {
this.student = student;
this.course = course;
}
public S getStudent() {
return student;
}
public C getCourse() {
return course;
}
public void setNextStudentEntry(MultiListEntry<S, C> next) {
nextStudentEntry = next;
}
public void setNextCourseEntry(MultiListEntry<S, C> next) {
this.nextCourseEntry = next;
}
public MultiListEntry<S, C> getNextStudentEntry() {
return nextStudentEntry;
}
public MultiListEntry<S, C> getNextCourseEntry() {
return nextCourseEntry;
}
}/**
* Created by Labunsky on 24.03.2017.
*/
public class MultiList<S, C> {
private Map<S, MultiListEntry<S, C>> studentsIndex = new HashMap<>();
private Map<C, MultiListEntry<S, C>> coursesIndex = new HashMap<>();
public void add(S student, C course) {
MultiListEntry<S, C> newEntry = new MultiListEntry<>(student, course);
MultiListEntry<S, C> lastEntry;
if (studentsIndex.containsKey(student)) {
lastEntry = studentsIndex.get(student);
while (lastEntry.getNextStudentEntry() != null)
lastEntry = lastEntry.getNextStudentEntry();
lastEntry.setNextStudentEntry(newEntry);
} studentsIndex.put(student, newEntry);
if (coursesIndex.containsKey(course)) {
lastEntry = coursesIndex.get(course);
while (lastEntry.getNextCourseEntry() != null)
lastEntry = lastEntry.getNextCourseEntry();
lastEntry.setNextCourseEntry(newEntry);
} else coursesIndex.put(course, newEntry);
}
public MultiListEntry<S, C> getStudentEntries(S student) {
return studentsIndex.get(student);
}
public MultiListEntry<S, C> getCourseEntries(C course) {
return coursesIndex.get(course);
}
}