Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data Structures - Coggle Diagram

- - - - Work like BSTs, only you also check to see if the node is balanced after you added the new node
      - This way we ensure we don't hit worst case scenarios
      - Our worst case becomes O(log n).
- - - - Dijkstra's algorithm
        
        Start at the beginning and end, and "spiral" outward
        
        mark each node with how far away it is from from its original Node
        
        As soon as the spiral intersect we know we've found the shortest possible path
  - - - The classic example of what you would use this for is autocomplete
      - A trie starts with a root node that doesn't represent anything
      - It has a bunch of child nodes (as many are necessary) that represent one letter, the first letter of all the words added to the data structure
      - Each of those letter-nodes will have children nodes for all the second letters of the words that are represented in the data structure.
      - So on and so forth, there will be a chain of nodes that represent each letter in the data structure.
  - - - think of Facebook's Social Graph
        
        X can be friends with Y, Y friends with Z, but X isn't friends with Z
- - - - made of a bunch of nodes that point to the next one in the list
      - Every node in a LinkedLists has two properties, the value of whatever is being store and a pointer to the next node in the list
      - These nodes will not be sequential in memory
      - Look Ups
        
        You only have access to a head node
        
        The head node will point to the 1 node
        
        The 1 node points to the 2 node, etc
        
        Big O is O(n) for lookups.
      - Deletions are O(1)
    - - Imagine there are no Arrays, only Objects
        
        we'll lay out everything sequentially in memory
        
        Since everything is already laid out in the order it's in memory, it makes look-ups really simple
        
        Just by knowing where the start of the array is and the index, we know where the thing we're looking for in memory
        
        O(1) in terms of complexity
- - - - Make the array a max heap
        
        heapify on the first half of the array, going backwards
      - Loop over the array / max array, dequeuing the root node, and swapping that with last item in the array
      - After dequeuing each item, run heapify again, once to find the next root node
      - Next loop you'll dequeue the root node and swap it with the second-to-last item in the array and run heapify again.
      - Once you've run out of items to dequeue, you have a sorted array