Previous Pre-recorded Lecture

Students’ led Q/As about the previous lecture:

 Recursion:
• How it really works

• Recursive Helper Methods

• More example problems

• Ones that have a nice recursive solution
• Ones that really need recursion
ArrayLists and Intro to Generics
Part 1/2 • Tail-Recursive Method

• Recursion vs. Iteration

Dr. Abdallah Mohamed

Acknowledgement: The slides mainly rely on the textbook of Y. D. Liang titled “Introduction to
Java Programming, 10th Ed.”, Pearson Edu. Inc. COSC 121. Page 1 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 2

Outline 121 Topics

Today: So far, you learned techniques of “how to do things”:
 Basic Java constructs (if, while, for, …)
 Intro to Java Collection Framework
 OOP basics (Encapsulation, Inheritance, Polymorphism)
 The ArrayList Class  Exception Handling
 Implementing a Stack using ArrayList  I/O streams
 Recursion
 Sample applications
Next, lets look at “how to do things efficiently”
Next lecture:
 Data structures
 Intro to the implementation of ArrayLists • what is the best and most efficient way to store data in memory?
• We have a course COSC222 dedicated for data structures
 Iterating Over an ArrayList  Algorithms – e.g. Searching
 Useful Methods for Lists • What is the most efficient algorithm to solve a problem (sorting)?
• We have a course COSC 320 dedicated for algorithms
• Arrays and Collections classes

 Intro to Generics COSC 121. Page 3 COSC 121. Page 4

 Java Collections Framework
A data structure is a collection of data organized somehow.
 It is a container object that stores other objects (data).
 A data structure is defined by a class.
• data fields – data objects
• methods – operations for managing the data.

Java Collections Framework includes several data structures

Java Collections Framework for storing and managing data (objects of any type).
It supports two types of containers:
 Collection: for storing a collection of elements.
• e.g., Lists (ordered), Stacks (LIFO), and Queues (FIFO).
 Map: for storing key/value pairs.
• e.g., HashMap

All concrete classes in the Collection framework implements the

COSC 121. Page 5
Serializable interface. COSC 121. Page 6

Collection Class Hierarchy Collections Class Hierarchy (simplified)

This diagram is not accurate. There are several abstract classes
and interfaces omitted, but it helps show the big picture.

Interfaces Abstract Classes Concrete Classes

Will discuss more on this in Chapter 20

Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 7 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 8
 Intro to ArrayList Class
An ArrayList object
 can be used to store a list of objects (similar to an array).
 its capacity can dynamically grow during the runtime.
• capacity: the maximum number of items an array list can currently
hold without being extended.
The ArrayList Class • size :the current number of items stored in the ArrayList.

 internally, it is implemented using an array

• Arrays are fixed-size data structures

COSC 121. Page 9 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 10

Array vs. ArrayList How to declare an ArrayList?

Objects of the generic class ArrayList are similar to ArrayList<String> list1 = new ArrayList<String>();
arrays, but have differences:  list1 holds String references

 Similarities
 This declaration sets up an empty ArrayList The initial capacity
is set to a default value.
• Both can store a number of references
• The data can be accessed via an index. ArrayList<Date> list2 = new ArrayList<Date>(100);
 Differences
 list2 holds Date references
• ArrayList can automatically increase in capacity as necessary
• Will request more space from the Java run-time system, if necessary.  This declaration can be used to specify the initial capacity – in
• ArrayList have methods to do many actions this case 100 elements.
• e.g. can insert/remove elements anywhere in the list • This can be more efficient in avoiding repeated work by the system in
extending the list, if you know approximately the required initial capacity.
• ArrayList is not ideal in its use of memory.
• As soon as an ArrayList requires more space than its current
capacity, the system will allocate more memory space for it. The
extension is more than required for the items about to be added. Whenever you use array lists, you must import java.util.ArrayList.
Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 11 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 12
 How to declare an ArrayList? Initializing an ArrayList
Since Java 7, the statement Once you create an array list, you can start adding elements to it
using its add method:
ArrayList<String> list1 = new ArrayList<String>(); ArrayList<String> list = new ArrayList< >();
can be simplified to list.add("R"); //add "R" to end of list
list.add("B"); //add "B" to end of list
ArrayList<String> list1 = new ArrayList< >();
list.add(1,"G"); //add "G" between R and G
compiler is able to infer the type from the variable declaration.
You can initialize an array list using another collection:
If Type is omitted, the default type is Object ArrayList<Type> list1 = new ArrayList<>(aCollection);

ArrayList list3 = new ArrayList(); We can use Arrays.asList method to create a fixed-size list
backed by specified elements (more about this next class).
list3 has references of the type Object, which means we can ArrayList<String> list1
store any object types in it (WHY?) = new ArrayList< >(Arrays.asList("R","G"));
Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 13 COSC 121. Page 14

Clicker Question Clicker Question

Which of the following is used to construct an ArrayList? Suppose ArrayList x has two strings ["A","B"]. Which of the

A. new ArrayList[] following will cause x to become ["A","C","B"]?

B. new ArrayList[100] A. x[2] = x[1]; x[1] = "C";

C. new ArrayList<>() B. x.add("C");

D. There is more than one correct answer C. x.add(0, "C");

D. x.add(1, "C");

E. There is more than one correct answer

COSC 121. Page 15 COSC 121. Page 16

 SOME methods (more will be discussed later) Clicker Question
boolean add(E o) Appends a new element o at the end of this list.
Suppose ArrayList x has two strings ["A","B"]. Which of the
void add(int index, E o) Adds a new element o at the specified index in this list.
E set(int index, E e) Sets the element at the specified index. following will cause x to become ["A"]?
E get(int index) Returns the element from this list at the specified index.
A. x[1] = "";
boolean remove(Object e) Removes the first occurrence of element o from this list.
E remove(int index) Removes the element at the specified index. B. x.remove(0);
void clear() Removes all the elements from this list.
C. x.remove(1);
int indexOf(Object e) Returns the index of the first matching element in this list
int lastIndexOf(Object e) Returns the index of the last matching element in this list. D. x.remove("B");
boolean contains(Object e) Returns true if this list contains the element o.
boolean isEmpty() Returns true if this list contains no elements.
E. There is more than one correct answer
int size() Returns the number of elements in this list.
void trimToSize() Trims the capacity of this ArrayList instance to the current size.
boolean equals(Object x) Returns true if x is a list and both lists have the same size,
and all corresponding pairs of elements are equal.
String toString() Returns a string representation of the list elements. COSC 121. Page 18

Clicker Question Clicker Question

Suppose ArrayList x has two strings ["A","B"]. Which of the What is the output of the following code?
ArrayList<String> x=new ArrayList<>(Arrays.asList("A","B","C"));
following will cause x to become ["C"]? System.out.println(x);
x.set(1, "D");
A. x = null; x.add("C"); x.add("D");
System.out.println(x);
B. x.clear(); x.add("C"); System.out.println(x.indexOf("C"));
System.out.println(x.indexOf("Z"));
C. x.remove(0); x.set(0,"C");
System.out.println(x.remove("Z"));
System.out.println(x.remove("D"));
Duplicates are
D. There is more than one correct answer allowed!
System.out.println(x);

A. [A, B, C] B. [A, B, C] C. [A, B, C]

[D, B, C, D] [A, D, C, D] [A, D, C, D]
2 2 2
-1 -1 -1
false false false
true true true
[B, C, D] [A, C, D] [A, D, C]
COSC 121. Page 19 COSC 121. Page 20
 Practice 1
Write Java code to do the following:
a. Create an ArrayList for storing double values
b. Append two doubles to a list
c. Insert a double at the beginning of a list
d. Find the number of objects in a list
e. Remove a given object from a list
Practice Questions f. Remove the last object from the list
g. Check whether a given object is in a list
h. Retrieve an object at a specified index from a list

COSC 121. Page 21 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 22

Practice 2 Practice 2 – cont’d

Write a program that reads from the user a set of integers and Simpler code
stores them in an ArrayList. The input ends with 0 where the
program displays all stored elements. Your list should have no ArrayList<Integer> list = new ArrayList<>();
int value;
duplicates. For example:
//read numbers
Scanner in = new Scanner(System.in);
System.out.println("Enter integers (0 to end): ");
while((value = in.nextInt()) != 0)
if(!list.contains(value))
list.add(value);

//display distinct numbers

System.out.println(list);

Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 23 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 24
 The Stack Practice 3
A Stack represents a LIFO (last-in-first-out) data Create a custom stack class, MyStack, that can hold objects
structure. The elements are accessed only from the according to the following:
top of the stack. That is, you can only retrieve, insert,
or remove an element from the top of the stack.

push pop MyStack

A
KT

Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 25 Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 26

class MyStack {
Solution private ArrayList list = new ArrayList<>();
public boolean isEmpty() {
return list.size() == 0;
}
public int size() {
return list.size();
}
public void push(Object e) {
list.add(e);
}
public Object pop() {
if(list.size()>0) Sample Applications in Gaming
return list.remove(list.size() - 1);
else
return null;
}
public Object peek() {
if(list.size()>0)
return list.get(list.size() - 1);
else
return null;
}
} COSC 121. Page 27 COSC 121. Page 28
 Practical Example Pseudo code for a space shooter game
The following example creates an ‘army’ of robots, e.g. in a game Create an ArrayList<Star> stars
and then control all of them using a loop (e.g., move forward) Create an ArrayList<Enemy> enemies
Create an ArrayList<Bullet> bullets
ArrayList<Robot> robots = new ArrayList<>(5);
robots.add(new Robot(1,1)); In each frame{
robots.add(new Robot(2,1)); for(Star star: stars) {star.move() }
robots.add(new Robot(3,1));
for(Enemy enemy:enemies){enemy.move()}
System.out.println("BEFORE:" + robots); for(Bullet bullet: bullets) {
for(Robot r: robots) //move your robot army forward bullet.move();
r.moveForward(); for(Enemy enemy: enemies)
System.out.println("AFTER :" + robots); if (bullet.hits(enemy)){
bullets.remove(bullet);
class Robot{
private int x, y; enemies.remove(enemy);
public Robot(int x, int y) {this.x = x;this.y = y;} score++
public void moveForward(){y++;} }
public String toString() {return "("+x+","+y+")";}
}
}
}
Liang, Introduction to Java Programming, Tenth Edition, (c) 2015 Pearson Education, Inc. COSC 121. Page 29 COSC 121. Page 30