Tuesday, September 06, 2005

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


Post a Comment

<< Home