Data Structures and Algorithms Overview

Data Structures

Overview of Data Structures

  • Data structures are ways of organizing, storing, retrieving, and processing data in programming.
  • Essential for efficient problem-solving and algorithm design.

Types of Data Structures

  • List: A collection of ordered elements, dynamic in size. Can contain duplicates and supports multiple operations (insertion, deletion).
  • Tuples: Immutable collections of ordered elements. Once created, cannot be changed, used for fixed records or returning multiple values from functions.
  • Sets: Unordered collections of unique elements, no duplicates allowed. Useful for operations like union, intersection, and difference.
  • Dictionaries: Collections of key-value pairs with unique keys for fast access; supports mutable and ordered data.
  • Stacks: Follow Last In First Out (LIFO) principle. Operations include push, pop, and peek.
  • Queues: Follow First In First Out (FIFO) principle. Operations include enqueue and dequeue.
  • Trees: Hierarchical structure with nodes connected by edges, used for various search algorithms.
  • Graphs: Collections of nodes connected by edges, useful in network routing.

Lists

  • Definition: Ordered collections that can grow and shrink dynamically.
  • Common Methods:
    • append(): Add item to end.
    • clear(): Remove all items.
    • copy(): Returns a shallow copy.
    • insert(): Adds item at specified position.
    • pop(): Removes item at specified position.
    • sort(): Sorts list.
  • Use Case: Storing sequences like user inputs.

Tuples

  • Definition: Immutable ordered collections.
  • Common Methods:
    • count(): Counts instances of a value.
    • index(): Returns the index of a value.
  • Use Cases: Used for returning multiple values or fixed data collections.

Sets

  • Definition: Unordered, unique collections.
  • Characteristics: Cannot contain duplicates and supports various operations for mathematical set handling.
  • Common Methods:
    • add(): Adds an element.
    • remove(): Removes specified element.
    • union(): Combines sets.
  • Use Cases: Membership testing, removing duplicates.

Dictionaries

  • Definition: Collections of key-value pairs, where keys are unique.
  • Common Operations:
    • get(): Retrieve value by key.
    • update(): Add or modify key-value pairs.
    • pop(): Remove item by key.
    • items(): Return key-value pairs.
  • Use Case: Configuration management, associative arrays.

Stacks

  • Definition: Data structure following LIFO principle.
  • Methods:
    • push(): Adds item to the top.
    • pop(): Removes item from the top.
    • peek(): Returns the top item without removing.
  • Use Cases: Undo operations, function call management.

Queues

  • Definition: Data structure following FIFO principle.
  • Methods:
    • enQueue(): Adds item to the back.
    • deQueue(): Removes item from the front.
    • peek(): Returns the front item without removing.
  • Use Cases: Task scheduling, handling requests.

Sorting Algorithms

  • Definition: Arrange elements in order (ascending or descending).
  • Common Types:
    • Bubble Sort: Simple comparison algorithm, needs multiple passes.
    • Selection Sort: Grows sorted part of the list with minimum selections.
    • Insertion Sort: Builds a sorted array one element at a time.
  • In-built Functions: sort() (in-place), sorted() (returns new list).

Searching Algorithms

  • Definition: Finding a specific element in a collection.
  • Types:
    • Linear Search: Compares each element sequentially, less efficient.
    • Binary Search: More efficient, requires sorted array, divides search interval in half.