Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data Structures - Coggle Diagram

- - - - Each node has atmost 2 children nodes
    - - Root/Parent node
      - Left child node
      - Right child node
    - - Depth First Search
        
        Inorder(Left-Root-Right)
        
        Preorder(Root-Left-Right)
        
        Postorder(Left-Right-Root)
      - Breadth First Search
        
        Level Order Traversal
    - - O(n)
  - - - Min Heap
        
        Root element is least
      - Max Heap
        
        Root element is highest
    - - Complete tree except last level(and last level all elements at left)
    - - Get Min/Max in Min/Max heap
        
        O(1)
      - Extract Min/Max in Min/Max heap
        
        O(log n)
      - Decrease key
        
        O(log n)
      - Insert
        
        O(log n)
      - Delete
        
        O(log n)
    - - Priority Queue, Dijikstra’s algorithm, Prim's graph algorithm
  - - - A function is required to map elements
    - - Search
        
        Average
        
        O(1)
        
        Worst
        
        O(n)
      - Insert
        
        Average
        
        O(1)
        
        Worst
        
        O(n)
      - Delete
        
        Average
        
        O(1)
        
        Worst
        
        O(n)
    - - Problems
        
        Collision can occur due to similar keys
      - Solution
        
        Chaining
        
        Open Addressing
    - - O(n)
  - - - Access/Search
        
        Quicker than linked list
        
        Slower than arrays
      - Insertion/Deletion
        
        Slower than linked list
        
        Quicker than arrays
    - - Root/Parent node
      - Left child node (Value less than parent)
      - Right child node (Value greater than parent)
    - - Depth First Search
        
        Inorder(Left-Root-Right)
        
        Preorder(Root-Left-Right)
        
        Postorder(Left-Right-Root)
      - Breadth First Search
        
        Level Order Traversal
    - - Search
        
        O(h)
      - Insertion
        
        O(h)
      - Delete
        
        O(h)
      - h is height of tree
    - - O(n) for pointers
- - - - Types
        
        Singly
        
        Doubly
        
        Circular
        
        Singly
        
        Doubly
      - Time Complexities
        
        Accessing Time
        
        O(n)
        
        Search Time
        
        O(n)
        
        Insertion Time
        
        O(1)
        
        Deletion Time
        
        O(1)
      - Information
        
        Conditions
        
        Similar elements
        
        Advantages
        
        Can't cause array overflow/underflow
        
        Disadvantages
        
        Memory allocation at run time
        
        Consumes more space than arrays
    - - Information
        
        Conditions
        
        Defined array size
        
        Similar elements
        
        Disadvantages
        
        Can cause array overflow/underflow
        
        Advantages
        
        Memory allocation at compile time
      - Time Complexities
        
        Search Time
        
        Sorted
        
        O(log n)
        
        Unsorted
        
        O(n)
        
        Insertion Time
        
        O(n)
        
        Deletion Time
        
        O(n)
        
        Accessing Time
        
        O(1)
  - - - Principle
        
        LIFO(Last In, First Out)
      - Conditions
        
        Operations from Top of Stack
      - Operations
        
        Push
        
        Insert element
        
        Pop
        
        Delete element
      - Time Complexities
        
        Accessing Time
        
        O(n)
        
        Insertion Time
        
        O(1)
        
        Deletion Time
        
        O(1)
    - - Principle
        
        FIFO(First In, First Out)
      - Conditions
        
        Operations from Front & Rear
      - Operations
        
        Enqueue
        
        Insert element from rear
        
        Dequeue
        
        Delete element from front
      - Time Complexities
        
        Accessing Time
        
        O(n)
        
        Insertion Time
        
        O(1)
        
        Deletion Time
        
        O(1)
      - Type
        
        Circular Queue(Array)
- - - - Set of vertices i.e., nodes
      - Set of ordered pair u,v i.e, edges
    - - Direction
        
        Directed
        
        Undirected
      - Weight
        
        Weighted
        
        Unweighted
    - - Adjacency Matrix
        
        Time
        
        O(V^2)
        
        Space
        
        O(V^2)
      - Adjacency List
        
        Time
        
        O(V+E)
        
        Space
        
        O(V+E)
      - V is vertices & E is edges
  - - - Insert
        
        O(M)
      - Search
        
        O(M)
      - Delete
        
        O(M)
    - - O(ALPHABET_SIZE * M * N)
    - - Advantages
        
        Better than hashing, no collisions
        
        Faster than BST
      - Disadvantage
        
        Requires lot of extra space
      - Also known as Radix or Prefix Tree