Classroom Exercise Demonstrating Linked List Operations

Classroom Exercise Demonstrating Linked List Operations

Timothy J. Rolfe

Eastern Washington University

Computer Science Department
319F Computing & Engineering Bldg.
Cheney, Washington 99004-2493 USA

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. The students themselves operate as the linked list nodes, and retain the attributes of data value and next list node.

Keywords
linked list; program behavior simulation; introductory concept demonstration

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 “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 “head” entry 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 are.

Write that on 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 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 “éclair” from the list, and then put in an “eggplant” — I would much rather eat an éclair than an eggplant.

Web Resource

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).