Multilists

Example::

Lets take a look at simple registration example ,
There 5 students and 4 courses available.
A student can be subscribe to zero or more courses.
A course can be subscribed by zero or more students.
We have to print the 2 reports
    1. Print all the courses with the list of students who were subscribed to the same.
    2. Print all the Students with the list of courses to which they have subscribed.
For Example, How we will store the following details
    1. S1 subscribed to the courses C1 & C2.
    2. S2 subscribed to the courses C2 & C4.
    3. S3 subscribed to the courses C1 & C3.
    4. S4 subscribed to the courses C1, C3 & C4.
    5. S5 subscribed to the courses C2 & C3.

Array implementation for Registration::

 We can use 2 dimensional array to store the value.
               int college[no_of_course][no_of_students]==> college[4][5];

 Print all the courses with the list of students::

 Print all the Students with the list of courses::

Problem in Array Implementation::

•     Here, We have used 4x5=20 number of spaces. But we have utilized only the 11 spaces which has value 1. Remaining 9 spaces are waste of space.
•     To avoid the wastage of space in 2 dimensional array to store the course and student combination, we can use Circular Linked List, here we can say it as Multilists. 

Multilists implementation for registration::

    We will use 2 circular linked lists, one for student another one for course.
    S1, S2, S3, S4 are Header of students(Circular Linked List).
    C1, C2, C3, C4 are Header of courses(Circular Linked List).
 

 Print all the courses with the list of students::

 Print all the Students with the list of courses::

Disadvantage of using Multilists::

•     Using circular linked list save space but does so at the expense of time.
•     In the worst case, if the first student was registered for every course, then every entry would need to be examined to determine all the course names for that student. Because in this application, there are relatively few courses per student and few students per course, this is not likely to happen.
•     If it were suspected that this could cause a problem, then each of the (non header) cells could have pointers directly back to the student and class Header. This would double the space requirement but would simplify and speed implementation.

 Reference::

     Data Structures and Algorithm Analysis in C, Mark Allen Weiss, 2nd Edition.



Goto Data Structure Concepts

Goto CSR Initiative