The great link list game!

I always have this game every time i teach link lists. In this game, the class is divided into groups of more or less seven. Some of the students would represent Node objects following this class delaration:

class Node {
int i;
Node next;
}

Students representing Node objects would be holding a piece of paper with a number, representing the value of their i variable. They would use their left hand to represent the next variable, if next is pointing to another object, they would use their left hand to point to the classmate representing that node. if next is null, they would cross their arms to indicate that they are pointing to no one.

Some members of the group would be Node references. Node head (pointing to the start of the list), tail (pointing at the last node), rover (an arbitrary object pointer) and bago (pointing to a new node). They would be pointing to Node objects, or crossing their arms to indicate that their value is null.

I had them work through the different link list algorithms as Machine Exercises. First group to finish gets +2, last group gets -2, groups who get it wrong get 6/10. +2 for optimal code.

Had them work on the following:
: deleting a node at the head of the link list
ME27: inserting at head
ME28: inserting at tail
ME29: inserting at rover
ME30: deleting rover.next
ME31: searching for an object (return rover)

Managed to finish all 6 games in two hours. and the fun thing was my students got it by themselves. pointer acrobatics is so simple to visualize if you actually have people running around and acting the commands out.

and then i told them: the link list implementation of the stack is just inserting and deleting at head. the link list implementation of queues is just inserting at tail, deleting at head. and then, for their machine exercise, the rover algorithms can be used to insert and delete nodes in a linklist implementation of a database.

that sweet sweet "ah!" moment.

machine exercise 32 and 33 are just cdstack and songqueue again, this time with the linklist implementations. machine exercise 34 is a mini-machine problem, given a class Crush with attributes String name and String crush, create a simple database that allows for inputs and deleting and searching.

and so ends the second part of the OOP class
ME23

Well... into the semester comes array stacks and circular queues. Made a nifty java application that visualizes (in a really cute way) circular queues. get it from here:

Afterwards ME25 and 26, CDStack class and SongQueue class. The CDStack simulates a stack of CDs. Of course you could only get and put CDs at the top, so what if you want to get a CD in the middle?

The SongQueue class has methods currentlyPlaying(), insertSong and nextSong(). This forced them to use the Queue algorithm on objects instead of primitive data types, showing that the algo works for whatever datatype.

One of the things about these two classes is that i asked them not to reimplement stacks and queues for their program. They have to reuse the existing stack and queue implementation (small changes only). They are to use Stacks and Queues as an abstract datatype without having to worry about how storage is implemented inside.