Data Structures Fundamentals

Data Structures

Arrays

• A collection of elements of the same data type stored in contiguous memory locations
• Each element is identified by an index or key
• Operations:
  • Access: O(1)
  • Insert: O(n)
  • Delete: O(n)

Linked Lists

• A collection of elements where each element points to the next element
• Each element is a separate object, and memory is allocated dynamically
• Operations:
  • Access: O(n)
  • Insert: O(1)
  • Delete: O(1)

Stacks

• A Last-In-First-Out (LIFO) data structure
• Operations:
  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)

Queues

• A First-In-First-Out (FIFO) data structure
• Operations:
  • Enqueue: O(1)
  • Dequeue: O(1)
  • Peek: O(1)

Trees

• A hierarchical data structure with nodes having at most two children (left and right)
• Operations:
  • Insert: O(log n)
  • Delete: O(log n)
  • Search: O(log n)

Graphs

• A non-linear data structure consisting of nodes and edges
• Operations:
  • BFS (Breadth-First Search): O(n + m)
  • DFS (Depth-First Search): O(n + m)

Algorithms

Sorting Algorithms

• Bubble Sort: O(n^2)
• Selection Sort: O(n^2)
• Insertion Sort: O(n^2)
• Merge Sort: O(n log n)
• Quick Sort: O(n log n)
• Heap Sort: O(n log n)

Searching Algorithms

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

Graph Algorithms

• Dijkstra's Algorithm: O(n log n + m)
• Floyd Warshall Algorithm: O(n^3)
• Topological Sort: O(n + m)

Dynamic Programming

• A method for solving complex problems by breaking them down into smaller subproblems
• Memoization: storing solutions to subproblems to avoid redundant computation
• Examples:
  • Fibonacci Series
  • Longest Common Subsequence

Data Structures

Arrays

• Collection of elements of the same data type stored in contiguous memory locations
• Each element identified by an index or key
• Operations have time complexities:
  • Access: constant time O(1)
  • Insert: linear time O(n)
  • Delete: linear time O(n)

Linked Lists

• Collection of elements where each element points to the next element
• Each element is a separate object, and memory is allocated dynamically
• Operations have time complexities:
  • Access: linear time O(n)
  • Insert: constant time O(1)
  • Delete: constant time O(1)

Stacks

• Last-In-First-Out (LIFO) data structure
• Operations have time complexities:
  • Push: constant time O(1)
  • Pop: constant time O(1)
  • Peek: constant time O(1)

Queues

• First-In-First-Out (FIFO) data structure
• Operations have time complexities:
  • Enqueue: constant time O(1)
  • Dequeue: constant time O(1)
  • Peek: constant time O(1)

Trees

• Hierarchical data structure with nodes having at most two children (left and right)
• Operations have time complexities:
  • Insert: logarithmic time O(log n)
  • Delete: logarithmic time O(log n)
  • Search: logarithmic time O(log n)

Graphs

• Non-linear data structure consisting of nodes and edges
• Operations have time complexities:
  • BFS (Breadth-First Search): linear time O(n + m)
  • DFS (Depth-First Search): linear time O(n + m)

Algorithms

Sorting Algorithms

• Bubble Sort: quadratic time complexity O(n^2)
• Selection Sort: quadratic time complexity O(n^2)
• Insertion Sort: quadratic time complexity O(n^2)
• Merge Sort: logarithmic time complexity O(n log n)
• Quick Sort: logarithmic time complexity O(n log n)
• Heap Sort: logarithmic time complexity O(n log n)

Searching Algorithms

• Linear Search: linear time complexity O(n)
• Binary Search: logarithmic time complexity O(log n)

Graph Algorithms

• Dijkstra's Algorithm: time complexity O(n log n + m)
• Floyd Warshall Algorithm: cubic time complexity O(n^3)
• Topological Sort: linear time complexity O(n + m)

Dynamic Programming

• Method for solving complex problems by breaking them down into smaller subproblems
• Memoization: storing solutions to subproblems to avoid redundant computation
• Examples include:
  • Fibonacci Series
  • Longest Common Subsequence