Data Structures and Algorithms

Introduction

• Definition: A data structure is a named location that can store and organize data.
• Examples: Family tree (hierarchy), arrays (collection of elements at contiguous memory locations).
• Algorithms: Steps to solve a problem. Example: Recipe for cooking.
• Importance: Efficient code and common in coding job interviews.

Data Structures Covered

1. Stacks
2. Queues
3. Priority Queues
4. Linked Lists
5. Dynamic Arrays
6. ArrayLists vs LinkedLists
7. Trees
8. Graphs

Stacks

• LIFO: Last In, First Out.
• Methods: push (add to top), pop (remove from top), peek (view top), isEmpty, search.
• Examples: Undo/redo in editors, browser history, navigating mazes.

Queues

• FIFO: First In, First Out.
• Methods: enqueue (add to end), dequeue (remove from front), peek, isEmpty, size, contains.
• Examples: Printer queues, ticket lines, keyboard buffers.

Priority Queues

• Definition: Elements are served based on priority.
• Heap Property: Min-heap (smallest element at root) and max-heap (largest element at root).
• Use Cases: Scheduling tasks, Dijkstra’s algorithm.

Linked Lists

• Singly and Doubly Linked Lists: Singly (nodes have data and next pointer), Doubly (nodes have data, next and previous pointers).
• Methods: add, remove, indexOf, getFirst, getLast, isEmpty.
• Advantages and Disadvantages: Easy insertion/deletion but poor random access.

Dynamic Arrays

• Definition: Arrays with resizable capacity (e.g., ArrayList).
• Methods: add, insert, delete, search.
• Advantages: Random access, efficient memory usage.
• Disadvantages: Insertion/deletion in the middle takes time.

ArrayLists vs LinkedLists

• ArrayLists: Better for indexed access, less memory overhead.
• LinkedLists: Better for frequent insertions/deletions.
• Performance Tests: Access time, insert/delete time comparisons.

Trees

• Binary Trees: Each node has at most two children.
• Binary Search Trees: Ordered binary trees (left < root < right).
• Traversal Methods: In-order (left, root, right), Pre-order (root, left, right), Post-order (left, right, root).
• Use Cases: File systems, databases, hierarchical data representation.

Graphs

• Types: Directed and Undirected.
• Representations: Adjacency Matrix and Adjacency List.
• Traversal: DFS (stack-based), BFS (queue-based).
• Use Cases: Social networks, street maps, network topologies.

Algorithms

Searching Algorithms

1. Linear Search: Simple, checks each element. Complexity: O(n).
2. Binary Search: Requires sorted array, divide and conquer. Complexity: O(log n).
3. Interpolation Search: Improved binary search, best for uniformly distributed data. Complexity: O(log log n).

Sorting Algorithms

1. Bubble Sort: Compares and swaps adjacent elements. Complexity: O(n^2).
2. Selection Sort: Selects smallest and places it at the start. Complexity: O(n^2).
3. Insertion Sort: Builds sorted array one item at a time. Complexity: O(n^2).
4. Merge Sort: Divide and conquer, recursive. Complexity: O(n log n).
5. Quick Sort: Partition-based, recursive. Complexity: O(n log n) on average, O(n^2) worst case.

Efficiency Analysis

• Big O Notation: Describes the performance of algorithms as data size increases.
  • O(1): Constant time.
  • O(n): Linear time.
  • O(log n): Logarithmic time.
  • O(n^2): Quadratic time.
  • O(n log n): Quasi-linear time.
  • O(n!): Factorial time.

Graph Algorithms

• DFS (Depth-First Search): Uses stack or recursion; explores as far as possible before backtracking.
• BFS (Breadth-First Search): Uses queue; explores neighbors level by level.
• Common Uses: Pathfinding, connectivity testing, topological sorting.

Applications and Examples

• Real-World Examples: Social networks, file systems, browser history management, scheduling tasks, game development.