Most problems can be approached with several different data structures, but the key is knowing how and when to use each possible option. Below are my notes on the basics of each relevant data structure/object.

 

String

Use case: When an immutable structure is appropriate

Methods:

• charAt(i)
• compareTo(s)
• contains(c)
• equals(o)
• indexOf(c || s)
• isEmpty()
• length()
• lastIndexOf(s)
• replace(c1,c2)
• split(p)
• substring(i1, i2)

 

StringBuilder

Use case: When you need to create a mutable character sequence

Methods:

• append(c || str)
• charAt(i)
• delete(i1, i2)
• indexOf(str)
• insert(i, str)
• substring(i)

 

Array

• Container of items
• Holds a fixed number of values of a single type
• Established length (fixed)

 

ArrayList

• Implemented via arrays
• When limit is reached, the array is doubled
• Cost is amortized

 

Hash[Map/Table]

• Array of Buckets (LinkedList of key value pairs encapsulated as Entry objects)
• Revolves around an array
• Function reduces the key to a number –> index in array
• Later, retrieve with same method
• Cheaper than a linear search
• Good for:
  • Put
  • Get
  • Contains
  • Remove
• Bad at anything else:
  • Iterating over elements
  • Sorting
  • Going from value to key
• Use cases:
  • Caching
  • Fast lookup

 

TreeMap:

To Be Completed

 

Queue

• FIFO
• Can be implemented as PriorityQueue
• Common uses:
  • Tree of graph traversal (breadth-first transversal)
• Methods:
  • boolean add(E e)
  • E peek() (null if not there)
  • E poll() (null if not there)

 

Stack

• LIFO
• Can be implemented as a singly linked list or array
• Common uses:
  • Method calls/ recursion
  • Parsing (e.g., bracket problems)
  • Tree or graph traversal (depth-first transversal)
• Methods:
  • boolean empty()
  • E peek()
  • E pop()
  • E push(E e)
  • int search(Object o)

 

Tree

A tree is a data structure composed of nodes.

• Each tree has a root node (usually)
• The root node has zero or more child nodes
• Each child node has zero or more child nodes, and so on

A tree cannot contain cycles.

 

Binary Search Tree

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Left and right subtree are also BST.
•  Node:
  • Key value
  • Left node
  • Right node

 

• Traversal:
  • Post-order (visit root last)
  • In-order
  • Pre-order
• Properties:
  • Balanced: Left and right subtrees are all about the same size
  • Complete: Every level is full (left to right) except for perhaps the last level
  • Full: Every node has either no child nodes or two child nodes
  • Perfect: Both full and complete
• Operations:
  • Insert: We start from the root node, if the node is less than the current node, go left, if the node is greater than the current node, go right. Continue until you can go no further and add the new node here.
  • Search: Similar algorithm to insert
  • Delete: Composed of three cases. The node to be deleted has:

1. No children: No extra work, just delete the node when it is found
2. One child: Delete the node and replace with the child node
3. Two children: 
   • Find minimum value in right subtree
   • Replace value of node to be removed with minimum value
   • Apply remove to right subtree to remove duplicate

 

Heaps

To be completed

 

Tries

To be completed

 

Graphs

• Types of representation:
  • Adjacency matrix
    • 2D array of size V x V
    • 1 for edge, 0 for no edge
    • Pro: Edge removal = O(1)
    • Con: More space
  • Adjacency list
    • Array of linked lists
    • Size of the array is equal to the number of vertices
    • The ith list holds adjacent nodes to ith vertex
• Depth-First Search –> recursion/ Stacks (allows to go deeper)
• Breadth-First Search –> Queue