Free Data Structures and Algorithms Cheatsheet | CompSciLib

Home

Homework Help

Study Help

Roadmaps

Cheatsheets

Image to LaTeX

Courses

Contact

Data Structures and Algorithms Cheatsheet

Definitions, Symbols, Formulas, and Notes — All in One Place.

Show Shortcuts

Arrays

Term		Definition
Length		The total number of elements currently in the array.
Capacity		The maximum number of elements an array can hold.
Index		The number, usually starting with 0, pointing to an element's position within an array.
Array		A linear data structure consisting of a collection of elements, each identified by at least one index or key.

Array Operations

Term		Time Complexity
Insertion		$O (n)$
Deletion		$O (n)$
Resize		$O (n)$
Element Access		$O (1)$

Linked Lists

Linked List Operations

Term		Time Complexity
Insertion		$O (1)$
Deletion		$O (1)$
Element Access		$O (n)$

Queues

Queue Operations

Term		Time Complexity		Definition
Enqueue		$O (1)$		Insert an element at the front of the queue.
Dequeue		$O (1)$		Remove the element at the front of the queue.

Stack Properties

Stack Operations

Term		Time Complexity		Description
Pop		$O (1)$		Remove and return an element from the top of the stack.
Push		$O (1)$		Place an element at the top of the stack.
Peek		$O (1)$		Return the element at the top of the stack.

Trees

Binary Trees

Term		Definition		Time Complexity
Binary Tree		A tree in which each node has at most two children, referred to as the left child and the right child. These children are typically ordered, with one designated as the left child and the other as the right child.
Insertion				$Balanced: O (\log n)$ $Unbalanced: O (n)$
Deletion				$Balanced: O (\log n)$ $Unbalanced: O (n)$
Access Element				$Balanced: O (\log n)$ $Unbalanced: O (n)$
Finding Max/Min				$Balanced: O (\log n)$ $Unbalanced: O (n)$

AVL Trees

Term		Definition		Time Complexity
AVL Tree		A self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one. They maintain a balance factor for each node to ensure that the tree remains balanced after insertions and deletions. This balance property ensures that the height of the tree remains logarithmic.
Insertion		Insert a new node into an (already balanced) tree.		$O (\log n)$
Deletion		Remove a node from a balanced tree.		$O (\log n)$
Access Element		Access a node in a balanced tree.		$O (\log n)$

Red and Black Trees

Term		Definition		Time Complexity
Red and Black Trees		A type of self-balancing binary search tree. They maintain balance using a set of properties, including color coding of nodes and rotations to enforce balance during insertions and deletions. Red-black trees are designed to ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path.
Insertion		Insert a new node into an (already balanced) tree.		$O (\log n)$
Deletion		Remove a node from a balanced tree.		$O (\log n)$
Access Element		Access a node in a balanced tree.		$O (\log n)$

B Trees

Term		Definition		Time Complexity
B Tree		A self-balancing search tree where each node can have multiple keys and children, designed for efficient searching, insertion, and deletion operations in large datasets, commonly used in databases and file systems.
B+ Tree		An extension of a B-tree where all keys are present in the leaf nodes, and leaf nodes are linked in a linked list, optimized for range queries, sequential access, and efficient storage systems like databases.
Insertion		Insert a node into a balanced B/B+ tree.		$B Tree: O (\log n)$ $B+ Tree: O (\log n)$
Deletion		Delete a node from a balanced B/B+ tree.		$B Tree: O (\log n)$ $B+ Tree: O (\log n)$
Element Access		Access a node in a B/B+ tree.		$B Tree: O (\log n)$ $B+ Tree: O (\log n)$

Properties of Heaps

Heap Operations

Term		Time Complexity
Insertion		$O (\log n)$
Deletion		$O (\log n)$
Build Heap		$O (n)$
Heapify		$O (\log n)$
Find Minimum/Maximum		$O (1)$

Hash Tables

Term		Definition
Hash Table		A data structure that uses a hashing algorithm to map keys to indices in an array, allowing for efficient storage and retrieval of values associated with those keys, with the goal of minimizing collisions and optimizing access times.
Hashing Algorithm		In the context of hash tables, a function that takes an input and produces a valid integer index. The goal of a hashing algorithm is to distribute keys evenly across the available space, minimizing collisions and maximizing efficiency.
Collision		Occurs when two different keys hash to the same index in the underlying array or bucket.
Load Factor		The load factor of a hash table is a measure of how full the hash table is, expressed as the ratio of the number of stored elements $n$ to the total number of slots or buckets $m$ available. Calculated as $n / m$
Open Addressing		Resolves collisions by finding alternative slots within the table, often using methods like linear probing or quadratic probing.
Chaining		Resolves collisions by storing multiple key-value pairs hashing to the same index in linked lists or other data structures associated with each slot in the hash table.

Hash Table Operations

Term		Definition		Time Complexity
Insertion				$O (1)$
Deletion				$O (1)$
Resizing				$O (n)$

Graphs

Graph Algorithms

Term		Definition		Time Complexity
Djikstra's Algorithm		Used to find the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. It works by maintaining a set of vertices whose shortest distance from the source vertex is known. At each step, it selects the vertex with the smallest tentative distance (shortest distance from the source) from the set of vertices not yet processed, updates the distances of its neighboring vertices, and adds them to the set. This process continues until all vertices have been processed or the destination vertex is reached. Dijkstra's algorithm guarantees the shortest path from the source vertex to any other vertex as long as the graph doesn't contain negative edge weights.		$Priority Queue Implementation: O ((V + E) \log V)$ $Array Implementation O (V^{2})$
Bellman-Ford Algorithm		Used to find the shortest paths from a single source vertex to all other vertices in a weighted graph, even when some edge weights are negative. It works by iteratively relaxing the edges of the graph, i.e., updating the distance estimates of vertices by considering all possible paths of increasing lengths. It repeats this process for a maximum of \|V\| - 1 iterations, where \|V\| is the number of vertices in the graph. After the iterations, if there are no negative cycles in the graph, the algorithm guarantees the shortest paths from the source vertex to all other vertices. If a negative cycle is detected during the iterations, the algorithm reports it as unreachable.		$O (V E)$
Prim's Algorithm		Used to find the minimum spanning tree (MST) of a connected, undirected graph. It starts with an arbitrary vertex and grows the MST one edge at a time by always selecting the shortest edge that connects a vertex in the MST to a vertex outside the MST. It maintains two sets of vertices: one in the MST and one outside the MST. At each step, it chooses the edge with the minimum weight that connects a vertex in the MST to a vertex outside the MST, adding the newly connected vertex to the MST. This process continues until all vertices are included in the MST.		$Priority Queue Implementation: O ((V + E) \log V)$ $Array Implementation O (V^{2})$
Kruskal's Algorithm		Used to find the minimum spanning tree (MST) of a connected, undirected graph. It uses a greedy approach and edge sorting to build the MST. Initially, all edges of the graph are sorted by their weights. Then, starting with the smallest edge, the algorithm iteratively adds edges to the MST as long as they don't form cycles. It maintains a data structure (e.g., disjoint-set) to efficiently detect and avoid cycles. This process continues until all vertices are included in the MST.		$O (E \log E)$
Topological Sort		Used to linearly order the vertices of a directed acyclic graph (DAG) such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The algorithm works by repeatedly removing vertices with no incoming edges and adding them to the sorted list. It continues this process until all vertices have been removed. If the graph contains cycles, topological sorting is not possible because there is no valid ordering of the vertices.		$O (V + E)$

Dynamic Programming

Sorting Algorithms

Term		Definition		Time Complexity
Merge Sort		A comparison-based sorting algorithm that follows the divide-and-conquer strategy. It divides the array into smaller subarrays, recursively sorts them, and then merges the sorted subarrays to produce the final sorted array.		$O (n \log n)$
Insertion Sort		A simple comparison-based sorting algorithm that builds the final sorted array one element at a time by repeatedly moving elements that are out of order into their correct position.		$O (n^{2})$
Selection Sort		A simple comparison-based sorting algorithm that divides the array into sorted and unsorted regions. It repeatedly selects the smallest (or largest) element from the unsorted region and swaps it with the first element of the unsorted region.		$O (n^{2})$
Bubble Sort		A simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.		$O (n^{2})$

Searching Algorithms

Term		Definition		Time Complexity
Linear Search Sequential Search		Iterates through each element in a list or array sequentially until the target element is found or the end of the list is reached.		$O (n)$
Binary Search		A more efficient search algorithm for sorted arrays. It works by repeatedly dividing the search interval in half until the target element is found or the interval is empty.		$O (\log n)$
Depth-First Search		A graph traversal algorithm that explores as far as possible along each branch before backtracking. It is often implemented using recursion or a stack data structure.		$O (V + E)$
Breadth-First Search		A graph traversal algorithm that explores all the neighbor nodes at the present depth before moving on to the nodes at the next depth level. It is often implemented using a queue data structure.		$O (V + E)$

Tree Operations

Term		Definition		Time Complexity
Pre-Order Traversal		A depth-first tree traversal algorithm where each node is visited before its children. In a binary tree, the order of traversal is: root, left subtree, right subtree.		$O (n)$
Post-Order Traversal		A depth-first tree traversal algorithm where each node is visited after its children. In a binary tree, the order of traversal is: left subtree, right subtree, root.		$O (n)$
In-Order Traversal		A depth-first tree traversal algorithm where each node is visited between its left and right subtrees. In a binary tree, the order of traversal is: left subtree, root, right subtree.		$O (n)$

AI Study Tools for STEM Students Worldwide.

© 2025 CompSciLib™, LLC. All rights reserved.

info@compscilib.com Contact Us

Company

About Us Pricing AI Homework Help AI Study Help Roadmaps Cheatsheets Image to Text Tool Privacy Policy Terms of Use Accessibility Commitment

Courses

Computer Organization Discrete Math Linear Algebra Networking Statistics

Stay up to date

Instagram Discord Eventbrite TikTok Twitter LinkedIn Slack YouTube