Example Solution:

Linked Lists As a Queue - Pong ; Helpdesk Assignment

(Console version)

Which version of C#/ Visual Studio is required for this assignment?
The provided files are (obviously) C#, and (less obviously:) ) they were built using the Visual Studio 2005 product. If you have an older version of Visual Studio (or are using Mono), you probaby won't be able to open the Solution (.SLN) file. If this is the case, in order to build this, you'll need to add all the .CS files to a new project, and then everything should compile & run just fine.
Console Application / Test Harness
Feel free to omit these, and make the students do more of the assignment, if you want to.
Major Themes in Student Solutions
After you've read the assignment, it should make sense that there are (at least) two major styles of solution to this assignment.
  1. The first major theme (which, of course, has many variations :) ) is to create a class to represent a Queue, implemented using a LinkedList. One then creates a Helpdesk class which has two Queue objects within in - one for the high priority items, and one for the low priority items.
    Thus, the Helpdesk class basically dispatches "Add Ticket" requests to the correct queue, and making sure that PrintAll / PrintFirstItem types of methods do the right thing. Personally, I think this tends to be the easier approach, especially for weaker students. This solution is demonstrated in the Helpdesk_MultipleQueues class (and the QueueOfTickets class)
  2. The second major theme (again with variations) is to create a single class, and within it, to keep all the tickets in a single linked list. The best way to do this is to have the 'first/head' pointer be the next thing to remove, and then keep a pointer to the last thing in the 'high priority ticket' region of the list, and another pointer to the last thing in the 'Low priority ticket' region of the list. By putting high priority tickets in front of the Low priority tickets, add/remove are each O(1) operations.
    This approach, demonstrated in the Helpdesk_SingleQueue class, tends to be more difficult. Also, be aware that students can do bizzare things with this one - one student added new items at the front of the list (without sorting), and 'timestamped' each node as it was added, then (when printing), would run through the list N times (making the print operation an O(N^2) operation!).

The second source of variation is how to model priority. Since the assignment only specifies "High" and "Low" priorities, a bool(ean) is a natural and reasonable choice. In my class, students have seen enums, and so I push them to use those, instead. Once in a while a student will use an int to model priority, so that an arbitrary number of priorities can be modeled.

The example solution uses enums, just because that's what I want my students to see.

Another possible source of differences amongst student solutions is whether to have the Helpdesk/helper Queue classes store references to Ticket objects, or whether to have the linked list's node class incorporate the ticket description (and priority) directly. In the assignments as they care currently written, the students are required to have each linked list node contain a reference to a Ticket object.  I tend to encourage them to have the Helpdesk application interface with the rest of the program by description (strings) rather than objects. Internally, they can either incorporate this into each linked list node, or have each linked list node have a reference to a book object (their choice).