Access Keys:
Skip to content (Access Key - 0)

Home

Skip to end of metadata
Go to start of metadata
Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.

Data Structures and Algorithms

Please visit https://docs.google.com/document/d/1HGDc3JF-k_nIMq41hyplcNEkXQPVh3UA1XimlU6VJ8w/edit for the most updated information. Some of the below run time are not correct here but are fixed in the Google Doc.

Data Structures

  • Unsorted Array
    • Insert @ Front: O(1)
    • Insert @ Arbitrary Spot: O(n)
    • Insert @ Given Spot: O(1)
    • Remove @ Front: O(1)
    • Remove @ Arbitrary Spot: O(n)
    • Remove @ Given Spot: O(n)
    • Find: O(n)
  • Sorted Array
    • Insert @ Front: O(n)
    • Insert @ Arbitrary Spot: O(n)
    • Insert @ Given Spot: O(n)
    • Remove @ Front: O(n)
    • Remove @ Arbitrary Spot: O(n)
    • Remove @ Given Spot: O(n)
    • Find: O(logn)
  • Singly Linked list
    • Insert @ Front: O(1)
    • Insert @ Arbitrary Spot: O(1)
    • Insert @ Given Spot: O(1)
    • Remove @ Front: O(1)
    • Remove @ Arbitrary Spot: O(n)
    • Remove @ Given Spot: O(1) w/ hack
    • Find: O(n)
  • Doubly Linked List
    • Insert @ Front: O(1)
    • Insert @ Arbitrary Spot: O(1)
    • Insert @ Given Spot: O(1)
    • Remove @ Front: O(1)
    • Remove @ Arbitrary Spot: O(n)
    • Remove @ Given Spot: O(1)
    • Find: O(n)
  • Stack - Last In First Out (LIFO), Pez dispenser
    • Array - Preferred because of their speed
      • Push: Amortized O(1) if we double size (and copy) each time we fill the current array.
      • Pop: O(1)
    • List
      • Push: O(1)
      • Pop: O(1)
  • Queue - First In First Out (FIFO), ticket line
    • Array - Preferred because of their speed
      • Enqueue: Amortize O(1) if we double size (and copy) each time we fill the current array.
      • Dequeue: O(1)
    • List
      • Enqueue: O(1)
      • Dequeue: O(1)
  • Trees
    • Binary Tree
      • Insert: O(1)
      • Remove: O(n)
      • Find: O(n)
      • Traverse: O(n)
    • Binary Search Tree
      • Insert: O(n)
      • Remove: O(n)
      • Find: O(h) were h = height of tree. At worse, O(n) if tree is a list.
      • Traverse: O(n)
    • AVL Tree (Balanced BST)
      • Insert: O(log n)
      • Remove: O(log n)
      • Find: O(log n)
      • Traverse: O(n)
    • BTree - block
      • Insert: O(log n)
      • Remove: O(log n)
      • Find: O(log n) 
      • Traverse: O(n)
  • Hash Table - For our purposes, if it's under SUHA and alpha is constant
    • Insert:O(1)
    • Remove: O(1)
    • Find: O(1)
  • Dictionary (Best = via Hash table)
    • Insert: O(1)
    • Remove: O(1)
    • Find: O(1)
  • Priority Queue (Best = via heap)
    • Insert: O(log n) 
    • Remove: O(log n)
  • Heap
    • Insert: O(log n)
    • Remove: O(log n)
  • DisjointSets (Best = via UpTrees)
    • w/o path compression and smart union
      • Find: O(n)
      • Union: O(1)
    • w/ smart union
      • Find: O(log n)
      • Union: O(1)
    • w/ smart union and path compression
      • Find: Basically O(1)
        • For any sequence of m union and find operations, the worst case running time is O(m log*(n)), where n is the number of items.
      • Union: O(1)
  • Graphs
n=vertices, m=edges Edge List Adjacency List Adjacency Matrix
Space O(n+m) O(n+m) O(n^2)
incidentEdges(v) O(m) O(deg(v)) O(n)
areAdjacent(v,w) O(m) O(min[deg(v), deg(w)]) O(1)
insertVertex(v) O(1) O(1) O(n^2); O(n) - amortized
insertEdge O(1) O(1) O(1)
removeVertex(v) O(m) O(deg(v)) O(n^2); O(n) - amortized
removeEdge O(1) O(1) O(1)
  • MinimumSpanningTree - MST

Algorithms

  • Singly linked list
  • insert/remove O(1)
    • remove abitrary O(n) due to find()
  • Array
    • insert front O(1)
    • insert at given O(1)
    • insert/remove given/arbitrary O(n) due to shift
  • Tree
    • Traversals
    • pre-order - act before processing children
    • in-order - act between processing children
    • post-order - act after processing children
  • Rotations
    • Left
    • Right
    • LeftRight
    • RightLeft
  • B-Tree Search O(mlogmN)
  • Hash Table
    • Collision handling
      • Separate Chaining
      • Linear Probing
    • SUHA(Simple Uniform Hashing Assumption)
    • Hash Function - Ideally Bipartite Function
  • Heap
    • HeapifyUp
    • HeapifyDown - faster because only one node needs to do LogN work
    • heapSort
  • DisjointSets
    • Find
    • Union
    • compress paths
    • union by size - smart union
  • Graphs
    • InsertVertex/Edge
    • RemoveVertex/Edge
    • IncidentEdges
    • areAdjacent
    • origin
    • destination
    • Kruskal
    • Prim
    • Dijkstra
    • Single Source Shortest Path - SSSP
    • Implementations with adjacency list vs. adjacency matrix
  • DepthFirstSearch - DFS - use recursion or stack
  • BreadthFirstSearch - BFS - use queue
Adaptavist Theme Builder (4.2.2) Powered by Atlassian Confluence 3.4.9, the Enterprise Wiki