Title: Data Structures

Q: Array
A: Contiguous memory stored in locations labelled from 1 to $n$.
\begin{itemize}
\item Accessing/changing $i$th element is $O(1)$.
\item Inserting/removing at $i$th position is $n-i+1 =O(n)$.
\item Searching for an element is $O(n)$.
\end{itemize}

Q: Linked list
A: A set of pairs $(e,p)$ called \emph{nodes} where $e$ is a data element and $p$ is a pointer to the next node. There are also pointers to the first and last nodes.
\begin{itemize}
\item Accessing/searching $i$th element is $O(n)$.
\item Inserting/removing near a pointer is $O(1)$.
\end{itemize}

Q: Binary search tree
A: A collection of nodes $(v, L, R)$ containing a value and (pointers to) two child nodes such that $l < v < r$ for any $l\in L, r\in R$.
All tasks are $O(h)=O(\log n)$.

Q: Root
A: The single node of a binary search tree with no parents.

Q: Sub-tree
A: The binary search tree consisting of a node and its descendants.
The \emph{left sub-tree} is the sub-tree formed by the left child and vice versa.

Q: Height
A: The height $h$ of a binary search tree is the distance of the farthest node from the root, i.e.
\[
h = \lceil \log_2 (n) \rceil = O(\log(n)).
\]

Q: Heap
A: A heap is a tree-based structure for ordered data that satisfies the heap property: child nodes have values larger (smaller) than the value of their parent in a (max-)min-heap.

Q: Binary heap
A: A complete binary tree (all, except maybe the last, levels filled). The root is the min.
\begin{itemize}
\item Searching is $O(n)$.
\item Inserting is $O(\log n)$ worst case, $O(1)$ average.
\item Deleting the min is $O(\log n)$.
\end{itemize}

Q: Hash Table
A: A collection of key-value pairs. A hash function determines a memory location for each key. Inserting/deleting/retrieving are $O(1)$ unless there is a collision, which is $O(n)$ to fix.

Q: Hash collisions
A: Non-injectivity of a hash function.

Q: Stack
A: A stack has two operations: push and pop, both $O(1)$. Push appends an element and pop undoes the last push.
Underneath: an array or a linked list.

Q: Queue
A: A queue also has two operations: push and pop, both $O(1)$. Push appends an element and pop removes the first pushed element.
Underneath: linked lists.

Q: Deque
A: A double-ended queue, or deque, is a queue that can be pushed into and popped from both ends.
Underneath: doubly-linked list, i.e. a linked list that has pointers in both directions

Q: Priority queue
A: A priority queue is a structure into which items are pushed with a given priority. Pop removes the highest priority element.
Underneath: a heap, so that pushes and pops are O(log n).

Q: Map
A: A map, also called an associative array, is a structure that stores key-value pairs.
Underneath: binary search tree ($O(\log n)$) or hash table ($O(1)$ expected, $O(n)$ max).