📘 DSA Basic Notes

Data Structures & Algorithms – Quick Revision Sheet

📌 1. What is DSA?

Data Structures and Algorithms (DSA) is the study of organizing data efficiently and solving problems using step-by-step procedures.

🧠 2. Time & Space Complexity

• Time Complexity: Measures execution time (Big-O notation)
• Space Complexity: Measures memory usage

Common complexities:

• O(1) → Constant
• O(log n) → Logarithmic
• O(n) → Linear
• O(n²) → Quadratic

📊 3. Basic Data Structures

📍 Arrays

Collection of elements stored in continuous memory locations.

📍 Linked List

Elements stored in nodes, each pointing to the next node.

📍 Stack (LIFO)

Last In First Out. Example: Undo operation.

📍 Queue (FIFO)

First In First Out. Example: Ticket counter.

📍 Hash Table

Stores key-value pairs for fast access.

📊 Basic Data Structures Detailed

📍 Arrays

Definition: Arrays are collections of elements stored in contiguous (continuous) memory locations.

• Key Features:
  • Fixed size
  • Fast access using index (O(1))
  • Stores same data type elements
• Example (Java):

  
  int[] arr = {10, 20, 30};
  System.out.println(arr[0]); // Output: 10
      

• Example (Python):

  
  arr = [10, 20, 30]
  print(arr[0])
      

• Advantages: Fast access, simple structure
• Disadvantages: Fixed size, costly insertion/deletion

📍 Linked List

Definition: A collection of nodes where each node contains data and a reference (pointer) to the next node.

• Types: Singly, Doubly, Circular Linked List
• Example (Concept):

  
  [10] → [20] → [30] → NULL
      

• Example (Python):

  
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
      

• Advantages: Dynamic size, easy insertion/deletion
• Disadvantages: More memory (pointers), slower access (O(n))

📍 Stack (LIFO)

Definition: Stack follows Last In First Out (LIFO) principle.

• Operations: push (insert), pop (remove), peek (top element)
• Real-Life Example: Undo operation, plates stack
• Example (Java):

  
  Stack stack = new Stack<>();
  stack.push(10);
  stack.push(20);
  stack.pop(); // removes 20
      

• Example (Python):

  
  stack = []
  stack.append(10)
  stack.append(20)
  stack.pop()
      

• Time Complexity: O(1) for push/pop

📍 Queue (FIFO)

Definition: Queue follows First In First Out (FIFO) principle.

• Operations: enqueue (add), dequeue (remove)
• Real-Life Example: Ticket counter, waiting line
• Example (Java):

  
  Queue queue = new LinkedList<>();
  queue.add(10);
  queue.add(20);
  queue.remove(); // removes 10
      

• Example (Python):

  
  from collections import deque
  
  queue = deque()
  queue.append(10)
  queue.append(20)
  queue.popleft()
      

• Time Complexity: O(1)

📍 Hash Table

Definition: A data structure that stores key-value pairs and provides fast access using hashing.

• Key Concept: Hash function maps keys to index
• Example (Java):

  
  HashMap map = new HashMap<>();
  map.put("A", 1);
  map.put("B", 2);
  System.out.println(map.get("A"));
      

• Example (Python):

  
  data = {"A": 1, "B": 2}
  print(data["A"])
      

• Advantages: Very fast lookup (O(1) average)
• Disadvantages: Collision handling needed

🔁 4. Basic Algorithms

🔍 Searching

• Linear Search → O(n)
• Binary Search → O(log n)

🔃 Sorting

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort → O(n log n)

🧩 5. Important Concepts

• Recursion
• Greedy Algorithms
• Dynamic Programming
• Backtracking

⚡ Quick Tips

• Always analyze time complexity before coding
• Practice problems daily (LeetCode / Codeforces)
• Understand logic, don’t memorize solutions

🚀 Keep learning. Keep building. Keep improving.