| title | type | duration | creator | competencies | ||||
|---|---|---|---|---|---|---|---|---|
Data Structures |
lesson |
2:30 |
|
Programming |
After this lesson, students will be able to:
- Identify common data structures
- Linked lists, Trees, Heaps, Tries, Graphs
- Be familiar with their common methods
- And be able to determine their run-times
- Know use-cases for each data structure discussed
Before this lesson, students should:
Linked lists are used to represent an ordered set. They are similar to arrays but do NOT live contiguously in memory.
We have a reference to the head (and possibly the tail). Each node has a reference (or pointer) to the next node.
In a doubly-linked-list each node also has a reference to the prev node.
We cannot get an element at a given index in constant time. We must iterate over the list.
We can however insert/remove an element to the head in constant time. This is not the case for an array. (Hence shift/unshift )
Linked Lists are often used to represent Stacks and Queues.
Why might we prefer to use linked list to implement a stack or queue? Why not an array?
Why would we choose to use a linked list over an array? What are the advantages and disadvantages?
A tree is a collection of nodes, where each node has some number of children. We cannot see every node at once, but we do have a pointer to the root node.
Leaf nodes are those that have no children.
Trees can be used to represent a family tree (where the old people are on top), or a file structure.
We can traverse a tree using Depth first search or Breadth first search. More on this below.
A binary tree is a tree such that every node has at most 2 children.
A binary search tree (BST) is one such that:
- The value of every left child is less than that of its parent
- The value of every right child is greater than that of its parent
This makes searching for elements in a BST very fast.
To insert into a BST, we compare the new val with the root value. If it is less than the root, we repeat the process for the left subtree. If it is greater than the root we repeat the process for the right subtree. We keep repeating this process until our node ends up on the bottom.
Look up how to remove a node if you are interested ;)
Tree.instanceMethods.traverse(callback) :=
left.traverse(callback) if hasLeftChild?
callback(value)
right.traverse(callback) if hasRightChild?
The above pseudocode is called in-order traversal. Check out pre-order and post-order as well.
This is a little more complicated. Look it up if you are interested ;)
How quickly (in Big-O) can we find an element in a BST with n elements?
How quickly can we find the min element? The max element?
Check out my Typescript and compiled Javascript implementations
An AVL (named for its inventors) tree is a self-balancing binary search tree. You do not need to understand how these work but know that they exist.
Self-balancing means that whenever we insert or remove a node, we re-organize the rest of tree so that no node with 0 or 1 children hangs more than 1 level below another.
Why would we want a self-balancing tree? Is it worth the implementation? Are the run-times different than a tree that is not self-balancing?
A Min Heap is binary tree such that the value of every node is less than the value of all of its children. Thus, the smallest value is always the root of the tree.
They are used when we want to keep track of the smallest element in a set.
You can probably guess what a Max Heap is
To get the min element we just look at the root. (Duh)
To insert elements, we add a node to first available position (the bottom-left) and "bubble it up". This means we keep swapping it with its parent until the value of the node is no longer larger than the parent.
How do we know inserting in this way will always leave us with a Min Heap?