Presentation 10: Memory and Linked Lists

Overview

Look at what memory is. In particular look, how linked list can be used to represent a list of numbers. Explore linked list in a game settings - making a train, removing / adding a train car, a problem with loops.

Resources

A set of cards - each containing a number in a box an arrow and a next number in the linked list following after this one, for example for a list 2,6,3,1

2->6

6->3

3->1

1

There should be the following sets:

A set of 6-8 cards for each group of kids, with all numbers in a list different

2 sets of 10-15 cards for half a class each set.

Presentation

Memory

Remember we talked about a processor? What can it do?

Let kids offer their answers

A processor is a computer part that's really good at calculating, but what's its problem? Yes! It has no memory!

So, if it needs to add many numbers, what can it do?

It uses external memory. External memory is like a honeycomb, or a drawer, where you can put a number in a box. Then processor checks what's in a box and uses that number.

Invite 5-6 kids to come.

Let us be these memory boxes. So, I tell each person what number to remember. Then the processor can just ask each person what number they remember and use it.

Do this for half of the kids (3 numbers)

Linked List

Now, what if the processor needs to add many numbers? Because it's so forgetful, it will easily forget who of you he asked to remember numbers, and in what order.

So, in order to solve this problem, people invented linked lists.

Draw a linked list on a board - one box is connected with the next one with an arrow.

So, when I ask you to remember the number, I also ask you to remember the name of the person who is next in the list. 

Try it with 3 numbers.

You see, the processor doesn't need to remember all 3 kids! All it needs to know is the name of the first person, first memory box, and then he can find out the rest of the numbers.

Train

Now, let's play a game. I am going to give out the cards to each of you. You'll split into teams of 6-8. The game is called a train. On each card there is a number on a wagon, as well as which is the next wagon it pulls. You should combine yourselves based on what cards you are given in a line that represents the train.

Give kids example on a board

Have kids do the exercise. Help as needed

Make sure the kids are positioned from left to right - in the same directions as the card is drawn, otherwise it's confusing. In other words, 

5-> 3, 3->4

Make sure kids are positions 

5 - 3 - 4 , not 4 - 3 - 5

Deleting an element

I am going to remove one of you from the train. You see, your train is no longer working - the wagons pull each others until the wagon that was removed. Then there is a break, and nobody pulls the rest of the wagons. So you need to fix it - you can erase and write new numbers on your cards.

remove a person in the middle.

Have kids try it. If they have hard time, show an example on a board:

5->3   

3-> 4  

4

Remove 3 and you get

5->4

4

Have the person who was removed, help the rest of the kids to figure it out.

Inserting an element.

Distribute new cards to each of the people removed. The card should just contain one number but no links. The number should be different from the other numbers in a list.

Ask kids to insert a wagon in a train. You may specify where to insert a wagon - first, last or some other place.

Show on the board an example if kids have hard time

5->4

4->2

2

insert 3after 4:

5->4

4->3

3->2

2

(Most kids add to the end of the train if the location of the new wagon is not defined.)

Loops

Modify the last wagon in each group to point to the beginning of the array. Ask kids in each group to modify the train according to the correction.

Most of the kids just stand as they were. Then correct them:

Hmm, this is interesting, the last wagon pulls the first wagon!

Have kids make a circle and see how their train is funny - wagons pull each other in circles.

Big train

This exercise is very challenging. We are going to build the BIG train (either with all kids or half of them). You will have to figure it out how to line up correspondingly so that your wagons are attached to each other.

Distribute the cards and have them make a big train.

(I did a single chain for all 26 people, and made a mistake in the cards (same number, pulled by different wagons) . This confused the kids. But even if the mistake was not made the exercise was extremely challenging because the number of kids was so big. At the end, I said the lesson is over, everybody did a good job, even though the kids weren't even close :)

Here is a sequence of 30 numbers. Cut the sequence depending on the number of kids. For older kids, have the last number point to the first, so that the train loops