|
|
|
 |
|
|
|
Teaching Linked Lists with Barrel of Monkeys
|
|
| |
Contributed by Sandy Czajka
Riverside Brookfield High School
Riverside, Illinois
When I started teaching AP Computer Science, the topic that scared me the most was linked lists. The whole idea of tying together nodes and pointers and teaching things like doubly linked lists and circular linked lists was daunting to me. Then one summer day a couple of weeks before school started I was shopping in a dollar store. I ran across a game I played as a kid: Barrel of Monkeys.
Fear completely took over my body when I realized that instead of reliving childhood memories, the thoughts crossing my mind were how the monkeys were nothing more than nodes and their arms could link the monkeys together! I could use markers or tape to color the monkeys' arms to make the pointers more clear. Developing the pseudocode for various linked lists functions with the students became much more entertaining using the monkeys as visual aids. Adding monkeys (nodes) to the beginning, middle, or end of a list could be easily explained when students could see the movement of the pointers clearly. Removing monkeys (nodes) from the linked list brought other problems to the surface. What happens when the monkey is removed from the list? Will we end up with a mess that needs to be cleaned up? Will there be a useless surplus of monkeys everywhere, indicating that the memory is being used up? (In other words, will there not be enough monkeys to make new nodes?) Or, is there an automatic garbage collector that comes around and cleans up the mess every so often?
As the year progressed, we referred to the monkeys on many occasions. The concept of a circular linked list was not such a mystery when we saw that if the last monkey pointed to the first monkey we actually made a circle of monkeys! Discussions then followed about how to keep track of when we traversed the entire list so as to not end up in an infinite loop. For doubly linked lists, students understood the importance of both arms (pointers) being crucial for the monkey and provided much more flexibility for accessing information from various monkeys (nodes) in the list. When we began to implement priority queues as a linked list we set up a "monkey emergency room." Each monkey came in with various injuries and illnesses. The monkey was then assigned an appropriate critical level and then entered into the priority queue so the most critical cases could be seen first. This reinforced the understanding of adding nodes to a list at various points in the list as well. Providing this visualization as an introduction to a variety of topics made the transition to code go much more smoothly.
I am not sure that all the students find the Barrel of Monkeys necessary, but for many students the visualization makes the introduction to a difficult topic less traumatic. It definitely made the teaching of linked lists less traumatic for me!
Contribute
If you would like to contribute your suggestions for teaching linked lists, please submit your ideas.
|
|
|
|
|
|
Course Home Pages