[DATA STRUCTURE & Other Objects Using JAVA] Chapter 3 Collection Classes

3.0 Introduction

  • Collection class: A collection class is a class in which each object contains a collection of elements.

3.1 A Review of Java Arrays

  • Array can be built for fixed data type.
  • Declare an array

  • Name is scores, and the components of this array are integers.

  • Create an array

  • An array can also be declared and allocated with a single statement.

  • Instead of specifying an actual size with the new operator, another alternative is to provide a list of initial values.

3.1.1 Exceptions that Arise from Arrays

  • NullPointerException: trying to use an array variable before the array has been allocated.

  • ArrayIndexOutOfBoundsException: trying to access an array outside of its bounds.

3.1.2 The Length of an Array

Every array has an instance variable called length, which tells the number of components in the array.

If an array variable is the null reference, you cannot ask for its length.

3.1.3 Assignment Statements with Arrays

  • A program can use an assignment statement to make two array variables refer to the same array.

  • There is only one array, and both array variables refer to this one array.

  • Any change to the array will affect both scores and exams.

3.1.4 Clones of Arrays

Changes to the original array don’t affect the clone, and changes to the clone don’t affect the original array either.

3.1.5 The Arrays Utility Class

  • Utility class: In Java, a utility class is a class that provides methods that are intended to help you manipulate objects from some other other class.
  • Generally, these utility methods are static methods of the utility class, meaning that they can be used without being activated by any other particular object.
  • Arrays.copyOf(): provides an alternative way to make a clone of an array

  • Arrays.copyRange(short[] original, int from, int to): copies a section of one array into a newly created array

    • from — This is the initial index of the range to be copied, inclusive.
    • to — This is the final index of the range to be copied, exclusive.
  • Arrays.fill(): fills a given array with a specified value.

3.1.6 Array Parameters

When a parameter is an array, then the parameter is initialized to refer to the same array that the actual argument refers to. Therefore, if the method changes the components of the array, the changes do affect the actual argument.

3.1.7 Enhanced for-loop for Arrays

This form of the for-loop is called iterating over an array.

3.2 An ADT for a Bag of Integers

  • (int... elements): means that the method can be called with any number of integer arguments.

  • Variable arity method

3.2.1 OutOfMemoryError and Other Limitations for Collection Classes

  • The memory for any array comes from a location called the program’s heap (also called the free store). In fact, the memory for all Java objects comes from the heap.
  • OutOfMemoryError: If a heap has insufficient memory for a new object or array, then the result is a Java exception called OutOfMemoryError.
  • Any method that uses the new operation could throw the OutOfMemoryError.
  • Integer.MAX_VALUE: 2,147,483,647

3.2.2 The IntArrayBag Class — Specification

Field

Constructor

Method

3.2.3 The IntArrayBag Class — Demonstration Program

  • Sentinel value: Using a special value to end list is a common technique; this value is called a sentinel value.

3.2.4 The IntArrayBag Class — Design

  • Invariant of the ADT: The rules that dictate how the instance variables of a class represent a value are called the invariant of the ADT.

3.2.5 The IntArrayBag Class — Implementation

  • When the method is activated, the Java runtime system will take the actual arguments and put them in an array that the implementation can access with the parameter name elements.

  • Copy the source array to the destination array

  • Short-circuit evaluation: a boolean expression is evaluated from left to right, and the evaluation stops as soon as there is enough information to determine the value of the expression.

  • The problem of calling super.clone() occurs because super.clone() copies each instance variable of the class without concern of whether the instance variable is a primitive type or a more complicated type. Reference variables will still refer to the objects that owned by the original copy. Thus extra work is needed, which is calling clone() on each reference variable.

3.2.5 The IntArrayBag Class — Analysis

  • In Java all array components are initialized (integers are set to zero).
  • When the time required by a method does not depend on the size of the input, the procedure is called constant time, which is written O(1).

3.5 The Java HashSet and Iterators

HashSet has a feature called the iterator, which permits a programmer to easily step through all the elements of a collection.

3.5.1 The HashSet Class

  • A HashSet stores references to objects rather than storing primitive values.
  • A HashSet cannot contain two objects that are equal.

  • The name of the data type is HashSet, but this name is augmented by <String> to indicate the type of elements that will reside in the set.

  • This augmentation is called a generic type instantiation.

3.5.2 Some of the HashSet Members

Constructors

When you declare a HashSet, you must specify the type of elements that reside in the set, such as the String in HashSet<String>.

Members That Are Similar to the Bag

E must be the data type of the elements in the HashSet.

Iterators

  • An iterator is an object from java.util.Iterator that permits a programmer to easily step through all the items in a container, examining the items and changing them.
  • It’s a programming error to active it.next() when it.hasNext() returns false.
  • Changes to the collection—either additions or removals—can cause all of the collection’s iterators to become invalid.
  • When an iterator becomes invalid because of a change to its container, that iterator can no longer be used until it is assigned a new value.

Leave a Reply

Your email address will not be published. Required fields are marked *