Collections

This is a brief, cursory overview of the different Data Structures used in hw7:

  1. array
    • Fixed size.
    • Once the array is full, cannot add unless you resize the array:
      1. Allocate a bigger array.
      2. Iterate through the original array and copy each element to the new memory.
      3. Update the reference to point to the new array.
    • Insert is expensive - need to iterate entire list and move each element down.
    • What about Delete?
    • What about Searching?
    • What about Sorting?
    • Uses a linear search function for insert and lookup, has O(n).

  2. ArrayList
    • System manages memory for you, so can add as many as needed.
    • Insert is expensive - need to iterate entire list and move each element down.
    • What about Delete?
    • What about Searching?
    • What about Sorting?
    • Uses a linear search function for insert and lookup, has O(n).

  3. HashMap
    • Key/Value pairs.
    • The key must be unique.
    • What about Delete?
    • What about Searching?
    • What about Sorting?
    • Uses a hashing function for insert and lookup, has O(1).

  4. LinkedList
    • System manages memory for you, so can add as many as needed.
    • Only use as much memory as needed: each element has data and a next pointer (reference).
    • Insert is less expensive - need to iterate entire list until found, then just reset the next pointers (references).
    • What about Delete?
    • What about Searching?
    • What about Sorting?
    • Uses a linear search function for insert and lookup, has O(n).

  5. Stack
    • Fixed size because typically implemented with an array.
    • Last-in-First-Out (LIFO).
    • Use push() to add an element onto the top of the stack.
    • Use pop() to retrieve the element at the top of the stack; the element is removed.