Data Structures (Quick Summary)

Data structures are ways to store and organize data in a computer so that it can be used efficiently for appropriate tasks.

1. Array & String

• What it is: Stores data contiguously in Memory
• Pros: Fast read access via Index O(1)
• Cons: Slow insertion/deletion in the middle O(n), fixed size (except Dynamic Array)

2. Linked List

• What it is: Nodes connected by Pointers ([Data|Next] -> [Data|Next])
• Pros: Fast insertion/deletion at the head or tail (if pointer exists) O(1), doesn't require contiguous Memory
• Cons: Slow search, must always traverse from the head O(n), wastes Memory storing Pointers

3. Stack & Queue

• Stack (LIFO): Last In, First Out (e.g., Undo, Back button, Call Stack).
  • Push/Pop = O(1)
• Queue (FIFO): First In, First Out (e.g., Print queue, Message queue).
  • Enqueue/Dequeue = O(1)

4. Hash Table (Hash Map)

• What it is: Stores data in Key-Value pairs, using a Hash Function to convert the Key into an Index
• Pros: Average search, insertion, deletion is O(1)
• Cons: If Collisions occur frequently, it can degrade to O(n)

5. Tree

• What it is: Hierarchical structure (Root, Node, Leaf)
• Binary Search Tree (BST): Left < Self < Right. Fast search O(log n) (if the Tree is balanced)
• Heap: (Min/Max) The topmost element has the minimum/maximum value. Good for Priority Queue. O(log n) for insertion/extraction

6. Graph

• What it is: Nodes (Vertex) connected by lines (Edge)
• Stored using: Adjacency Matrix (O(V^2) space) or Adjacency List (O(V + E) space)
• Use cases: Social networks, GPS maps, Computer networks