[DATA STRUCTURE & Other Objects Using JAVA] Chapter 5 Generic Programming

5.1 Java’s Object Type and Wrapper Classes

  • Java has an important built-in data type called Object. AnObject variable is capable of holding a reference to any kind of object.

5.1.1 Widening conversion

Suppose x and y are reference variables. An assignment x = y is a widening conversion if the data type of x is capable of referring to a wider variety of things than the type of y.

5.1.2 Narrowing conversion

Suppose x and y are reference variables, and x has a smaller ability to refer to things than y. A narrowing conversion using a typecast can be made to assign x from y.

Narrowing conversions also occur when a method returns anObject and the program assigns that Object to a variable of a particular type.

5.1.3 Wrapper Classes

  • Wrapper class: A wrapper class is a class in which each object holds a primitive value.
  • Boxing conversion: placing an integer into an Integer object.
  • Unboxing conversion: taking back out an integer form an Integer object.

5.2 Object Methods and Generic Methods

Object Methods

There are some potential type errors that can’t be caught until the program is running.

Generic Methods

A generic method is a method that is written the types of the parameters not fully specified.

  • T is called the generic type parameter.
  • Single capital letters such as T for “type”, and E for “element”.
  • The generic type parameter always appears in angle brackets right before the return type of the method.
  • When a generic method is activated, the compiler infers the correct class for the generic type parameter.
  • A generic method allows any class for the argument, and the compiler can detect certain type errors.
  • The generic type parameter is similar to id in Objective-C.
  • Generic methods with more than one generic type parameter.

  • The data type inferred by the compiler for the generic type must always be a class type.

  • You may not call a constructor for the generic type, nor may you create a new array of elements of that type.

5.3 Generic Classes

5.3.1 Writing a Generic Class

When an entire class depends on an underlying data type, the class can be implemented as a generic class, resulting in the same typechecking advantages that you have seen for generic methods.

  • The single capital letter ‘E’ indicates that it is the unknown class of an “element” in the bag.
  • Programs cannot creates arrays where the components are the generic type parameter.

5.3.2 Using a Generic Class

  • A program that wants to use a generic class must explicitly specify what class will be used for the generic type parameter. This process is called instantiating the generic type parameter.

  • You cannot add a String object to a bag of Integer objects.

5.3.3 Creating an Array to Hold Elements of the Unknown Type

  • Within the generic class implementation, we are not allowed to create a new array of objects of the unknown type E.
  • The solution is to declare data as an array of Java Objects.

5.3.4 Retrieving E Objects from the Array

Whenever we retrieve a component of the array, we must apply a typecast to the type E.

This typecast (E) is one of several places where Java compilers issue warnings about possible errors that can occur at run time.

5.3.5 Warning in Generic Code


During the runtime, the information about the actual data type of a generic object is always unavailable. Therefore there is no way for the program to check whether the typecast is correct. The warning that Java produces in this situation is an “unchecked cast” warning. This means that if the typecast is illegal at run time, then the error will not be caught as it usually is.

Variable Arity Methods

Variable arity methods will cause the compiler to create an array of generic object, which usually is forbidden because it can result in unchecked typecast errors.

Suppressing Unchecked Warnings

There is no semicolon after this annotation, and the line can be placed by itself just prior to any method declaration.

  • Available since Java 1.7
  • It can suppresses both warning at the declaration of the variable arity method and the warning that sometimes occur when the variable arity method is activated.
  • Only available to static or final methods.

5.3.6 Using ArrayBag as the Type of a Parameter or Return Value

All the uses of the ArrayBag data type within its own implementation will be written as ArrayBag<E>.

5.3.7 Generic Collections Should Use the equals Method

When a generic collection tests for the presence of a non-null elements, it should generally use the equals method rather than the == operator.

5.3.8 Set Unused Reference to null

When a collection class is converted to a generic collection class, make sure any unused reference variables are set to null. This usually occurs in methods that remove elements from the collection. Setting these variables to null will allow Java to collect any unused memory.

5.3.9 Steps for Converting a Collection Class to a Generic Class

1. The Name of the Class

  • Convert all IntArrayBag to ArrayBag<E>.
  • The name of the constructor is just ArrayBag.

2. The Type of the Data Array

3. The Type of the Underlying Element

Find all the remaining spots where the old classes used int to refer to an element in the bag, and change them to the generic type parameter.

4. Change Static Methods to Generic Static Methods

Any static method that depends on the generic type E must be changed to a generic method, which means that <E> appears just before the return type in the method’s heading.

5. Use Typecasts When an Element Is Retrieved from the Array

return (E)data[i];

6. Suppress Warning

Some code in generic collection classes generates “unchecked” warnings. Examine each of these spots and suppress the warning.

7. Updated Equality Tests

Use the method equals() instead of ==.

8. Decide How to Treat the null Reference

  • Allow the null reference to be placed in the bag, and indicate this in the documentation.
  • Some of the bag’s methods will need special cases to deal with null references.
  • Such as the countOccurrences() will search for a null target using “==”, but non-null target is counted by using its equals method.

9. Set Unused Reference Variable

10. Update All Documentation

5.4 Generic Nodes

  • In general, the equals method may be used only when you know that the target is non-null.
  • When the purpose of a boolean expression is to test whether two references refer to the exact same object, then use the “==” or “!=” operator.

5.5 Interfaces and Iterators

  • A Java interface is primarily a list of method that a programmer may want to implement in a single class.
  • A class that has implemented the methods of a interface is said to implement the interface.

5.5.1 How to Write a Class That Implements an Interface

1. Read the documentation that is provided for the interface.

2. Tell the compiler that you are implementing an interface.

  • The keyword implements informs the compiler that you are implementing the interface.
  • If a class implements several difference interfaces, then the names of the interface appear one after another, separated by comma.

3. Implement the class in the usual way.

Make sure that each of the specified methods is implemented.

5.5.2 Generic Interfaces and the Iterable Interface

  • A generic interface specifies a list of methods that depend on one or more unspecified classes.
  • Interface Iterator<E>

  • remove() removes the element that was given by the most recent call to next().

  • Sometimes an iterator does not allow elements to be removed. In this case, activating the remove() method results in an UnsupportedOperationException.

5.5.3 The Comparable Generic Interface

  • Java has a generic interface called Comparable<T> that requires just one method:

  • x.compareTo(y): The method returns an integer that is negative (if x is less y), zero (if x and y are equal), or positive (if x is greater than y).

5.5.4 Parameters That Use Interfaces

When an interface name is used as the type of a method’s parameter, the actual argument must be a data type that implements the interface.

5.5.5 Using instanceof to Test Whether a Class Implements an Interface

variable instanceof interface-or-class-name

5.5.6 The Cloneable Interface

  • There are no methods specified in the Cloneable interface. (What the fuck?!)
  • object.clone()

    1. Check to see whether the class has implemented the Cloneable interface. If not, a CloneNotSupportedException is thrown.
    2. Otherwise, the clone is make by copying each of the instance variable of the original.

5.7 The Java Collection Interface and Map Interface

Map: A map is a collection class in which key/value pairs may be added. A pair can be retrieved or removed by specifying just its key. This is similar to NSDictionary in Objective-C.

[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




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


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.


  • 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.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 2 Java Classes and Information Hiding

2.0 Introduction

  • Object-oriented programming is an approach to programming in which data occurs in tidy packages called objects.
  • The separation of specification from implementation is an example of information hiding.
  • ADT (abstract data type): In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. (from wikipedia)

2.1 Classes and Their Members

  • Member: Taken together, the data (instance variables), constructors, and methods of a class are called the class members.
  • class head: consists of the Java key word public class followed by the name of the new class.

  • Always use a capital letter for the first character of names of new classes.

  • public & private

2.1.1 Constructors

  • Before any constructor begins its work, all instance variable are assigned Java “default values” which is zero.
  • The name of a con structure must be the same as the name of the class.
  • A constructor is not really a method, and therefore it does not have any return value.
  • Some classes may have more than one constructor, and those constructors are distinguished by distinct sequence of parameters.

2.1.2 No-Arguments Constructors

  • no-argument constructor: a constructor with no argument
  • If you write a class with no constructs at all, then Java automatically provides a non-arguments construct that initializes each instance variable to its initialization value or its default value.

2.1.3 Methods

  • Accessor method: It gives information about an object without altering the object.
  • Modification method: It can change the status of an object.
  • Accessor method often have no parameters, no precondition, and only a simple return condition in the specification.

Why private and accessor method?

  1. Don’t need to know how the class is implemented (don’t need to know what instance variable the class has, only need to know public functions)
  2. Programs use the class will still work when the implementation of class is changed, because the accessor methods are not changed.
  3. It is easy to test the accessor method, which makes the class more reliable.
  4. The pattern of “private data, public method” is able to forbid other programmers from using instance variables in unintended ways (such as setting numberOfPeople to negative).
  • Modification methods are usually void, meaning there is no return value. Most modification methods have parameters.
  • Arithmetic overflow: trying to compute or store a number that is beyond the legal range of the data type.
  • The name of the Java file must match the name of the class.

2.2 Using Class

2.2.1 Creating and Using Objects

  • Call a method = activate a method
  • When a program has several objects of the same class, each object has its own copies of the class’s instance variable.
  • Reference variable: used to refer to objects

2.2.2 Null Reference

  • Null reference: Sometimes a reference variable does not refer to anything. This is a null reference, and the value of the variable is called null.


If a variable is null, then it is a error to activate a method of it. However, it is fine to send message to NULL in Objective-C, which does nothing.

2.2.3 Assignment Statements with Reference Variables

  • If t1 and t2 are reference variables, then the assignment t2 = t1 is allowed.
  • If t1 is null, then the assignment makes t2 null also.
  • It t1 is not null, then the assignment changes t2 so that it refers to the same object that t1 already refers to. At this point, changes can be made to that one object through either t1 or t2.

2.2.4 Clone

  • Clone: A separate copy is a copy of the original object which should not alter the original, nor should subsequent changes to the original alter the copy. (Deep copy)

2.2.5 Test for Equality with Reference Variables

For reference variable t1 and t2, the test (t1 == t2) is true if both references are null or if t1 and t2 refer to the exact same object.

2.3 Packages

2.3.1 Declaring a Package

  • Using the Internet domain name in reserve as a prefix to name package

  • Package declaration

  • Place the package at the right place

    1. Suppose the pwd is a folder called classes.
    2. Underneath the classes directory, crate a subdirectory called com.
    3. Underneath comm, create a subdirectory called brucedsu.
    4. Underneath bruecedsu, create a subdirectory called PACKAGE_NAME
    5. All the .java and .class files for the package mush be placed in the PACKAGE_NAME subdirectory.

2.3.2 The Import Statement to Use a Package

‘*’ means import all classes.

Only import the class called ‘CLASS_NAME’.

2.3.3 The JCL Packages

  • JCL: Java Class Libraries
  • Package java.lang is so useful that is automatically imported into every Java program.

2.3.4 More about Public, Private, and Package Access

  • Access modifiers: The keywords public and private are called the access modifiers because they control access to the class members.

2.4 Parameters, Equals Method, and Clones

2.4.1 Static Method

  • The static keyword means that the method is not activated by any one object.

2.4.2 Parameters That Are Objects

  • When a parameter is an object, then the parameter is initialized so that it refers to the same object that the actual argument refers to.
  • Double.Nan: a constant that a program uses to indicate that a double value is “not a number”.

2.4.3 Methods May Access Private Instance Variables of Objects in Their Own Class

A method may access private instance variables of an object as long as the method is declared as part of the same class as the object.

2.4.4 How to Choose the Name of Method?

Accessor Methods

  • The name of a boolean accessor method will usually begin with “is” followed by an adjective, such as isOn().
  • Methods that convert to another kind of data start with “to”, such as toString().
  • Other accessor method start with ‘get’ or some other verb followed by a noun that describes the return value, such as getFLow().

Modification Methods

A modification method can be named by a descriptive verb, such as shift(), or a short verb phrase, such as shutOff().

Static Methods that Returns a Value

Try to use a noun that describes the return object, such as distance() or midpoint().

2.4.5 Java’s Object Type

In Java, Object is a kind of “super data type” that encompasses all data except the eight primitive types (byte, short, int, long, float, double, boolean, char). In Objective-C, NSObject is the “super data type”.

2.4.6 Using and Implementing an equals() Method

  • When p itself is null, it is a programming error to activate any method of p. Trying to activate any method when p is null results in a NullPointerException.
  • instanceof: is an boolean operator. On the right of the operator is a class name, such as Location. The test returns true if it is valid to convert the object to the given data type.
  • To avid ClassCastException use instanceof first. In Objective-C, use isKindOfClass(__unsafe_unretained Class).

2.4.7 Implementing a clone() Method

1. Modify the Class Head

Add the words “implements Cloneable” in the class head. Just like conforms to protocol in Objective-C.

2. Use super.clone() to Make a Copy

super.clone() is actually clone() method from Java’s Object type.

This exception is thrown by the clone() method from Java’s Objet type when a programmer tries to call super.clone() without including the implements Cloneable clause as part of the class definition.

3. Make Necessary Modification and Return

2.4.8 Java Parameters

  • The eight primitive types: The parameters is initialized with the value of the argument. Subsequent changes to the parameter do not effect the argument.
  • Reference variables: When a parameter is a reference variable, the parameter is initialized so that it refers to the same object as the actual argument. Subsequent changes to this object do affect the actual argument’s object.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 1 The Phases of Software Development

1.0 Introduction

1.0.1 Data Structure

A data structure is a collection of data, organized so that times can be stored and retrieved by some fixed techniques.

1.0.2 The Phases of Software Development

  1. Specification of the task
  2. Design of a solution
  3. Implementation (coding) of the solution
  4. Analysis of the solution
  5. Testing and debugging
  6. Maintenance and evolution of the system
  7. Obsolescence

The last one really surprises me. It is kind of sad for a programmer to say good-bye to his or her program which can be regarded as the baby. However, I realize that I need to code this way because I need to move on! Just like what Steve Job said, “Death is the most powerful change engine!”

1.0.3 Some Thing About Java

  • [Java](http://en.wikipedia.org/wiki/Java_(programming_language) was conceived by a group of programmers at Sun Microsystems in 1991.
  • The group was led by James Gosling.
  • Initial design was called Oak that was motivated by a desire for a single language in which programs could be developed and easily moved from one machine to another. (Great! Compile once, run everywhere!)
  • Java source code -> Byte code -> Java Runtime Environment (JRE)
  • Because the JRE controls all Java programs, there is an added level of security that comes from avoiding potential problems from running unknown programs.
  • Object-oriented programming: information hiding and component reuse

1.1 Specification, Design, Implementation

  • Specification: the specification is a precise description of the problem
  • Design: the design phase consists of formulation the steps (or algorithm) to solve the problem
  • Implementation: implementation is the actual java code to carry out the design.

1.1.1 Design Technique: Decomposing the Problem

  • The large problem is decomposed into subtasks, and subtasks are implemented as separate pieces of problem.
  • The subtask should help you produce short pseudocode—no more than a page of succinct description to solve the entire problem and ideally much less than a page.
  • Another two important things: code reusing and future updating
  • Large proportion of programmer’s time is spent maintaining and modifying existing programs.
  • When you are working on one method, you should not worry about how the other methods perform their jobs.
  • Information hiding: know only as much as you need but no more!

1.1.2 How to Write a Specification for a Java Method

  • Signature of a method: method name + parameter list + return type + modifiers

  • Procedural abstraction (method abstraction): When we pretend that we do not know how a method is implemented, we are using a form of information hiding called procedural abstraction.


  1. Short Introduction
    • method’s name
    • complete heading
    • short description
  2. Parameter Description
  3. Precondition: a precondition is a condition that is supposed to be true when a method is called.
  4. The Returns Condition or Postcondition
    • A return condition specifies the meaning of a method’s return value.
    • A postcondition is a complete statement describing what will be true when a method finishes.
  5. The Throws List

1.1.3 Throw an Exception To Indicate a Failed Precondition

  • Exceptions: violations of preconditions
  • Throwing an exception: The act of halting your own work and passing a message to the calling program is known as throwing an exception.
  • Syntax

  • IllegalArgumentException: tells a programmer that one of the method’s arguments violated a precondition.

  • What happens when an exception is thrown?

    1. The method stops its computation.
    2. An new “exception object” is created, incorporating the indicated error message.
    3. The exception, along with its error message, is passed up to the method or program that made the illegal call in the first place.

  • When an exception is not caught, the program halts, printing the error message along with a list of the method calls that led to the exception.

1.1.4 Programming Tips


Final Variables

  • Final variable means that its value will never be changed.
  • A common programming style is to use all capital letters for the names of final variables.

  • To increase clarity, some programmers declare all constants as final variables.

  • Use final variables instead of constants. Make exceptions when constant are clearer or less error prone.

Make Exception Messages Informative

Format Output with System.out.printf

1.2 Running Time Analysis

  • Time analysis: consists of reasoning about an algorithm’s speed.
  • Instead of measuring the actual elapsed time, we count certain operations that occur while carrying out the work.
  • The analysis counts the number of operations required.
  • There is no precise definition of what constitute an operation, although an operation should satisfy your intuition of a “small step”.

1.2.1 Big-O Notation

  • Precision is not always needed.
  • Quadratic time: O(n^2). The algorithm is called quadratic.
  • Linear time: O(n). The algorithm is called linear.
  • Logarithmic time: O(log n). The algorithm is called logarithmic.
  • Order of an algorithm: When a time analysis is expressed with big-O, the result is called the order of the algorithm.
  • Multiplicative constants are ignored in the big-O notation.
  • The order of an algorithm generally is more important than the speed of the processor.

1.2.2 Time Analysis of Java Methods

  • For Java, a good choice is to count the total number of Java operations, such as an assignment, an arithmetic operation, or the < comparison.
  • If a method calls other methods, we would also need to count the operations that are carried out in the other methods.
  • Frequent Linear Pattern: A loop that does a fixed amount of operations n times requires O(n) time.

1.2.3 Worst-Case, Average-Case and Best-Case Analysis

  • Worst-case analysis: Counting the maximum number of operations is called the word-case analysis, and we usually count the maximum number of required operations for inputs if a given size.
  • The actual number of operation must be guaranteed to be less than the estimate that you use in the analysis.

1.3 Testing and Debugging

  • Programming testing: programming testing occurs when you run a program and observe its behavior.

1.3.1 Choosing Test Data

  • You must know what output a correct program should produce for each test input.
  • The test inputs should include those inputs that are most likely to cause errors.

1.3.2 Boundary Values

  • Boundary value: A boundary value of a problem is an input that is one step away from a different kind of behavior.
  • Frequently zero has a special behavior, so it is a good idea to consider zero to be a boundary value whenever it is a legal input.
  • The number 1 and -1 also have special behavior in many situation, so they should be tested as boundary values whenever they are legal input.
  • In general, there is no precise definition of a boundary value, but you should develop an intuitive feel for finding inputs that are “one step away from different behavior.”

1.3.3 Fully Exercising Code

  • Make sure that each line of your code is executed at least once by some of your test data. Make sure that this rare situation is included among your set of test data.
  • If there is part of your code that is sometimes skipped altogether, make sure there is at least one test input that actually does skip this part of your code. For example, there might be a loop where the body is sometimes executed zero times. Make sure that there is a test input that causes the loop body to be executed zero times.

1.3.4 Assertion

  • Assert statements (also called assertions) are boolean expressions that can be checked for validity while a program is running.
  • Syntax

  • When an assert statement is reached

    • The boolean expression is tested.
    • if (true) { // Do nothing }
    • if (false) { // An exception calledAssertionErrorwill be thrown }.
    • When an AssertionError occurs, the method where the failure occurred will stop its computation and usually the program will stop, printing the indicated error message along with an indication of the line number where the AssertionError occurred.
  • Turn on assertion checking by using the -enableassertions option (or -ea) for the Java runtime system.

  • Assertions should not be used to check preconditions in a public method. Instead, programmers should throw exceptions which can not be turned off.

[DATA STRUCTURE & Other Objects Using JAVA] Chapter 4 Linked Lists

Class IntNode

An IntNode provides a node for a linked list with integer data in each node. Lists can be of any length, limited only by the amount of free memory on the heap. But beyond Integer.MAX_VALUE, the answer from listLength() is incorrect because of arithmetic overflow.






An IntLinkedBag is a collection of int numbers.


  1. Beyond Int.MAX_VALUE elements, countOccurrence, size and grab are wrong.
  2. Because of the slow linear algorithms of this class, large bags have poor performance.