Java Collections Framework
1. Collection Interfaces
A data structure is a collection of data organized in some fashion. A data structure not only stores data, but also supports the operations for accessing and manipulating data in the structure.
Java supports the traditional data structures at a high level under the Collections framework. The framework is built on the base interface Collection. Please have a look at Figures 22.1 and 23.3 (22.15 in 8E) so that you will have a rough picture what we are going to learn in this topic.
1.1 Collection interface
The fundamental interface for collection classes is the Collection interface.
public interface Collection
int size();
boolean isEmpty();
boolean contains(Object a);
boolean containsAll(Collection c);
boolean equals(Object other);
boolean addAll(Collection from);
boolean remove(Object a);
boolean removeAll(Collection c);
void clear();
boolean retainAll(Collection c);
Object[] toArray();
boolean add(T element);
Iterator
.. .. ..
}
The Collection interface provides the basic operations that a collection needs, for example, adding an element to the collection, removing an element from the collection, querying an element and reporting the size of the collection etc. It also supports an iterator with which a user can traverse all the elements in the collections.
From Figure 22.1 you can see that the implementation of almost all the traditional data structures is based on the collection interface.
1.2 Iterators
To support the way of traversing a collection, Java provides the Iterator interface which has three methods
public interface Iterator
E next();
Boolean hasNext();
Void remove();
}
With an iterator, it is very easy to traverse all the elements in a collection by using the following template
Collection
Iterator
while (iter.hasNext())
{
Employee person = iter.next();
Do something with the person
}
or You can use the following shortcut for loop
for (Employee person: empl) {
do something with the person;
}
The compiler will translate this for loop into a loop with an iterator.
1.3 The AbstractCollection class
Many of the methods declared in the Collection interface are implemented in the abstract class AbstractCollection. Thus a concrete collection like a list can extend the AbstractCollection class. After that users are free to use the whole collection for their own tasks.
2. Fundamental collections
The Java Collection Framework offers a great number of concrete collections, such asArrayList, LinkedList, PriorityQueue etc. It is up to you to pick them for your own purposes. You should have your own background knowledge about which data structure is most appropriate to your problem. In this topic you are expected to learn how to create the data collection you need with the assistance of the Collection framework.
2.1 Using lists
A list is a popular data structure for storing data in sequential order. For example, a list ofEmployee, a list of Manager, and a list of city names. The typical operations on a list are
· Inserting a new element to a list
· Deleting an element from a list
· Retrieve an element from a list
· Finding the number of elements in a list
There are two implementations for the lists in the collection framework. One is to use array to store the elements, called ArrayList. The other approach is to use a linked structure, called LinkedList. Both are generic classes.
To create an array list use the following way
List
//ArrayList implements List
To create a linked list use the following way
List
//LinkedList implements List
When you use a list in your program, you don’t need to know which implementation is actually used once the collection has been constructed. Thus we always use the interface type, here List, to hold the collection reference. Choosing either ArrayListor LinkedList depends on your tasks. If your task is involved a lot of inserting or deleting elements to or from a list, you should consider using LinkedList because it is more efficient to use a linked structure for frequently adding and removing.
The following example demonstrates how to use the LinkedList and its iterator.
import java.util.*;
import java.io.*;
public class LinkedListTest {
public static void main(String[] argv) {
List
// create a list
names.add(“Beijing”);
names.add(“Tokyo”);
names.add(“Sydney”);
names.add(“Washington”);
List
population.add(18000000);
population.add(1200000);
population.add(4000000);
population.add(800000);
ListIterator
Iterator
System.out.println(“The City Population Table”);
while (nIter.hasNext() && pIter.hasNext()) {
System.out.println(nIter.next()+”: “ + pIter.next());
}
}
}
Read the Java document for more information on the available methods for ArrayListand LinkedList classes.
2.3 Using the Stack
The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends classVector with five operations that allow a vector to be treated as a stack. The usual pushand pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
The following example shows you how to use a stack object in your program
import java.util.*;
import java.io.*;
public class TestStack {
public static void main(String[] argv) {
Stack
mystack.push("Syndey");
mystack.push("London");
mystack.push("Paris");
mystack.push("Beijing");
while (!mystack.empty())
System.out.println(mystack.pop());
}
}
2.4 Using Queue and PriorityQueue
Queue is also a collection of data but you can add element at the tail of the queue, and remove them at the head. It is also called First-In-First-Out (FIFO) data structures. It is very useful in tasks management and simulation.
The basic operations of queue is enqueue, implemented by the add method and dequeue by the remove method. Just like the lists, Java defines the Queue interface and however the collection framework does not provide any implementation for ordinary queues, but for example ProrityQueue, ArrayBlockingQueue etc. The reason is that it is very easy for one to use a list to simulate a queue by restricting the addition at the one end of the list and deletion on the other end.
There are some implementations for ordinary queues from other organizations. For example JGroups implements the Queue interface as LinkedListQueue in the following way
class LinkedListQueue
{
LinkedListQueue() { ..}
public void add(T element) { …}
public E remove() { .. }
public int size() { .. }
private Link head;
private Link tail;
}
To use it, you can follow the following syntax
Queue
jobline.add(new Job(“Job Description”));
The only difference between ordinary queues and PriorityQueue is that the elements in a PriorityQueue is ordered by a nature Comparable way or a Comparatormethod. That is the element in a priority queue must be comparable. The remove method always returns the smallest element in the collection.
Try the following example, then you will see how elements are taken from a priority queue.
import java.util.*;
import java.io.*
public class TestPriorityQueue {
public static void main(String[] argv) {
Queue
myqueue.add(“Syndey”);
myqueue.add(“London”);
myqueue.add(“Paris”);
myqueue.add(“Beijing”);
Iterator
while (Iter.hasNext())
System.out.println(Iter.next());
//Removing elements from the head
while (myqueue.size()>0)
System.out.println(myqueue.remove());
}
}
After running the program you will see the output will be Beijing, London, Paris and Sydney which are in the alphabetical order. This is the natural order of the String objects. You can change the order of taking elements from a PriorityQueue by providing an appropriate Comparator. Try the following example
import java.util.*;
import java.io.*;
public class TestPriorityQueue1 {
public static void main(String[] argv) {
PriorityQueue
Collections.reverseOrder());
myqueue.offer("Syndey");
myqueue.offer("London");
myqueue.offer("Paris");
myqueue.add("Beijing"); //or use add method
Iterator
while (Iter.hasNext())
System.out.println(Iter.next());
while (myqueue.size()>0)
System.out.println(myqueue.remove());
}
}
Can you see what are different?
A set is a collection of elements but there is no special implicit “order” among the elements. This is different from other data structure we met in the previous sections. For example, a list is also a collection of elements, but we can talk about the first element, the second element on the list. The elements in a set should not be duplicated, however you may add an element onto a list/stack/queue many times.
3. Advanced collections
3.1 The Set interface
The Java Set interface extends the Collection interface. It specially stipulate that an instance of Set contains no duplicate elements.
The concrete classes that implement Set interface must ensure that no duplicate elements can be added to the set.
The collection framework offers three different kind of implementation for the Setinterface. These three concrete classes are HashSet, LinkedHashSet andTreeSet. When you use these classes for your tasks, you don’t need to care much about the implementation although for a large project using one implementation may be more efficient than using the other.
3.2 Using concrete set classes
Using the three concrete set classes is simple and it seems no difference. Read the following examples
import java.util.*;
public class TestSets {
public static void main( String[] argv ) {
Set
Set
Set
set1.add(“Beijing”);
set1.add(“London”);
set1.add(“Paris”);
set1.add(“Sydney”);
set2.add(1);
set2.add(10);
set2.add(100);
set2.add(1000);
set3.add(1.0);
set3.add(2.01);
set3.add(3.002);
set3.add(4.0003);
for (Object element: set1)
System.out.println(element);
Iterator iter = set2.iterator();
while (iter.hasNext())
System.out.println(iter.next());
System.out.println(set3);
//output all the elements in the set
}
}
3.3 Using maps
A map is a collection of elements in the form of key/value pairs. The map structure is very useful in the case of storing indexed/keyed data. For example, you may have a table of employee records where the employee ID is the key and the values areEmployee objects. With a key it is easy for you to look up an element in a map. A map cannot contain duplicate keys. Each key maps to one value.
The collection framework defines the Map interface. The interface provides the methods for querying, updating, and obtaining a collection of values and a set of keys. Check Figure 23.4 of your text book with the methods defined in the Map interface.
The collection framework supplies three implementation for maps: HashMap,LinkedHashMap and TreeMap. Using maps is easy. The following illustrates a map at work. We first add key/pairs to a map where both keys and values are Integer and we are creating a table of square numbers for 1 to 100. Then we change the value that is associated with a key and call the get method to look up a value. Next, we remove one key from the map, which removes its associated value as well. Finally, we iterate through an entry set.
import java.util.*;
public class TestMaps {
public static void main( String[] argv ) {
Map table =
new HashMap();
for (int i = 1; I <= 100; i++)
table.put(i, i*i);
//print all entries
System.out.println(table);
//change a value by putting a new one
int a = 3;
table.put(a, 19); //an incorrect value
System.out.println(“The square of “ + a + “ is: “
+ table.get(a));
System.out.println(“The square of “ + (a+1) + “ is: “
+ table.get(a+1));
table.remove(a);
for (Map.Entry entry: table.entrySet())
{
int key = entry.getKey();
int value = entry.getValue();
System.out.println(“key=” + key+ “,
value = “ + value);
}
}
}
Try this program and you will see the printout is not in any reason order. Then changeHashMap to TreeMap and see what will happen. If you are concerned with a certain order for your map elements, then you should use the TreeMap class.
4. Simple Algorithms
Reading: The Study Guide here
4.1 Converting between Collections and Arrays
Sometimes you need to translate between traditional arrays and the more modern collections. If you have an array, you want to turn it into a collection. You can use theArrays.asList wrapper to achieve it. For example,
String[] myarrayvalues = new String[4];
// add some strings into the array here
HashSet
HashSet
On the other side, you could use toArray method to convert a collection into an array. Two ways for this goal
Object[] myarray = myset.toArray(); // returning an array of Object
// rather than an array of String
Or put the elements from a collection into an newly created array variable
String[] myarray = new String[myset.size()];
myset.toArray(myarray);
4.2 Maximal and minimal elements
The collection framework supplies methods for you to find the maximal/minimal element in a collection. You simply call the max/min method with your collection as a parameter, then the method returns the result. Of course, it is supposed that the element of the collection is Comparable. Try the following example
import java.util.*;
public class TestMinMax {
public static void main( String[] argv ) {
Set
set.add("Beijing");
set.add("London");
set.add("Paris");
set.add("Sydney");
System.out.println("The minimal string is " +
Collections.min(set));
System.out.println("The maximal string is " +
Collections.max(set));
}
}
Of course, you can provide a Comparator as the second parameter to the max/minmethod so that the maximal/minimal element in the meaning of the new Comparatorcan be obtained.
4.3 Sorting a list
Most of time we want to sort the elements of a list in increasing/decreasing order. This can be easily done by call the sort method. Read the following example
import java.util.*;
public class TestSort {
public static void main( String[] argv ) {
List
list.add("Beijing");
list.add("Sydney");
list.add("Paris");
list.add("London");
System.out.println(list);
Collections.sort(list);
System.out.println(list);
Collections.sort(list, Collections.reverseOrder());
System.out.println(list);
}
}
4.4 Binary searching
To find an object in an array, you normally visit all elements until you find a match. However, if the array is sorted, then you can look at the middle element and check whether it is larger than the element you are trying to find. If so, you keep looking in the first half of the array; otherwise, you look in the second half. That cuts the problem in half. If the array is very large, then this method is much more efficient. This algorithm is called binary search.
Collections class implements this algorithm. There are two versions for this method. They are
Collections.binarySearch(acollection, anElement);
Collections.binarySearch(acollection, anElement, aComparator);
A return value of nonnegative integer from the method denotes the index of the matching object. A negative value means that the target is not found. Try this simple program.
import java.util.*;
public class TestBinarySearch {
public static void main( String[] argv ) {
List
for (int i=0; i<=49; i++)
list.add(i);
Collections.sort(list); //make sure the list is ordered
int index = Collections.binarySearch(list, 37);
System.out.println("The index: " + index);
index = Collections.binarySearch(list, 59);
System.out.println("The index: " + index);
//the target is not on the list
}
}
No comments:
Post a Comment