Data Structures Flashcards
Array
A fixed size contiguous block of memory to store elements of the same data type
Linked List
A linear data structure that consists of a series of nodes connected by pointers
Queue
A linear data structure that follows the principle of First In First Out (FIFO)
Stack
A linear data structure that follows the principle Last In First Out (LIFO)
Hash Map
An unordered collection of data that stores elements in key-value pairs
Tree
Nonlinear hierarchical data structure that consists of nodes connected by edges
Binary Tree
A tree where each node can have at most two children
Full Binary Tree
A binary tree where every node has either two children or none
Perfect Binary Tree
Binary tree where every parent has two children nodes and all the leaf nodes are on the same level
Degenerate / Pathological Tree
Binary tree where each parent has one child
Skewed Binary Tree
A degenerate / pathological tree but with all left nodes or all right nodes
Balanced Binary Tree
Binary tree where the difference between the height of the left sub tree and the right subtree for each node is either 0 or 1
Array Insert Time Complexity
O(n)
Array Insert (at the end) Time Complexity
O(1)
Array Delete Time Complexity
O(n)
Array Delete (at the end) Time Complexity
O(1)
Max Heap
A complete binary tree where every node is always greater than its child node(s)
Min Heap
A complete binary tree where every node is always smaller than its child node(s)
Array Access Time Complexity
O(1)
Array Search Time Complexity
O(n)
Linked List Access Time Complexity
O(n)
Linked List Search Time Complexity
O(n)
Linked List Insert (at position) Time Complexity
O(n)
Linked List Delete (at position) Time Complexity
O(n)
Stack Search Time Complexity
O(n)
Stack Insert (Push) Time Complexity
O(1)
Stack Delete (Pop) Time Complexity
O(1)
Queue Search Time Complexity
O(n)
Queue Insert (Enqueue) Time Conplexity
O(1)
Queue Delete (Dequeue) Time Complexity
O(1)
