Data Structures - robbiehume/CS-Notes GitHub Wiki

Sets vs Lists / Arrays vs Dictionary / Map

Sets: Use for fast lookups, uniqueness, and when order doesn’t matter. Typically, choose a set for tasks like filtering, membership testing, or enforcing uniqueness
Lists: Use when order and indexing matter, or when you need to allow duplicates. Lists are generally better for ordered collections and scenarios where you need to frequently access elements by position

Feature	Set	List / Array	Dictionary / Map
Time Complexity	O(1) for membership checking, adding, and removing (average case).	O(n) for membership checking and removal. O(1) for appending.	O(1) for adding, accessing, and removing elements by key.
Space Complexity	O(n); Requires more memory due to hashing.	O(n); Requires less memory compared to sets, as no hashing is involved.	O(n); Requires more memory due to hashing of keys.
When to Use	When uniqueness and fast lookups are important (e.g., membership tests).	When order matters, or you need to maintain duplicates or access elements by index.	When you need fast lookups based on keys and associated values.
Common Operations	- Add: O(1) - Remove: O(1) (average) - Membership check: O(1)	- Add: O(1) (for append) - Remove: O(n) - Membership check: O(n)	- Add/Update: O(1) - Remove: O(1) - Lookup by key: O(1)
Mutability	Mutable (can add/remove elements).	Mutable (can add/remove/modify elements).	Mutable (can add/remove/modify elements by key).

Feature	Stack	Queue
Insertion	Elements are added to the top of the stack using `push()`.	Elements are added to the end of the queue using `enqueue()`.
Removal	Elements are removed from the top using `pop()`.	Elements are removed from the front using `dequeue()`.
Common Use Cases	- Undo functionality (e.g., Ctrl+Z) - Function call stacks in programming - Parsing expressions	- Task scheduling (e.g., printer jobs) - Breadth-first search in algorithms - Handling real-time data streams (e.g., message queues)
Time Complexity	- Insertion: O(1) - Removal: O(1) - Access: O(n) (no direct access to middle elements)	- Insertion: O(1) - Removal: O(1) - Access: O(n) (no direct access to middle elements)
Space Complexity	O(n) where `n` is the number of elements in the stack.	O(n) where `n` is the number of elements in the queue.
Order of Processing	LIFO (Last element added is the first to be removed).	FIFO (First element added is the first to be removed).
Real-World Analogy	A stack of plates: The last plate added is the first one taken off.	A line at a checkout: The first person in line is served first.

A trie (pronounced "try") is a type of tree data structure that is used to efficiently store and retrieve keys in a dataset of strings
It is particularly well-suited for applications that involve prefix matching, such as autocomplete, spell-checking, or searching for common prefixes
- It is also known as a prefix tree because it stores keys by their prefixes

Nodes are the individual elements
- Also called vertices in graphs
Edges connect these nodes
Root node: the top most node with no parent
Leaf nodes: nodes with no children
- In DSA, it's common to refer to leaf nodes as external nodes and all others as internal nodes
Tree relationships: parent, child, sibling
Depth of a node: the number of edges required to each a particular node from the root node
Height of a node: the length of the longest path from that node to a descendant leaf node
Degree of a node: the number of children that node has
- Degree of a tree is the maximum degree of any node in the tree
Level of a tree:
- Level 0: root node
- Level 1: nodes directly connected to the root
- Level 2: direct child nodes of nodes in level 1
- Etc.
Subtree: a portion of a tree that is derived from a specific node
- This node is known as the subtree root
Forest: a set of non-interacting trees
- You can create a forest by removing certain nodes from a tree

A node object stores three attributes:
- The data element
- A reference to the parent node
- A single container of references to its children, since one node can have multiple children