Core Concept

This prototype is intended to be a visualization of Linked Lists.

Why?

Linked lists are simple at face value: they are chains of nodes where each node knows its own value and which node follows it. However, this structure has complex implications for traversing the list and adding new nodes. Typically, these are explained using a visual representation of the entire list written out and arrows showing which nodes point to which other nodes. This is useful for understanding how the list as a whole looks at any given point, but does not help students understand that actually only one node may be viewed at a time and new nodes must be added in a particular way in order to avoid losing the rest of the list.

The Pitch

Gain experience with linked lists by physically manipulating a chain of flags. Each flag has a letter on it and a rope to connect it to the flag that follows it. Traverse the chain manually by pulling flags towards yourself one at a time, and hang on to the chain while you add a new flag without losing the rest. The goal is to make the chain of flags spell out a certain word.

The Actual Experience

This prototype changed a little bit during the development process. The most significant change is that the traversal of the list changed from hand over hand to wrapping the flags around a wheel, because two hands are not enough to hold everything you need to in this interaction and we needed a way to justify not being able to traverse the list backwards. We decided to try adding a wheel that would function kind of like a winch so that when it’s released it goes straight back to the beginning of the banner of flags.

Key Interactions:

1. Wrap the banner around a wheel one flag at a time to get to the flag you need.
2. Follow the correct procedure to add and remove flags so that you don’t lose the rest of the banner by disconnecting a flag too early.

Key Lessons:

1. Linked lists must be traversed one node at a time. (All but the first couple flags of the banner are out of reach until the player uses the wheel to bring them closer.)
2. New nodes must be added to the list by first connecting the new node with the node in the list that should follow it, then by connecting the node that should come before the new node to the new node. (Flags are added by setting their rope to connect to the flag that should come next before redirecting the rope from the flag that comes before it to connect to the new node instead of the one it was connected to.)
3. If the node that comes before the new node is connected to the new node first, nothing is connected to the rest of the list and the nodes that follow can no longer be accessed. (If the rope of the flag that comes before the new one is disconnected from the next flag before the new flag has been connected, the rest of the banner flies away).
4. Singly-linked lists can not be traversed backwards. (When the player lets go of the wheel it snaps back to the beginning of the list.)

Step by Step Walkthrough Guide

Demo Video

Team Goals

• Create an interaction that corresponds as closely as possible to working with a linked list, particularly in terms of traversal and insertion.
• Create an experience that allows for exploration and failure.

Lessons Learned

Usability:

• Programming a prototype that allows players to combine elements however they like proved to be more difficult than we expected. We wanted them to be able to chain flags differently and lose part of the banner if they did things wrong, which meant that the underlying program needed to be able to keep track of and handle those things. It turned out to be our most bug-prone prototype.
• Getting spacing right is really important, we struggled to have everything within reach without the players feeling too crowded or claustrophobic.

Teaching:

• The process necessary for adding a new flag is much less intuitive than we had thought. We had assumed that once players saw the pieces and how they connected they would figure out the process for adding to the chain organically, but they still needed quite a bit of guidance. This may have been because the banner does not look like it is any danger of getting lost if flags are disconnected.
• The layout ended up making the rest of the banner more accessible than originally intended, so the idea that flags must be traversed one by one did not come across very well.
• Letting part of the banner fly away turned out to be more fun than successfully completing the banner, so there was not a lot of incentive to follow the correct procedure.

Role in a Lesson

This experience could be used as a way of introducing linked lists if it were played at or near the beginning of a lesson and followed up with code-based practice. It could also be used as reinforcement of a lesson if students played it after learning the material.

Additionally, this experience could be used to introduce the idea of pointers in memory, potentially even without being connected to lists. 

In programming terms:

• The banner corresponds to a linked list.
• The flags are equivalent to nodes.
• The ties between the flags act as pointers between nodes.
• The start tag is the head of the list.
• The rest of the banner is the tail of the list.
• The wheel acts as a temporary “current” variable used to traverse the list.
• The player’s hands act as other temporary variables.
• The end marker acts as a pointer to null at the end of the list.

If this experience were used as an introduction to the concept, then a teacher could follow it up with code like this, which is a simple pseudo-code representation of what happens in the experience:

Level 1:
Initial: INKED
Target: LINKED

Code:
NodeL = new Node(“L”);
NodeL.next = Head.next;
Head.next = NodeL;

Level 2:
Initial: IKED
Target: LINKED

Code:
NodeL = new Node(“L”);
NodeL.next = Head.next;
Head.next = NodeL;
NodeN = new Node(“N”);
NodeN.next = NodeK;
NodeI.next = NodeN;

Level 3:
Initial: IKD
Target: LINKED

Code:
NodeL = new Node(“L”);
NodeL.next = Head.next;
Head.next = NodeL;
NodeE = new Node(“E”);
NodeE.next = NodeD;
NodeK.next = NodeE;

Level 4:
Initial: LINKEED
Target: LINKED

Code:
NodeE1.next = NodeD;

Ideas for Future Development

• Generate random target words rather than trying to make the banner say “linked” all the time.
• The structure could be themed many different ways, and it may help to make the node in the list look like they could easily fall away if disconnected.
• Find a way to make only the current flag and the one following it easily accessible, so that the list really must be traversed one flag at a time.
• Add feedback for individual steps.
• Improve the instructions and/or add a tutorial.

Teacher Reactions

The teachers that playtested this experience for us were generally excited by it. It was somewhat difficult to get a sense of how it might be useful in teaching linked lists because linked lists tend not to be introduced until later computer science courses, so none of the teachers we showed this to were actually very familiar with them. However, they still thought that this experience was something they could use to teach well and that their students would like it. We also found that teachers had an easy time coming up with different lessons that this prototype might be useful for. One elementary school teacher suggested that with some minor modifications this experience could be good for spelling practice for younger students, and a high school teacher thought that this would be a good way to introduce memory and pointers.

Student Reactions

 The student reaction to this prototype varied pretty widely. Some students really struggled to get the actual interactions working, and they tended not to get very much out of the experience. The students that did figure out the interactions tended to figure out the necessary process for adding flags fairly quickly. We had varying degrees of success with people understanding the steps they needed to follow; some students only needed it explained to them once and some needed the explanation every time. Most of the students found it an interesting experience.

Thoughts From the Team

Miriam – I really like the fundamental design of this prototype and the way that it corresponds so closely with the way linked lists work. I think the wheel does kind of get in the way of that, and I wish we’d had time to figure out a more effective way of handling the traversal. It was originally pulling each flag closer manually, but we realized that two hands isn’t actually enough for the necessary interactions and introduced the wheel. Overall, I think the concept of this one is strong but it needs some more work before it will be an enjoyable and engaging experience.

Jiawen – The original design clearly demonstrate all important facts about a singly linked list. However, the wheel doesn’t work as we expected. But the possibility that we can do with pointer makes it really fun to play around. Besides, maybe we shouldn’t have the tail of the main list fly away. Whenever the player is getting familiar with operation and the accidently miss the tail of the list, they mostly just had to restart the game.

Luna – Understand how this illustrate linked list is simple. However, understand how to use this is painful. And accidentally making interesting mistakes is obviously not a good way to encourage people to do things correctly.

Nick – Flying flags is an adamant attempt that tries to map every legitimate operation in CS to an experience in VR. We believed this would be very helpful in teaching the CS concept. However, it seems like there is a balance between the usability and correspondence to CS concept. Interactions in the game, since they have to match operations on linked list, are not intuitive enough for the naive guests. The game itself illustrates the linked list well, but is not easy for the players to play through.

Joe – I like how straightforward it shows people what is a linked list. With all the interactions and friendly environment style, I would say people will be happy to learn in such an environment. However, there is one part a little confusing where the wheel’s original objective is just making people to be able to reach further flag rather than moving to there, so every time you turn the wheel and release it will go back to its original position which confuses a lot playtesters.

Click Here to Get the Code and Try it For Yourself

Further Reading

To learn more about this prototype and its development, check out these blog posts:

1. Week 6: Wrapping Up Solar System and Fractal Magic
2. Week 7: Of Factories and Flags
3. Week 8: Refining and Preparing
4. Week 9: Halfway Through
5. Week 10: Playtesting and More