What is a data structure? Compound data that we group together. Ex., price of a stock option at a given moment.

What operations are possible on a data structure? Sorting, searching, adding, deleting,

What is Big O Notation? It is a measure of how much an operation scales on a data structure in a time scale.

Is a data structure perfect for all cases? No, each one is better at a certain operation: etc…

What is a Linked List? It is a data structure that has a node (which has a value and a pointer). Ther value can be a number, and the pointer connects it to the next node on the chain. The first element is the head, the last one is the tail.

• PROS:
• adding new nodes
• deleting nodes
• CONS:
• retrieving
• searching

What is an array? Is a continuous block of cells on the computer memory.

• PROS:
• retrieving items
• CONS:
• adding items (sometimes - because you may move the whole array to a new block so that it fits)

What is a Hash Table? Equivalent of a dict in Python, object in Javascript. It has a key, and you get the value by its’ key. The key passes through a hashing function that maps to a memory location. It is different from an array because the memory location to store It does not need to be continuous. collision - depending on the hashing function, 2+ keys could point to the same memory location. Higher level languages solve that problem.

• PROS:
  • adding
• removing
• retrieving
• CONS:
  • collisions

What is a stack? Last in, Last Out. Example: stack of dishes, you must remove the last to not break all of them. Example 2: a call stack on a programming language push: add to the top pop: remove from the top Related to the “Depth First Search” algorithm.

What is a queue? First in, First out. Works like a queue in a bank, when you are on a line to pay something, etc… enqueue: add to the list dequeue: remove from the list Related to the “Breadth First Search” algorithm.

• PROS
  • efficient add + remove
• CONS
  • limited use cases

What is a graph? Similar to a Linked List (you have notes pointing to other nodes). The pointers are called “edges”. Edges can have weights (numbers assigned to them). Example: Sao Paulo can be a node, Ubatuba can be another. The road to them is the edge, and the length of the road can be the weigth of the edge. Complicated relationships, like social media networks, are also stored as graphs. There is a whole computer science field related to it called “graph teory”.

What is a tree? It is a hierarchical graph, in which nodes expand in one direction. Examples: family tree, html with nested elements

What is a binary search tree (BST)? - More specific tree, that allows searching efficiently. - Each node can only have 2 children (left and right) - left < node - right > node

• Example: 5 /
  1 7
• CONS:
  • Adding elements in weird order can turn it very unbalanced, reducing its efficiency. (one of the sides, left or right, much bigger than the other) (that can be solved with self balancing trees: red black trees, b trees)