Data Structures & Graphs
Time 1.8 hrs

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

### Blurb

Data Structures

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

### Outline

 Learner OutcomesStudents will: ... Competency Focus ... Interdisciplinary Connections ... ReflectionWhat was successful? What needs changing? Alternative Assessments and Lesson Ideas? What other Differentiation Ideas/Plans could be used? ... CreditsAny CC attribution, thanks, credit, etc. Database vector created by fullvector - www.freepik.com Linked list illustration by Edpresso, CC-BY-SA 4.0 Graph illustration by Edpresso, CC-BY-SA 4.0 Tree illustration by Edpresso, CC-BY-SA 4.0

This page requires you to be logged in to access it. Please login and try again.
10 mins
Structuring Data
Introduction
• 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
Trees
Theory

Check out: What is a tree?

5 mins
Traversing the Tree
Example
• 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
Graphs
Theory

Check out: What is a Graph?

5 mins
Traversing the Graph
Example
• 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
Theory
5 mins
Traversing the List
Example
• 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
Evidence
• 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
• 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.

## Embeds

There are no records to display.