CSC 216/s08/no comparison

Linked Lists in Person

This exercise will help students understand the structure of a linked list.

The Problem

A linked list is a useful data structure but it can be very confusing for students first trying to grasp it. This interactive exercise should help students understand the concept.

Participants and Props

To run this exercise, you will need at least 6 students and some paper and writing utensils.

How to Execute

Set-up

Each student participating in the exercise has a card with "Data = [name]", name being the name of the student, written on it. One student is chosen to be the head of the list. Three students are then lined up to the left of the head of the list in alphabetical order. Starting from the head, each student will write "Next = [name of the person to their left]" on their card. The last student in the list should write "Next = null" on their card. This setup represents a basic linked list.

Here is an example card.

Insertion

Now we will practice inserting a new node. One of the remaining students will write "Data = [name]" on their card, and become the new node. The new node will ask if the first node is alphabetically before itself. If the answer is no, the new node will stand to the right of the first node. The new node will then write "Next = [name of the first node]" on his card. If the answer is yes, the new node will ask the next student in line until they receive a "no" answer or reach the end of the line, in which case they will stand at the end of the line write "Next = null". After the student has found their place in the line, they will write "Next = [name of the student to their left]". The student to the right of the new student will write "Next = [name of new student]" on their card.

Deletion

Now we will practice deleting a student. The instructor will choose a student to be deleted. Starting at the head of the list, he will ask each student if their "Data = [the chosen value]". If the answer is yes, the deleted student will pass the value of its "Next" to the student to their right. The student to their right will appropriately change their card, and the chosen student exits the list. Continue these exercises until the concept is understood.

Demonstration

Here is a demonstration of the exercise.