Data Structures.md

Array:

• Fixed size
• Contiguous memory block
• Constant time access

Efficiency

• Modifying: O(1)
• Find (using iterator or index): O(1)

Can't insert in middle since the size is fixed.

Deque

• Double ended queue container
• Efficient insertion and deletion at both front and back
• Dynamic resizing

Efficiency

• Inserting (at beginning or end): O(1)
• Find (using iterator or index): O(1)
• Insert in the middle (cus stuff is shifted): O(n)

Can insert in middle but stuff is shifted, better to use if you wanna only use from the start/back.

Forward List

• Singly-linked list
• Constant time insertion and deletion anywhere
• Only supports forward iteration
• Lacks direct access to elements by index

Efficiency

• Insert (adds to front): O(1)
• Find: O(n), does linear search
• Insert (in the middle): O(1) after finding the insertion point which could be O(n) if you use Find

Used when you need memory efficient and simple linked lists that support quick insertion and deletion and don't need random access.

List

• doubly-linked list
• constant time insertion and deletion anywhere.
• supports bidirectional iteration since EACH ELEMENT POINTS TO BOTH FORWARD AND BACK
• you can traverse from beginning to end and end from beginning. But this uses more memory.
• DIFFERENT BETWEEN FORWARD_LIST CUS IT HAS THE BACK POINTER SO IT HAS: push_back (add to end), pop_back (remove end), and stuff.

Efficiency

• Insert/Append: O(1)
• Find: O(n) linear search
• Insert: O(1)

Used when you need frequent insertions and deletions.

Map

• key-value pair in specific order
• unique keys, fast lookup insertion and deletion based on keys

Efficiency

• Insert: O(log n)
• Find: O(log n)

Use if you want to associate key value pairs with unique keys in a specific order.

Queue

• First in first out
• Insert at back and removed from front

Efficiency

• Insert (push): O(1)
• Access (front/back only using .front() or .back()): O(1)
• Remove (pop): O(1)

Middle insertion is impossible. Use when you need to maintain a sequence where its first in first out.

Set

• NIQUE elements in specific order, each element is its own key
• efficient lookup and sorted

Efficiency

• Insert: O(log n)
• Find: O(log n)
• Inserting in the middle isn't possible

Use if you need collection of unique sorted elements with fast lookup, insertion and deletion. Like when duplicates aren't allowed.

Stack

• Last in First Out
• llows elements to be added and removed only from the top of the stack.

Efficiency

• Insert (push): O(1)
• Access (top): O(1)
• Remove (pop): O(1)

Not possible to insert in the middle cus its LIFO.

Use for last in first out stuff like DFS.

Unordered Map

• Unordered using a hash table for fast retrieval
• Normal map uses a self balancing tree so its slow but its ordered.
• Unique keys, no duplicates
• Key-value pairs

Efficiency

• Insert: O(1)
• Find: O(1)

Ideal for key-value pairs where order of elements is not important. Used for implementing dictionaries or caches.

Unordered set

• Unique elements in unordered fashion
• Uses hash table

Efficiency

• Insert: O(1)
• Find: O(1)

Basically set but no order so its faster.

Vector

• dynamic array, which can change size
• ontiguous memory locations to store the elements

Efficiency

• Insert (at the end using push_back): O(1)
• Access (by index): O(1)
• Insert (in the middle): O(n) because need to shift elements
• Remove (from middle) O(n) because need to shift elements
• Remove (from end) O(1) using pop_back.

use when you need a dynamic array with fast random access and frequent additions/removals at the end of the sequence. basically any scenario where the number of elements can change frequently and order is important.