Data Structures & Graphs
Time 1.8 hrs

Difficulty Intermediate
Prerequisites Elevator Challenge
Departments Science
Authors Sandra Kuipers
Groupings Individual
Minimum Year Group None


Data Structures


This work is shared under the following license: Creative Commons BY-SA-NC


Learner Outcomes
Students will:
  • ...
Competency Focus
  • ...
Interdisciplinary Connections
  • ...
What was successful? What needs changing? Alternative Assessments and Lesson Ideas? What other Differentiation Ideas/Plans could be used?
  • ...
Any CC attribution, thanks, credit, etc.

This page requires you to be logged in to access it. Please login and try again.
10 mins
Structuring Data
  • What is a data structure?
  • So far, we've already used data structures in our code: Arrays.
  • Arrays are a linear data structure, like a list, where we access items in order with an index.
  • There are also non-linear data structures! This is where data gets fun and a bit creative.
  • Non-linear data structures include node graphs and trees.
  • Check out the following video for an intro to data structures:

5 mins

Check out: What is a tree?

5 mins
Traversing the Tree
  • Trees are non-linear, and at first it can be hard to see how they'd be useful.
  • A Decision Tree is a type of tree structure, and a great way to visualize trees.
  • Consider the following situation:
    • Lets say I wanted to know what month you were born in, but I could only ask you yes or no questions.
    • I could technically start at the beginning and ask...
    • "Is is January? Is it February? Is it March?" etc... all the way to December.
    • To get the right answer, I'd end up asking between 1 to 11 questions.
    • This isn't very efficient! And programming is all about efficiency.
    • Instead, we could structure the questions into a decision tree:

  • With this structure, no matter which month it is, we would only ask 3 or 4 questions.
  • To traverse a decision tree, start at the top, then work your way down until you reach a leaf node: the end result is your decision.
  • This particular tree is a Binary Tree because each decision has two options.
10 mins

Check out: What is a Graph?

5 mins
Traversing the Graph
  • Graphs, also called node graphs, are another non-linear type of data structure.
  • They're great for representing things that have connections to each other.
  • This could be physical connections, like roads on a map or wires in a network.
  • This could also be conceptual connections, like friends in a social network.

  • For an example of a node graph, lets consider the board game Risk.
  • In risk, the map is divided into six continents, each a different colour.
  • Not all continents can reach each other: they're connected by land borders, or dotted lines for water connections.

  • If we were programming a digital version of the Risk game, we'd need to know which continents can reach each other.
  • To do this, we could represent the map as a node graph, below.
  • Each continent is a node, and the connections between them are edges.

  • To traverse a node graph, any one node can use it's edge to reference the next node, and so on and so forth.
  • If you wanted to ensure you reached each node, you'd flag them as 'visited', then move onto the next unvisited node, until they're all visited.
10 mins
Linked Lists
5 mins
Traversing the List
  • Linked lists are a linear data structure.
  • To traverse the list, you start as the head of the list, then move to the next item, until you reach the end.
  • Linked lists can become circular if the end points back to the head.
  • A singly linked list only has a single reference per node, which points to the next node.
  • A doubly linked list has two references: a next node, and a previous node. This enables traversing the list in either direction.

60 mins
Data Structures
  • These are just three common data structures, there are others.
  • The goal of this unit isn't to memorize them all, but to consider how they might be useful.
  • Open up your slideshow from the beginning of this course.
  • Pick any three of the following data structures and add some new slides to your slideshow:
    • Tree
    • Graph
    • Linked List
    • Stack
    • Queue
    • Array
    • Hash
  • For each slide, add:
    • A short definition, in your own words.
    • An image to illustrate this concept.
    • Describe one idea of how you might use this data structure. Feel free to be creative :)
  • The images and videos in the unit here will get you started, but you'll need to do some more research of your own to complete these slides.
  • Once you have finished, submit the link to your slideshow as evidence of learning in this unit.
There are no records to display.
Powered by Gibbon v26.0.00dev | © Ross Parker 2010-2023
Created under the GNU GPL at ICHK | Credits | Translators