Manipulatives for understanding the concept of Linked Lists in a computer science class - the Nodes are the elements of the list and have a slot for you to put in a card (e.g. a section of a 3 x 5 card) with the value being held by the node. Each node has a "next" element that can latch onto another node. Pointers also have slots for their variable names (e.g., "p") and nestle into the sides of the nodes.
The shortcoming of this is that it loses the idea that the pin & hole connections are also pointers, but it reinforces the idea of a chain of nodes. The pointer connections are different because in typical algorithms, we find that more than one pointer is likely to point to the same node. It is also easy to see that creating a pointer variable doesn't automatically create a node.
The goal is to have students practice things like advancing a pointer through the list, adding items to the start of the list, deleting items from the middle of the list, and other algorithms that apply to linked lists. Sometimes, as students are working through writing or analyzing these algorithms, it is too much to keep in their heads!
Overview and Background
A Linked List is a computer science concept - a data structure for holding a sequence of data elements. While many students can grasp the basic idea and think that they have a deep understanding, often when they actually try to write code to implement a list, they find that they can't keep track of it all in their heads!
This project is a set of manipulatives that can help a student walk through his or her own code to identify problems or to talk through a potential algorithm.
Lesson Plan and Activity
The student is given a pool of Node objects and about 3 Pointer objects. Also, the student is given a set of cards (typically a quarter of a 3x5 card) for each node and a smaller card (enough for a variable name) for the pointers.
To create a Node with a given value ( e.g.,
new Node("A");),this is modeled by writing the value on a card, pulling a Node from the pool, placing the card in the node and placing the node on the table.
If this Node is being assigned to a standalone pointer ( e.g.,
*Node p = new Node("A");),, then the name of the pointer is written on a small card and put into a Pointer object, which is then nestled into the Node object.In this model, there are two slots for Pointers to connect to a given Node, but they are optional.
If this Node is being set as another Node's "next," then the node is hooked onto the previous node.
Typically, one pointer, "start" will indicate the start of a chain of Nodes, and at the end of the chain will be a Node with an empty connection.
Students attempting to simulate a pointer reassignment (e.g.,
p = p -> next) simply move the "p" pointer from one node to the next node. Assigning a pointer the same thing as another pointer (e.g.,
p = start) simply place the nodes so they both nestle into the same Node on opposite sides.
Students can use these techniques to simulate the processes of:
- adding an item to the start of the list
- adding an item to the end of the list
- counting the items in a list
- searching a list for a value
- inserting an item in the middle of a list
- removing an item from the start of the list
- removing an item from the end of the list
- removing an item from the middle of the list
- Several printed copies of the Node object, and about three printed copies of the Pointers. These look good if the Nodes are one color and the Pointers are another.
- a few 3" x 5" cards
- scissors to cut the cards (or precut them)