Please enable JavaScript.

Coggle requires JavaScript to display documents.

DS (Definition: A data structure is a way of organizing data so that it…

- - - - Space - Big-O Notation
        
        Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size become arbitrarily large
        
        n - The size of the input
        Complexities ordered from smallest to largest
        Complexities
        
        Complexities Examples:
        Greatest O(n)
        As shown in the above img -> Big(O) notation is always the greatest O(n) time complexity
        Note: A loop itself can be of constant time if it does have a fixed value to which it will loop through. Otherwise if the value changes then its not constant.
        O(1)
        O(n)
        O(log(n))
        O(n^2) OR O(n^2)
        O(n^4)
        Other variations
      - Space
  - - - Usage
        
        Storing and accessing sequential data
        
        Temporarily storing objects
        
        Used by IO routines as buffers
        
        Lookup tables and inverse lookup tables
        
        Can be used to return multiple values from a function
        
        Used in dynamic programming to cache answers to sub-problems
      - Example
        int[] values = {1,2,3};
        1.Object Header- int[] => 12 bytes (on 64 bit machines with compressed OOPS).
        
        Compressed ups makes the pointer to be small by making them 32 bit pointers. On the other hand it limits you to a maximum of 30GB of address space. But its faster than using 64 bit pointers consequently java program will work faster
        
        int length =>4 bytes
        
        Actual number in the array
        
        12 + 4 + (4 * 3) = 28 bytes total. This number have to be adjusted to the nearest 8 byte multiple which is 32 bytes
    - - ArrayList
        
        An array list doubles the capacity if the array length is equal or greater than the capacity
        
        How to count the memory needed ?
        List<Integer> al = new ArrayList<>(); 1_000_000
        1_000_000 * 4 + 12 + 4 + 64
        4 bytes = int
        12 bytes = object header
        4 bytes = array length
        64 - ArrayList object
      - LinkedList
        
        A linked list is a sequential list of nodes that hold data which point to other nodes also containing
        
        Usage
        
        Used in many Lists, Queue & Stack
        
        Great for creating circular lists
        
        Can easily model real-world objects such as trains
        
        Used in separate chaining, which is present certain Hashtable implementations to deal with hashing collisions.
        
        Often used in the implementation of adjacency lists for graphs.
        
        Terminology
        Head - The first node in a linked list
        Tail - The last node in a linked list
        Pointer - Reference to another node
        Node - An object containing data and pointer(s)
        
        Singly vs Doubly Linked List
        
        Singly linked list only hold a reference to the next node. In the implementation you always maintain a reference to the head to the linked list and the reference to the tail node for quick additions/removals
        
        With a doubly linked list each node holds a reference to the next and previous node. In the implementation you always maintain a reference to the head and the tail of the doubly linked list to do quick additions/removals from both ends of your list.
        
        Pros and Cons
        
        Singly LinkedList
        
        Pro
        . Singly linked list uses less memory.
        . Simpler implementation
        
        Cons
        . Cannot easily access previous elements
        
        Double LinkedList
        
        Pro
        . Can be traversed backwards
        
        Cons
        . Takes 2x memory
        
        Complexity Analysis
        Insert Complexity
        Remove Complexity