Transcript Lists and the Collection Interface

Lists and the Collection Interface
Chapter 4
The List Interface and ArrayList Class
• So far, all we have is an array for storing a collection of
elements.
• An array is an indexed structure: can select its elements
in arbitrary order using a subscript value
• Elements may be accessed in sequence using a loop
that increments the subscript
• You cannot
• Increase or decrease the length
• Add an element at a specified position without shifting
the other elements to make room
• Remove an element at a specified position without
shifting other elements to fill in the resulting gap
2
The List Interface
• Some of the allowed operations on the List interface
(java.util.List) include:
• Finding a specified target
• Adding an element to either end or in the middle
• Removing an item from either end or from the middle
• Traversing the list structure without a subscript
• Not all classes implementing the List interface perform
the allowed operations with the same degree of
efficiency
3
The List Interface and ArrayList Class
4
The ArrayList Class
• Simplest class that implements the List interface
• Improvement over an array object
• expandable! (ans shrinkable!)
• Mostly used when a programmer wants to add new
elements to the end of a list but still needs the capability
to access the elements stored in the list in arbitrary order
• How to construct and ArrayList?
ArrayList myList = new ArrayList();
//each element is an Object
5
The ArrayList Class
• How to construct and ArrayList? (Java 5.0)
ArrayList<String> myList = new ArrayList<String>();
//each element is a String
6
The ArrayList Class
• size
• int s = myList.size(); //returns 4 for the ArrayList below
7
The ArrayList Class
• Add at a specified index
myList.add(2, “Doc”);
• Add at the end
myList.add(“Dopey”);
8
The ArrayList Class
• Illegal if index > size()
myList.add(8, “Doc”);
9
The ArrayList Class (continued)
• Remove at a certain index
myList.remove(1);
10
The ArrayList Class (continued)
• cannot index like an array
myList[i] ! //illegal
• use
myList.get(i);
myList.set(2, “Sneezy”);
myList.set(6, “Sneezy”); //illegal if index > size()-1
11
The ArrayList Class (continued)
• Search using
myList.indexOf(“Sneezy”); // returns 2
myList.indexOf(“Jumpy”); // returns -1
12
Specification of the ArrayList Class
13
Application of ArrayList
• The ArrayList gives you additional capability beyond
what an array provides
• For Java 1.4.2
• ArrayList stores items of type Object and can thus
store an object of any class
• You cannot store values of the primitive types directly
but must instead use wrapper classes
Example??
• When an object is stored in an ArrayList, the
programmer must remember the original type
String entry = (String) myList.get(1);
14
Application of ArrayList
• For Java 5.0 and higher:
• You cannot store values of the primitive types directly but must
instead use wrapper classes. However,
autoboxing/autounboxing are in effect
ArrayList <Integer> B = new ArrayList<Integer>();
B.add(42); //autoboxing
int temp = B.get(0); //autounboxing
• No casting required when retrieving from the ArrayList
ArrayList<String> C = new ArrayList<String>();
C.add(“Hello”);
String entry = myList.get(0);
15
Recall PhoneDirectory?
• Instance variable theDirectory
private DirectoryEntry [ ] theDirectory = new DirectoryEntry[capacity];
• ArrayBased addOrChangeEntry method
public String addOrChangeEntry(String name, String number) {
String oldNumber = null;
int index = find(name);
if (index > -1) {
oldNumber = theDirectory[index].getNumber();
theDirectory[index].setNumber(number);
}
else {
add(name, number);
}
modified = true;
return oldNumber;
}
16
Using an ArrayList in PhoneDirectory
•
Instance variable theDirectory
private ArrayList<DirectoryEntry> theDirectory = new ArrayList<DirectoryEntry>();
•
addOrChangeEntry method
public String addOrChangeEntry(String name, String number) {
String oldNumber = null;
int index = theDirectory.indexOf(new DirectoryEntry(name, “”));
//assuming DirectoryEntry class has an equals method that compares entries by name
if (index != -1) {
DirectoryEntry de = theDirectory.get(index);
oldNumber = de.getNumber();
de.setNumber(number);
}
else {
theDirectory.add(new DirectoryEntry(name, number));
}
modified = true;
return oldNumber;
}
17
Assignment #1 (Due Thursday, Sep 24)
• Design and implement the Programming Project #2
described at the end of Chapter 1 (page 56), using an
ArrayList as the underlying storage.
• Provide UML diagrams for your design.
• Document your code well.
• Place all your file under a directory called
YourNameHW1 and zip the directory. Email a single
zipped file to [email protected]
• Submit a hardcopy of your code together with your UML
diagram in class on the due date.
18
Implementation of an ArrayList Class
• KWArrayList: simple implementation of a ArrayList class
• Physical size of array indicated by data field capacity
• Number of data items indicated by the data field size
19
Implementation of an ArrayList Class
(continued)
20
Performance of KWArrayList and the Vector
Class
• Set and get methods execute in constant time
• Inserting or removing elements is linear time
• Initial release of Java API contained the Vector class
which has similar functionality to the ArrayList
• Both contain the same methods
• New applications should use ArrayList rather than Vector
21