09-collections

CMPT 270: Developing Object Oriented Systems Java Collections

1. Learning Objectives

  • Understand the collection classes supplied in the Java library.

  • Learn how to choose the correct collection for a given problem.

  • Understand boxing and unboxing primitive datatypes in Java.

2. Efficiency

  • Importance of efficient storage when managing many objects.

  • Efficiency varies based on object usage.

  • Choosing the appropriate collection can significantly impact algorithm efficiency.

3. Data Structures in Java

  • Basic data structures provided by Java:

    • Array

    • LinkedList

    • ArrayList

    • TreeMap

    • HashMap

    • TreeSet

    • HashSet

4. Arrays

4.1 Characteristics

  • A single block of memory with a fixed number of values.

  • Values accessed by integer index; all values must be of the same type (primitive or reference).

  • A value can appear multiple times.

  • Not part of the Java Collections Framework.

4.2 Example
int [] myArray = new int[10];  // Declare an integer array of capacity 10
myArray[8] = 4;  // Store '4' in the 9th position

5. ArrayList

5.1 Characteristics

  • Dynamic memory allocation that can grow or shrink as needed.

  • All values must be of the same type (reference types only).

  • A value can appear multiple times. Often similar to Python Lists.

5.2 Example
ArrayList<String> myList = new ArrayList<String>();
myList.add("Hello");  // Add a String to the end of the ArrayList
System.out.println(myList.get(0));  // Access first element
5.3 Methods

  • Basic methods available in ArrayList:

    • add

    • get

    • remove

    • clear

    • isEmpty

    • size

    • And many more.

6. Efficiency: Arrays and ArrayLists

  • Indexing: O(1)

  • Linear Search: O(N)

  • ArrayList add()/remove(): O(N) in worst case due to copying unless from the end.

7. LinkedList

7.1 Characteristics

  • Sequence of values accessed in order; reference types only.

  • Allocates exactly as much space as needed.

7.2 Example
List<String> l = new LinkedList<String>();
// Can easily switch between LinkedList and ArrayList

8. Maps

8.1 Characteristics

  • Stores key-value pairs; organized by key for accessing values.

  • Java provides two types of Maps:

    • HashMap: Array-like.

    • TreeMap: Tree-like.

8.2 Example
Map<String, Color> favouriteColours = new HashMap<String, Color>();
favouriteColours.put("Jason", Color.RED);  // Add entry
Color c = favouriteColours.get("Jason");  // Look up entry
favouriteColours.remove("Jason");  // Remove entry

9. Hash Tables

9.1 Intuition

  • Example of student numbers as indices for a large array.

  • Suggests creating an array of suitable size with a function to convert indices to correct locations.

  • Collision handling strategy discussed but beyond course scope.

10. Using HashMaps

  • Java provides a built-in hash function, but custom classes should override hashCode and equals methods for better functionality.

11. Tree Concept

  • TreeMaps use a Red-Black Tree structure; custom keys require implementing Comparable interface for proper ordering.

12. Sets

  • An unordered collection that allows operations to store, remove, and check for values.

  • Two types of Sets available:

    • HashSet

    • TreeSet

13. Steps to Choosing a Collection

  1. Determine access method for values.

  2. Identify element or key/value types.

  3. See if order matters for elements or keys.

  4. Decide which operations should be efficient.

  5. If using Hash Sets/Maps, check for need to implement .equals() and .hashCode() methods.

  6. For trees, determine if a comparator is needed and implement Comparable if not present.

14. Primitive Data Types

  • Collections (except arrays) only store reference types. Need for primitive to be stored in collections leads to wrappers.

15. Wrappers and Auto-boxing

  • Java's wrapper classes for primitives allow them to be wrapped for collection usage. Example:

ArrayList<Integer> numbers = new ArrayList<Integer>();

  • Java auto-boxes and unboxes primitives for ease of use.

15.1 Auto-boxing Example
double x = 19.95;
ArrayList<Double> values = new ArrayList<Double>();
values.add(29.95);  // auto-boxing
values.add(x);      // auto-boxing
double y = values.get(0);  // unboxing

16. Summary

  • Java offers various collection types tailored for different problems.

  • Primitive types have corresponding wrapper classes to facilitate their use as reference types in collections.