Data Structures & Algorithms

Data Structure

A way to store and organize data, and preforming operations on data.

Record

A data structure that stores items as subitems called fields.

Array

A data structure that stores an ordered collection of elements.

Linked List

A data structure that stores items in nodes, where each node points to the next node. featuring a dynamic size

Node

An individual element that stores data and may point to another node.

Binary Tree

A data structure where each node can have up to two children: a left child and a right child.

Hash Map

A data structure that stores items by mapping each item to a location using a key.

Heap

A tree-based data structure that maintains a specific ordering between parent and child nodes.

Max Heap

A heap where each parent key is greater than or equal to the keys of its children.

Min Heap

A heap where each parent key is less than or equal to the keys of its children.

Graph

A data structure used to represent connections between items using vertices and edges.

Vertex

An item or point in a graph.

Edge

A connection between two vertices in a graph.

Array vs Linked List

Arrays may require shifting elements when inserting, while linked lists can insert elements by changing pointers.

Algorithm

A sequence of steps used to solve a problem or accomplish a task.

Computational Problem

A problem that takes an input and produces an output that can be solved using a computer.

Efficient Algorithm

An algorithm whose runtime generally increases no more than polynomially as the input size increases.

Abstract Data Type (ADT)

Defines what a data structure does without specifying how it is implemented.

Abstraction

Allowing a user to interact with something at a high level without needing to know how it works.

Algorithm Efficiency

A measure of how effectively an algorithm solves a problem based on the resources it uses.

Computational Complexity

The amount of resources an algorithm uses, including runtime and memory.

Runtime Complexity

A measure of how the number of operations performed by an algorithm grows as input size increases.

Space Complexity

A measure of how the amount of memory used by an algorithm grows as input size increases.

Best Case

The scenario where an algorithm performs the minimum possible number of operations.

Worst Case

The scenario where an algorithm performs the maximum possible number of operations.

Constant-Time Operation

An operation that takes the same amount of time regardless of the input values.

Linear Search

An algorithm that starts at the beginning of a collection and checks each element until the search key is found or the end is reached.

Linear Search Best Case

O(1), because the search key could be the first element.

Linear Search Worst Case

O(N), because the algorithm may need to check every element.

Binary Search

An algorithm that repeatedly checks the middle element and eliminates half of the remaining search space.

Binary Search Requirement

The data must be sorted for binary search to work correctly.

Big O Notation

A mathematical notation used to describe how an algorithm's runtime grows as input size increases.

Big O Rule

Keep the fastest-growing term and remove constant factors and lower-order terms.

Asymptotic Notation

mathematical tools used to analyze the performance of algorithms by understanding how their efficiency changes as the input size grows. (3 different types)

Algorithm Analysis

The process of determining an algorithm's resource usage, such as runtime and memory usage.

Recursion

A technique in which a function calls itself to solve smaller versions of a problem.

Recursive Algorithm

An algorithm that solves a problem by breaking it into smaller subproblems and calling itself.

Base Case

The condition that stops a recursive algorithm from continuing to call itself.

Fibonacci Numbers

A sequence where each term is the sum of the previous two terms.

Recurrence Relation

A way of describing the runtime of a recursive algorithm in terms of smaller inputs.

Binary Search Recursion

A recursive binary search calls itself on either the upper or lower half of the search range.

Binary Search Time complexity

O(log N), because the search space is cut approximately in half after each step.

Binary Search Recurrence

T(N) = T(N/2) + O(1).

Recursion Tree

is a visual diagram used to analyze the time complexity of recursive algorithms by representing each recursive call as a node and the work done at that call as its value.

BinarySearch Example

BinarySearch(numbers, 0, 6, 42) searching [14, 26, 42, 59, 71, 88, 92] finds 42 at index 2.

Polynomial Runtime

A runtime that can be represented by a polynomial function such as O(N), O(N²), or O(N³).

O(1)

Constant time. The amount of work does not grow with the input size.

O(N)

Linear time. The amount of work grows proportionally with the input size.

O(log N)

Logarithmic time. The input is repeatedly reduced by a constant factor, such as cutting it in half.

O(N²)

Quadratic time. The amount of work generally grows proportionally to the square of the input size.

Linked List Statement

A linked list stores items in nodes where each node points to the next node.

Binary Tree Children

A binary tree node can have zero, one, or two children.

Array Indexing

Items in an array can be accessed using a positional index.

Linear Search vs Binary Search

Linear search checks elements one at a time, while binary search repeatedly checks the middle and eliminates half of the remaining search space.

Binary Search Requirement

The data must be sorted.

Max Heap Property

Every parent node has a key greater than or equal to its children's keys.

Min Heap Property

Every parent node has a key less than or equal to its children's keys.

Runtime vs Space Complexity

Runtime complexity measures operations, while space complexity measures memory usage.

What are the standard operations on data sturctures?

Accessing, updating, searching, inserting, and removing data.

What does data structure selection depend on?

Data types and required operations

What is a Hash table?

A data structure that maps items to array locations for fast key-based access.

What is a graph

Vertices connected by edges, used for relationship modeling

How do you perform an array append?

Determine size increase by 1, then assign the new item.

How do you perform a linked list append?

point tail's next pointer to the new node, then update the tail pointer.

What does FibonacciNumber(4) return?

3

What does FibonacciNumber(8) return?

21

What is the best-case time complexity of Insertion Sort and when does it occur?

O(N), when the list is already sorted.

What is the average/worst-case time complexity of Insertion Sort and why?

O(N²), due to nested loops (outer loop N-1 times, inner loop averages N/2 times).

Which sorting algorithms are easily adapted to linked lists?

Insertion Sort (works on doubly-linked lists; requires head-to-current search for singly-linked) and Merge Sort (must search linearly for middle; can merge without extra storage).

Which sorting algorithms are difficult for linked lists and why?

Shell Sort (cannot jump gaps),Quicksort (needs backward traversal for partitioning), and Heap Sort (requires indexed access for child nodes).

What is the fundamental challenge making array-based sorting algorithms difficult to adapt to linked lists?

"Elements in a linked list cannot be accessed by index".

What is a Stack?

A LIFO (Last In, First Out) data structure where push prepends to the head and pop removes/returns the head.

How is a Stack initialized when empty?

Head pointer = null

What is a Queue?

A FIFO (First In, First Out) data structure where push (enqueue) adds to the tail and pop (dequeue) removes from the head.

What are the operations of a Deque (Double-Ended Queue)?

PushFront, PushBack, PopFront, PopBack, PeekFront, PeekBack.

What is the Big-O complexity hierarchy from smallest to largest?

O(1) < O(log n) < O(n) < O(n log n) < O(n²).

What is the formula for the maximum number of Binary Search calls?

ceil(log2(n))