Avi Mehenwal

# Data Structures

programmingfundamentalsdatastructures
Data Structure
A data structure is a format to store, manage and organize data in such a way that enables efficient data access and data modification.
ADT abstract data type
is a mathematical model for data types.

Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks.

Choice of data- structure selection to attack a problem seperates pros from mediocre porgrammers

ADT can themselves be implemented in a variety of ways

Abstraction ADT Implementation DS
List Dynamic Array
Linked list
Queue linked list
using Arrays
stack based
Map Tree map
Hash Map
Hash Table
Vehicle Golf cart
Bicycle
Smart car
# Some examples,
  1. Relational databases commonly use B-tree indexes for data retrieval
  2. while compiler implementations usually use hash tables to look up identifiers.

Usually, efficient data structures are key to designing efficient algorithms.

Abstraction levels on data

Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer—a bit string, representing a memory address, that can be itself stored in memory and manipulated by the program

# Data structure Types

There are numerous types of data structures, generally built upon simpler primitive data types:

  1. Linear data Structures
    1. can be traversed in singled run
    2. Examples
      1. Arrays
      2. Stacks
        1. LIFO
        2. FIFO
      3. Queues
  2. Non Linear data structures
    1. cannot be traversed in single run
    2. Examples
      1. Trees
      2. Graphs
      3. Linked lists
        1. sequence of nodes
        2. Dynamic Data structures
        3. Grow and shrink at run-time
  • What are Binary trees
  • Binary Heaps
  • Linear Search
  • Binary Search
    • Divide and conquer
  • Linear Sort
  • Difference between stacks and Queues
  • What are recursive algorithms
  • Sorting algorithms
    • Merge Sort
  • Heap vs Tree and Stack , Advantages and disadvantages

# Spanning Tree

  • Operations
    • Tree generations
    • Tree traversal
      • in-order
      • preorder
      • post-order
    • Tree searching
    • Tree modification
    • Node deletion
    • Balancing tree
  • Heaps
    • max heap
    • min heap
    • Operations
      • insertion
      • self-balancing
      • removal - pop from the root
      • Sorting
      • Heapify
    • Priority Queue

# Some good Questions

Major Takeaways before you leave

  1. What are Data Structures?
  2. Why are they important?
  3. What is the point of data structure?

← Graph →