Classroom Exercise Demonstrating Linked List Operations

Classroom Exercise Demonstrating Linked List Operations
Available as a Word 6.0 document (inroads format) that prints in two pages

Timothy J. Rolfe

Computer Science Department
Eastern Washington University
319F Computing and Engineering Building
Cheney, WA 99004-2493 USA
Timothy.Rolfe@mail.ewu.edu
http://penguin.ewu.edu/~trolfe/

Abstract

This paper describes a strategy whereby, using directly manipulable items, one can show the behaviors of a linked list, and even show some of the details of linked list manipulations.

Overview

For purposes of this exercise, the instructor stands in for the program, the blackboard functions as local memory, the students function as heap space within the computer memory, and slips of paper constitute the contents of memory when the heap space is allocated for use as linked list nodes. The instructor has some means of calling random students, so that the space is pulled from the heap, and puts information onto the paper, mimicking the execution of an object constructor, which is then given to the student. To obtain information about the contents of an object after it has been constructed, the instructor/program must explicitly query the student/object for that information.

Set-Up Requirements

Generate the objects, slips of paper with a "Data" field and a "Next" field, thereby mimicking an object like this:

class Node

{  Object data;
   Node   next;
    .     .     .

My pack has the data field already filled in with food items, from "Apple" to "Zwieback" (though I had to get obscure and use "umbles" to get all 26 slips), with the next field blank. They are in forward alphabetic order.

In some fashion, assign each student a number, possibly from the class roster itself if that is numbered. Then get some way to shuffle the list. I’ve chosen to do a simple program that just shuffles the numbers and then provides them one after the other. Fairly obviously, a blackboard or whiteboard is needed to hold local information — the reference to the head of the list, as well as the reference to a current node during the traversal of the list.

List Construction — Insertion at the Front of the List

Initially have the "head" entry on the board contain "null". Then construct the list in a stack-oriented fashion (though you don’t have to tell the students that that’s what you’re doing).

For as many entries as you wish to make in the list
- Identify a random student
- On the Node slip, copy the current contents of "head" into "next"
- Write the name of the student into "head" on the board
- Pass the slip of paper to the student — who now is that node object in the list
End-For

Once you’re finished, the board points at the beginning of the list — it has the name of the student who is the first node object. All of the node objects are scattered throughout the classroom (while using them as an array would simply use them from left to right and front to back).

List Traversal

On the board you have not just "head", but also "current." That node reference will drive the traversal. As in the execution of a program, the local variables contain only references to objects. To get the information in the objects it is necessary to query the objects. The data fields themselves are probably private, so that the query actually is a function call.

Copy the contents of "head" into "current"
While "current" does not contain a null reference
- Ask the student whose name is in "current" what the contents of the "data" field is.
- Write that in a board area mimicking output.
- Ask the student whose name is in "current" what the contents of the "next" field is
- Update "current" to contain that name
End-While

The students will notice that the nodes come back in reversed order. If the objects were created in alphabetical order, they will show up in reversed alphabetical order.

List Amplification — Insertion at the Back of the List

Next you can show what is needed to avoid inverting the list: insert at back.

For as many entries as you wish to add in the list
- Copy "head" into "current"
- Loop
  - Obtain from the "current" student the contents of "next"
  - if "next" is null
    exit the loop
    otherwise
    write that name into "current"
  End-Loop
- Identify a random student
- Direct the "current" student to write THAT name into the "next" field of his/her object
- On the Node slip, either leave "next" empty or write null into it
- Pass the slip of paper to the student — who now is that node object in the list
End-For

Once you’re finished, you can do another traversal of the list. While the first items inserted are in reversed alphabetic order, the newly inserted items are in forward alphabetic order.

List Deletion and Further Insertion

Demonstration of insertion into the middle of the list, and of removal of items from the list, is simply a matter of making a similar conversion from the standard algorithms to using this particular physical implementation of a linked list. Myself, I like to remove the "eclair" from the list, and then put in an "eggplant" — I would much rather eat an eclair than an eggplant.

Web Resource

http://penguin.ewu.edu/~trolfe/LinkedListExercise/index.html
This page provides access to this paper, and also to the RTF file with 26 food objects, and to a C program to generate random student assignments (plus Windows executable files from the Borland C and Visual C compilers).