Essential Data Structures and Algorithms: Concepts and Applications

Posted on Jan 23, 2025 in Computers

Data Structures and Data Types

Data Types: Represent the type of data (e.g., int, float, char). These are building blocks used to define variables in programming.

Data Structures: Ways to organize and store data to perform operations efficiently (e.g., arrays, stacks, queues, linked lists).

Key Difference: Data types are intrinsic to a language, while data structures provide functionality for organizing and managing data.

Abstract Data Type (ADT)

Abstract Data Type (ADT): A mathematical model for a data structure specifying its behavior without implementation details.

Stack (LIFO): Supports operations like push (add an element), pop (remove the top element), and peek (view the top element).

Queue (FIFO): Supports enqueue (add element at the rear) and dequeue (remove element from the front).

Basic Operations on Data Structures

Insert: Adding an element (e.g., inserting at the end of an array).

Delete: Removing an element (e.g., removing the top of a stack).

Traverse: Visiting each element (e.g., traversing a linked list).

Search: Finding an element (e.g., binary search in an array).

Example: In an array, inserting at the end is O(1), but inserting at the start is O(n) due to shifting.

Time-Space Trade-Off

Time-Space Trade-Off: The balance between memory usage and execution time.

Example:

  • Using hashing for fast lookups increases memory usage but reduces search time.
  • Using a recursive algorithm increases stack usage but simplifies the code.

Time Complexity and Space Complexity

Time Complexity: Measures how the runtime of an algorithm grows with input size.

Space Complexity: Measures memory usage during execution, including auxiliary and input storage.

Asymptotic Notations

Big O: Describes the worst-case growth rate of an algorithm.

Big Theta (Θ): Represents the average-case complexity.

Big Omega (Ω): Represents the best-case complexity.

Example: For sorting algorithms:

  • Merge Sort: Best, average, and worst-case are O(n log n).
  • Bubble Sort: Best-case O(n), worst-case O(n2).

Linear Search vs. Binary Search

Linear Search: Sequentially checks each element; O(n).

Binary Search: Divides the array into halves; O(log n).

Difference: Binary search is faster but requires a sorted array.

Example:

Array = [1, 3, 5, 7].

  • Linear Search: Checks 1 → 3 → 5 → 7.
  • Binary Search: Compares mid (5), narrows search to [1, 3].

Stack Operations with Time Complexity

Push: Add an element at the top (O(1)).

Pop: Remove the top element (O(1)).

Peek: View the top element (O(1)).

Stacks are implemented using arrays or linked lists.

Applications of Stack

  1. Infix to Postfix Conversion:

    Input: A+B*C.

    Output: ABC*+.

  2. Postfix Evaluation:

    Input: 23*5+.

    Output: 11 (compute 2 * 3, then add 5).

What is a Queue? Types of Queues

Queue: FIFO structure.

  1. Simple Queue: Processes in the order they arrive.
  2. Circular Queue: Rear connects to the front when the end is reached.
  3. Priority Queue: Processes elements by priority.

Operations on Queues

  1. Enqueue: Add an element at the rear.
  2. Dequeue: Remove an element from the front.
  3. Peek: View the front element.

Example:

Queue = [1, 2, 3].

Enqueue(4): [1, 2, 3, 4].

Dequeue(): [2, 3, 4].

Stack and Queue Representation in Memory

Stack: Linear representation using arrays or linked lists.

Queue: Array (linear or circular) or linked list for dynamic memory.

Linked List

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

Types of Linked Lists

  1. Singly Linked List: Nodes link in one direction.
  2. Doubly Linked List: Nodes link in both directions.
  3. Circular Linked List: Last node links back to the first.

Algorithms for Linked List Operations

  1. Insert at the beginning:

    NewNode.next = Head

    Head = NewNode

  2. Delete a node at position k: Traverse to k-1 and update pointers.

What is a Tree?

Tree: A hierarchical structure where each node has a parent (except the root) and may have children.

Binary Tree and Binary Search Tree (BST)

Binary Tree: Each node has up to two children.

BST: Binary tree with ordered elements (left < root < right).

Constructing a Binary Search Tree

Insert elements [10, 5, 15, 3, 7]:

    10
   /  \
  5    15
 / \
3   7

AVL Tree

A self-balancing BST where the height difference between subtrees is at most 1.

Rotations:

  • LL (Left-Left).
  • RR (Right-Right).
  • LR (Left-Right).
  • RL (Right-Left).

Difference Between BST and AVL Tree

BST: May become unbalanced, leading to O(n) operations.

AVL: Maintains balance, ensuring O(log n) operations.

Max Heap and Min Heap

Max Heap: Parent node is greater than or equal to children.

Min Heap: Parent node is less than or equal to children.

What is a B-Tree?

A self-balancing tree for large datasets, where nodes can have multiple keys and children.

Difference Between B-Tree and B+ Tree

B-Tree: Keys are stored in all nodes.

B+ Tree: Keys are stored in leaf nodes, making it efficient for range queries.

Sorting Algorithms

Selection Sort: Repeatedly selects the smallest element. O(n2).

Merge Sort: Divide and conquer; O(n log n).

Quick Sort: Partitioning; O(n log n).

Hashing

Definition: Maps keys to values using a hash function.

Techniques:

  • Chaining: Handles collisions using linked lists.
  • Open Addressing: Finds alternate slots.

Linear Probing vs. Quadratic Probing

Linear Probing: Searches next slot sequentially.

Quadratic Probing: Jumps based on square increments.

Graphs and Applications

Graph: A set of vertices and edges.

Applications:

  1. Shortest path algorithms (e.g., Dijkstra).
  2. Social networks.

Directed vs. Undirected Graph

Directed Graph: Edges have direction.

Undirected Graph: Edges are bidirectional.

Connected vs. Disconnected Graph

Connected: Every vertex is reachable.

Disconnected: Some vertices are isolated.

Graph Representation

  1. Adjacency Matrix: 2D array; O(V2) space.
  2. Adjacency List: List of neighbors; O(V + E) space.

Graph Traversal Algorithms

BFS: Visits level by level using a queue.

DFS: Visits depth-first using a stack or recursion.