Data Structures and Algorithms Review

Flashcards covering data structures, algorithms, and related terms from the lecture notes.

Complexity (Big O Notation)

An estimate of the number of loops in a program; used to understand time complexity.

Common Complexity Classes

O(N) - Linear, O(N^2) - Quadratic, O(N log N) - linearithmic

Stack (LIFO)

A data structure where the last element inserted is the first element removed (Last In, First Out).

Stack - Push

An operation to insert an element into the stack.

Stack - Pop

An operation to remove the top element from the stack.

Stack - Peek

An operation to view the top element without removing it.

Queue (FIFO)

A data structure where the first element inserted is the first element removed (First In, First Out).

Queue - Dequeue

An operation to remove the element from the front of the queue.

List

A general data structure that allows insertion or removal from any position (middle, end, etc.).

Recursion

A programming technique where a function calls itself to solve smaller subproblems.

Recursion - Base Case

The termination condition for a recursive function, preventing infinite loops.

Iterator

A component that allows traversal and removal of elements from a data structure.

Iterator - hasNext()

A method to check if there are more elements in the data structure during iteration.

Iterator - next()

A method to retrieve the next element in the data structure during iteration.

Optimal Sorting Algorithms

Sorting algorithms with a complexity of O(N log N), such as Merge Sort and Quick Sort.

Merge Sort

A sorting algorithm that splits the array into two parts, sorts them recursively, and then merges the sorted parts.

Quick Sort

A sorting algorithm that splits the array into three parts based on a pivot element: elements less than the pivot, the pivot, and elements greater than the pivot.

Binary Search

An efficient search algorithm that requires the data to be sorted and eliminates half of the elements in each step.

Hash Map (Key-Value Table)

A data structure that handles insertion, removal, overwrite, and retrieval of values based on keys.

Binary Search Tree (BST)

A tree data structure where the value in each node is greater than or equal to any value in its left subtree and less than or equal to any value in its right subtree.

BST Traversal - Level Order

Read nodes from left to right, top down.

Heap

A complete binary tree where the root node of every subtree is the smallest (in a min-heap) element.

Heap - Insertion

Adding a new node to the heap as the last leaf and then moving it up to its correct position.

Heap - Removal

Removing the root node, replacing it with the last leaf, and then pushing the new root node down to its appropriate position.

Graphs

Generalization of trees.

Breadth-First Search (BFS)

A graph traversal algorithm that uses a queue to maintain the order of traversal.