• 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:

Check out: What is a 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.

Check out: What is a 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.

• Check out: What is a Linked 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.

• 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.