CSC 216/s08/no comparison: Difference between revisions
No edit summary |
No edit summary |
||
| Line 14: | Line 14: | ||
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. | 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. | ||
[http://pg-server.csc.ncsu.edu/mediawiki/index.php/Image:Java5.jpg Here] is an example card. | |||
====Insertion==== | ====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 | 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 | ||
| Line 21: | Line 25: | ||
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. | 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. | ||
[ | [http://pg-server.csc.ncsu.edu/mediawiki/index.php/Image:Java5.jpg Here] is an example card. | ||
Revision as of 19:37, 20 April 2008
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.
Here is an example card.