Transcript PPTX - UF CISE

1 / 83
1
COP 3503 FALL 2012
SHAYAN JAVED
LECTURE 8
Programming Fundamentals using Java
2 / 83
ArrayList and Java
Generics
3 / 83
Collection

A container object that groups multiple objects
4 / 83
Collection

A container object that groups multiple objects
 Example:
Arrays
5 / 83
Collection

A container object that groups multiple objects
 Example:

Arrays
Java provides multiple classes/interfaces in the
Java Collection Framework
6 / 83
Collection

A container object that groups multiple objects
 Example:

Arrays
Java provides multiple classes/interfaces in the
Java Collection Framework
 Going
to look at ArrayList
7 / 83
Arrays

Hold several elements (primitives/objects) of the
same type
8 / 83
Arrays

Hold several elements (primitives/objects) of the
same type

Size = static.
 Once
set, cannot be changed
9 / 83
Arrays

Advantages:
 Easy
to access elements directly
10 / 83
Arrays

Advantages:
 Easy
to access elements directly
 Easy to traverse
11 / 83
Arrays

Advantages:
 Easy
to access elements directly
 Easy to traverse

Disadvantages:
 Have
to decide on size before creating
12 / 83
Arrays

Advantages:
 Easy
to access elements directly
 Easy to traverse

Disadvantages:
 Have
to decide on size before creating
 Inserting/removing elements is troublesome
 Shifting elements
13 / 83
ArrayList (java.util.ArrayList)

Holds several objects in order (like Arrays)
14 / 83
ArrayList (java.util.ArrayList)

Holds several objects in order (like Arrays)

Unlike Arrays:
 Size
does not need to be specified at creation time
15 / 83
ArrayList (java.util.ArrayList)

Holds several objects in order (like Arrays)

Unlike Arrays:
 Size
does not need to be specified at creation time
 Grows in size as items added
16 / 83
ArrayList (java.util.ArrayList)

Holds several objects in order (like Arrays)

Unlike Arrays:
 Size
does not need to be specified at creation time
 Grows in size as items added

Provides useful methods for manipulating the list
17 / 83
ArrayList (java.util.ArrayList)

Constructors:
 new ArrayList( )
- no need to pass in size (10)
18 / 83
ArrayList (java.util.ArrayList)

Constructors:
 new ArrayList( )
 new ArrayList(int)
- no need to pass in size (10)
- initial capacity
19 / 83
ArrayList (java.util.ArrayList)

Methods:

boolean add(Object o):
Appends object at the end of the list
20 / 83
ArrayList (java.util.ArrayList)

Methods:


boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
21 / 83
ArrayList (java.util.ArrayList)

Methods:



boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
22 / 83
ArrayList (java.util.ArrayList)

Methods:




boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
23 / 83
ArrayList (java.util.ArrayList)

Methods:





boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
Object get(int index):
Returns object at the index
24 / 83
ArrayList (java.util.ArrayList)

Methods:






boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
Object get(int index):
Returns object at the index
boolean remove(Object o):
Removes the object from the list
25 / 83
ArrayList (java.util.ArrayList)

Methods:







boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
Object get(int index):
Returns object at the index
boolean remove(Object o):
Removes the object from the list
Object remove(int index):
Removes the object at the index
26 / 83
ArrayList (java.util.ArrayList)

Methods:








boolean add(Object o):
void add(int index, Object o):
void clear():
boolean contains(Object o):
Object get(int index):
boolean remove(Object o):
Object remove(int index):
int size():
Appends object at the end of the list
Inserts object at specified index
Removes all elements
Returns true if object is in the list
Returns object at the index
Removes the object from the list
Removes the object at the index
Returns the no. of elements in the list
27 / 83
ArrayList (java.util.ArrayList)

Methods:









boolean add(Object o):
void add(int index, Object o):
void clear():
boolean contains(Object o):
Object get(int index):
boolean remove(Object o):
Object remove(int index):
int size():
int indexOf(Object o):
Appends object at the end of the list
Inserts object at specified index
Removes all elements
Returns true if object is in the list
Returns object at the index
Removes the object from the list
Removes the object at the index
Returns the no. of elements in the list
Returns index of first matching element
28 / 83
ArrayList (java.util.ArrayList)

Methods:










boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
Object get(int index):
Returns object at the index
boolean remove(Object o):
Removes the object from the list
Object remove(int index):
Removes the object at the index
int size():
Returns the no. of elements in the list
int indexOf(Object o):
Returns index of first matching element
Object set(int index, Object o): Sets the object at the index
29 / 83
ArrayList (java.util.ArrayList)

Methods:











boolean add(Object o):
Appends object at the end of the list
void add(int index, Object o): Inserts object at specified index
void clear():
Removes all elements
boolean contains(Object o):
Returns true if object is in the list
Object get(int index):
Returns object at the index
boolean remove(Object o):
Removes the object from the list
Object remove(int index):
Removes the object at the index
int size():
Returns the no. of elements in the list
int indexOf(Object o):
Returns index of first matching element
Object set(int index, Object o): Sets the object at the index
Object clone():
Returns a shallow copy
30 / 83
ArrayList Example
import java.util.ArrayList;
31 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
32 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
numbers.add(new Integer(10));
// no size specified initially
33 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
34 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
int sum = 0;
int number = 0;
// sum up all the numbers in the list
35 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
}
36 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = (Integer)numbers.get(i);
}
// cast required – why?
37 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = (Integer)numbers.get(i);
sum += number;
}
// cast required – why?
// auto un-boxing: Integer converted to int
38 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
numbers.add(“A String”);
// will compile!
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = (Integer)numbers.get(i);
sum += number;
}
// cast required – why?
// auto un-boxing: Integer converted to int
39 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList numbers = new ArrayList();
// no size specified initially
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: converted to
numbers.add(new Integer(3)); */
numbers.add(“A String”);
// will compile!
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = (Integer)numbers.get(i);
sum += number;
}
// run-time error when i = 2
// auto un-boxing: Integer converted to int
40 / 83
ArrayList
How do we make sure we are dealing with
objects of only one type?
41 / 83
ArrayList
How do we make sure we are dealing with
objects of only one type?
Solution: Java Generics
42 / 83
Java Generics

Generics is the capability to parameterize types
43 / 83
Java Generics

Generics is the capability to parameterize types

Can define class/interface/method with generic
types – compiler replaces with concrete types.
44 / 83
Java Generics

Generics is the capability to parameterize types

Can define class/interface/method with generic
types – compiler replaces with concrete types.

Introduced in JDK 1.5
45 / 83
java.util.ArrayList<E>

Methods:











boolean add(E o):
void add(int index, E o):
void clear():
boolean contains(E o):
E get(int index):
boolean remove(E o):
E remove(int index):
int size():
int indexOf(E o):
E set(int index, E o):
E clone():
Appends object at the end of the list
Inserts object at specified index
Removes all elements
Returns true if object is in the list
Returns object at the index
Removes the object from the list
Removes the object at the index
Returns the no. of elements in the list
Returns index of first matching element
Sets the object at the index
Returns a shallow copy
46 / 83
Java Generics

Type of objects it can hold is specified at
declaration
47 / 83
Java Generics

Type of objects it can hold is specified at
declaration
// will only hold Integer objects
ArrayList<Integer> numbers = new ArrayList<Integer>();
48 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: */
numbers.add(“A String”);
// WON’T COMPILE!
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = (Integer)numbers.get(i);
sum += number;
}
// cast NOT required – why?
// auto un-boxing: Integer converted to int
49 / 83
ArrayList Example
import java.util.ArrayList;
ArrayList<Integer> numbers = new ArrayList<Integer>();
numbers.add(new Integer(10));
numbers.add(3);
/* auto-boxing: */
numbers.add(“A String”);
// WON’T COMPILE!
int sum = 0;
// sum up all the numbers in the list
int number = 0;
for(int i = 0; i < numbers.size(); i++) {
number = numbers.get(i);
sum += number;
}
// cast NOT required – why?
// auto un-boxing: Integer converted to int
50 / 83
Java Generics

More strictness
51 / 83
Java Generics


More strictness
Fewer errors
52 / 83
Generic Classes
public class AClass<E> {
// properties and methods can use the “E” type
}
53 / 83
Generic Classes
public class AClass<E> {
// properties and methods can use the “E” type
ArrayList<E> numbers = new ArrayList<E>();
}
54 / 83
Generic Methods
public class GenericMethodDemo {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York”};
}
55 / 83
Generic Methods
public class GenericMethodDemo {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York”};
}
public static <E> void print(E[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println(); }
}
56 / 83
Generic Methods
public class GenericMethodDemo {
public static void main(String[] args ) {
Integer[] integers = {1, 2, 3, 4, 5};
String[] strings = {"London", "Paris", "New York”};
GenericMethodDemo.<Integer>print(integers);
GenericMethodDemo.<String>print(strings);
}
public static <E> void print(E[] list) {
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
System.out.println(); }
}
57 / 83
Generic Interfaces
public interface AnInterface<E> {
// properties and methods can use the “E” type
public void aMethod(E object);
}
58 / 83
Generic Interfaces
public interface Comparable<E> {
public int compareTo(E object);
}
59 / 83
Generic Interfaces
public interface Comparable<E> {
public int compareTo(E object);
}
public interface Comparator<E> {
public int compare(E object1, E object2);
}
60 / 83
Generic Interfaces
public Book implements Comparable{
// comparison based on price
public int compareTo(Object o) {
Book b = (Book)o;
if (price > b.getPrice())
return 1;
else if (price < b.getPrice())
return -1;
else
return 0;
}
}
61 / 83
Generic Interfaces
public Book implements Comparable{
}
// comparison based on price
public int compareTo(Object o) {
Book b = (Book)o;
if (price > b.getPrice())
return 1;
else if (price < b.getPrice())
return -1;
else
return 0;
}
HOW WOULD YOU USE JAVA GENERICS?
62 / 83
Generic Interfaces
public Book implements Comparable<Book>{
// comparison based on price
public int compareTo(Book b) {
Book b = (Book)o;
if (price > b.getPrice())
return 1;
else if (price < b.getPrice())
return -1;
else
return 0;
}
}
63 / 83
Generic Interfaces
public Book implements Comparable<Book>{
// comparison based on price
public int compareTo(Book b) {
Book b = (Book)o; // no more casting!
if (price > b.getPrice())
return 1;
else if (price < b.getPrice())
return -1;
else
return 0;
}
}
64 / 83
Generic Interfaces
public Book implements Comparable<Book>{
// comparison based on price
public int compareTo(Book b) {
Book b = (Book)o; // no more casting!
if (price > b.getPrice())
return 1;
else if (price < b.getPrice())
return -1;
else
return 0;
}
}
65 / 83
Generic Interfaces
public class ReviewComparison implements Comparator {
public int compare (Object o1, Object o2) {
Book b1 = (Book)o1;
Book b2 = (Book)o2;
if (b1.getACR() > b2.getACR())
return 1;
if (b1.getACR() < b2.getACR())
return -1;
else
return 0;
}
}
66 / 83
Generic Interfaces
public class ReviewComparison implements Comparator<Book> {
public int compare (Book b1, Book b2) {
Book b1 = (Book)o1;
Book b2 = (Book)o2;
if (b1.getACR() > b2.getACR())
return 1;
if (b1.getACR() < b2.getACR())
return -1;
else
return 0;
}
}
67 / 83
Generic Interfaces
public class ReviewComparison implements Comparator<Book> {
public int compare (Book b1, Book b2) {
Book b1 = (Book)o1;
Book b2 = (Book)o2;
if (b1.getACR() > b2.getACR())
return 1;
if (b1.getACR() < b2.getACR())
return -1;
else
return 0;
}
}
68 / 83
Java Generics - Summary

Allows you to create a “general” template

Classes/methods/interfaces

Versatile and strict
69 / 83
Back to ArrayList...

How does it work “behind the scenes”?
70 / 83
Back to ArrayList...

How does it work “behind the scenes”?

Elements are stored inside an array
 private
array
71 / 83
Back to ArrayList...

How does it work “behind the scenes”?

Elements are stored inside an array
 private

array
Array has an initial capacity
72 / 83
Back to ArrayList...

How does it work “behind the scenes”?

Elements are stored inside an array
 private

array
Array has an initial capacity
 Empty
constructor [new ArrayList()]: capacity 10
73 / 83
Back to ArrayList...

How does it work “behind the scenes”?

Elements are stored inside an array
 private

array
Array has an initial capacity
 Empty
constructor [new ArrayList()]: capacity 10
 Otherwise specify capacity [new ArrayList(capacity)]
74 / 83
ArrayList

When number of elements exceeds capacity (the
add/insert method):
75 / 83
ArrayList

When number of elements exceeds capacity (the
add/insert method):
 Internal
array replaced by new one
76 / 83
ArrayList

When number of elements exceeds capacity (the
add/insert method):
 Internal
array replaced by new one
 Elements from the old array copied over
77 / 83
ArrayList

When number of elements exceeds capacity (the
add/insert method):
 Internal
array replaced by new one
 Elements from the old array copied over

Insert and remove require shifting of elements
78 / 83
ArrayList

When number of elements exceeds capacity (the
add/insert method):
 Internal
array replaced by new one
 Elements from the old array copied over

Insert and remove require shifting of elements
 (Recall
add/remove in Project1)
79 / 83
Efficiency of ArrayLists

Reallocation of underlying array = when capacity
reached and need to add more elements
80 / 83
Efficiency of ArrayLists

Reallocation of underlying array = when capacity
reached and need to add more elements

Add/Insert/Remove = costly because requires
shifting of elements in array
81 / 83
Efficiency of ArrayLists

Reallocation of underlying array = when capacity
reached and need to add more elements

Add/Insert/Remove = costly because requires
shifting of elements in array

Accessing element (get) = fast just like an array
82 / 83
Efficiency of ArrayLists

Reallocation of underlying array = when capacity
reached and need to add more elements

Add/Insert/Remove = costly because requires
shifting of elements in array

Accessing element (get) = fast just like an array

Problems overcome with Linked Lists.
83 / 83
Other Java Collections

LinkedList

Stack

Queue

Will look at these later