Data Structures

Question 1

Linked List

Answer 1

Points to first [and last] linked nodes. If a Doubly Linked List, it can iterate in either direction.

Pros:
- insert/remove from start/end/middle—if you have a node reference—is always O(1)

Cons:

• arrays iterate faster (though not much different in JS since they’re hash tables)
• random read/writes are O(n) whereas arrays are O(1)

Question 2

Node

Answer 2

Simple object that contains data and a reference to the next Node (or null if there isn’t one).

Question 3

Hash Table

Answer 3

Arrays & Objects in JS are Hash Tables, so our desire is only to understand their pros/cons:

Pros:

Cons:

Question 4

Queue

Answer 4

FIFO.

Operations: Add to the end of a list and extract the first from the list (like a line) w/ O(1) performance. LinkedList are great for this (whereas arrays have shift as O(n))

Question 5

Stack

Answer 5

LIFO.

Operations: Add to end of list and extract the last from list w/ O(1) performance. JS Arrays are great for this.

Question 6

Deque

Answer 6

Same as Queue but can add/remove from either direction.

Operations: Add to start/end of list and extract from start/end of list w/ O(1) performance. LinkedLists are great for this (whereas arrays have shift/unshift as O(n))

Question 7

Trees & Balanced Trees

Answer 7

Unlike linear data structures like Array or LinkedList, Trees allow you to find a value in less steps than iterating a linear data structure. Balanced trees ensure that the max number of steps stays balanced across the tree.

Pros:
- faster searching

Cons:

• more complex to implement
• removing is no trivial matter, and can be slower than linked lists

Question 8

Graphs

Answer 8

Graphs are a set of vertices (points on the graph; singular word is vertex) and edges (connections between vertices). A path on a graph is a chain of vertices connected by edges, equivalent to a route on a map.

By traversing the graph, we can determine the path.

BFS—breadth first search—visits neighbors of each vertex before moving on to the next vertex. This is done using a queue containing the next vertex.