This is a brief, cursory overview of the different Data Structures used in hw7:
- array
- Fixed size.
- Once the array is full, cannot add unless you resize the array:
- Allocate a bigger array.
- Iterate through the original array and copy each element to the new memory.
- 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).
- 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).
- 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).
- 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).
- 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.