One Pager Cheat Sheet

• This cheat sheet provides a quick summary of time complexity of common array operations and a reminder on Big O notation.
• A Dynamic array, also known as an array list, list, growable array, resizable array, mutable array or dynamic table, is a type of array that can resize itself and provides constant time access with O(n) worst-case insertion (append) and deletion.
• A Linked List is a linear collection of elements ordered by links instead of physical placement in memory, featuring optimized operations for insertion and deletion but with costly access and search time complexity.
• A Queue is a FIFO data structure usually implemented on top of a linked list for O(1) enqueuing and dequeuing.
• A Stack is a sequential collection where elements are added and removed from the same end, making insertions and deletions O(1) but access and search O(n).
• A hash table is an unordered collection that maps keys to values using hashing for quick search, insertion and deletion with average time complexity O(1).
• A Graph is a data structure that stores items in a connected, non-hierarchical network, connected by edges, which can be directed or undirected, cyclic or acyclic, and weighted or unweighted.
• A Tree is a hierarchical data structure composed of nodes connected through links, which can be used for indexing files, syntax trees, comment threads, and more, with O(log(n)) average time complexity for most operations.
• A Binary Search Tree is a kind of binary tree where nodes to the left are smaller, and nodes to the right are larger than the current node.