CSC72002Object Oriented Programming

CSC72002
Object Oriented Programming
Topic 4
Collections
©
Southern Cross University
Developed and produced by Southern Cross University
Military Rd, EAST LISMORE. N.S.W. 2480. 2nd Session, 2018.
No part of this publication may be reproduced, stored in a retrieval system or transmitted
in any form of by means electronic, mechanical, photocopying, recording or otherwise
without the prior written permission of the publisher.
Copyright materials reproduced herein are used under the provisions of the
Copyright Amendment Act (1989).
Readings, if any, indicated in this work have been copied under section VB of the Copyright Amendment Act 1989
Copies, if any, were made by Southern Cross University in February, 2018
for private study only by students.
CAL LICENSED COPY – UNAUTHORISED COPYING PROHIBITED
CSC72002 Study Guide
4-3
Contents
COLLECTIONS ………………………………………………………………………………………………………………………………………4
References……………………………………………………………………………………………………………………………………………..4
Objectives………………………………………………………………………………………………………………………………………………4
Introduction……………………………………………………………………………………………………………………………………………4
The Collection interface ……………………………………………………………………………………………………………..4
The Iterator interface ………………………………………………………………………………………………………………………..6
Lists………………………………………………………………………………………………………………………………………………………7
ArrayList class………………………………………………………………………………………………………………………..8
LinkedList class………………………………………………………………………………………………………………………9
Static methods in the Collections class ……………………………………………………………………………………………..11
The Stack collections ……………………………………………………………………………………………………………………13
The Queue collection……………………………………………………………………………………………………………………..15
Sets……………………………………………………………………………………………………………………………………………………..16
Maps……………………………………………………………………………………………………………………………………………………18
Summary ……………………………………………………………………………………………………………………………………………..20
CSC72002 Study Guide Collections
4-4
Collections
References
Liang, Y.D. 2015. Introduction to Java Programming – Comprehensive Version, 10th Edition, Pearson,
USA. ISBN:978-1-292-07001-8.
Java Platform, Standard Edition 8 API Specification: https://docs.oracle.com/javase/8/docs/api/
Objectives
On completion of this topic you should be able to:
1. Use the Java collections API in your programs
2. Chose appropriate collections for different applications based on the collection data structure
3. Use lists, stacks, queues, sets and maps in your Java programs
4. Use iterators to process collections
5. Use utility methods to sort, search, fill and other processing of lists and collections
Introduction
In years past most IT courses had units on “Data Structures” in their curriculum. Such units were about
implementation and performance of various data structures known to provide different attributes for our
data and its organisation. In those days you were expected to be able to implement the data structures
using basic programming structures. With the advent of object-oriented technology, it is no longer
necessary to implement well known data structures as the code can be incorporated in APIs and re-used
in our programs. This topic is about what the data structures do, when to select them and how to re-use
the API implementation of each.
The Java Collections Framework is the Java APIs for us to implement data structures. It is not just a
set of classes for each data structure. It also defines common attributes of each data structure and allows
us to re-use code for different data structures and transfer data between them. In the latest versions of
Java, the Java Collection framework is implemented as generic classes and interfaces. This allows static
(compile-time) type checking of data resident in data structures. It also means you should be familiar
with generics which were covered in the previous Topic.
In this topic we will first look at the Collection interface, which is implemented by all collections to
give a standard interface. We will then examine the Iterator interface which is designed to provide
a standard way to process collection elements, regardless of the underlying structure of the data. The
remainder of this topic will look at the different types of collections provided by Java.
The Collection interface
To enforce a common set of methods in Java collections, all the classes that implement data structures
implement the Collection interface. This ensures they all provide a common set of methods and
allow some polymorphic procession of data, regardless of the data structure deployed.
Some of the methods in the Collection interface are as follows. Note that this means they are
implemented in all collections!
CSC72002 Study Guide Collections
4-5
boolean add(E e) – add element e to the collection. Return true on success.
boolean addAll(Collection c) – adds collection c to this collection.
Returns true if something added. Notice that elements of a subtype of the current type may
be added.
void clear() – clear all data from the collection.
boolean contains(Object o) – return true if the given object is in the collection.
boolean containsAll(Collection c) – return true if all the objects in the given
collection c are in this collection.
boolean isEmpty() – return true if collection is empty
Iterator iterator() – return an iterator to process collection elements.
boolean remove(Object o) – remove one object o from the collection.
boolean removeAll(Collection c) – remove all the objects in given collection c from
this collection.
boolean retainAll(Collection c) – retain the objects in given collection c in this
collection and remove all others.
int size() – return number of elements in the collection
E[] toArray() – returns an array containing all the elements in the collection.
In the following sections we will not always redescribe these methods with each of the collection types.
You can assume these methods are implemented in each of the collections we look at.
You may have noticed there is no member function for retrieving elements from collections, except for
the iterator() member function. This is because there are different ways to retrieve elements
depending on the data structure. You will see the different methods in the following sections.
Notice that the Collections wildcard is used as a parameter to several methods in the
Collection interface. You will recall from the previous topic that this is equivalent to extends Object>. This means that a collection of any type of object can be used as a parameter,
even a different type than the collection itself. If you look closely at the members that use this, you will
see that they are all involved in making comparisons between objects so that an object of an incorrect
type will not impact the current collection objects.
The iterator() method requires further explanation because it returns an Iterator object. We
will look at that in the following section.
CSC72002 Study Guide Collections
4-6

YOU MAY ALSO READ ...  Consider developments, policies, and laws in that period from 1865 to the 1920s.
 Activity x-1: The Collection interface
1. Read the textbook Section 20.1-20.2 (pp 784-787). This reading gives an overview of
the Java Collection Framework as well as discussing the Collections interface.
2. Review the ArrayList example from the previous Topic. You will see we used the
add() and size() member functions in our examples. Implement a small program
that does the following using the ArrayList implementation of the following
Collection member functions:
– Create an ArrayList object and add elements with the add()
method.
– Print out the size of the ArrayList (number of elements) using size()
– Try removing one element using the remove() method. You should print all the
element to check that this works.
– Try checking if one of your elements is in the collection. You will know it is but
check by code an if statement using the contains() member function.
– Create a second ArrayList object with a few elements and add all
the elements to your first object using the addAll() member function. You will
need to print out all the elements to check it worked.

Next, we look at the Iterator interface.
The Iterator interface
In the previous section we mentioned the Iterator interface. This interface is used to provide a
standard way to process each of the elements in any collection. It is designed to process collection
elements regardless of the underlying structure of the collection.
Iterator is an interface with four member functions as follows:
void forEachRemaining(Consumer action) – apply the action functional
form to each of the remaining elements in the iteration.
boolean hasNext() – returns true if there any remaining elements in the iteration
E next() – returns the next element in the iteration (moving forward in the collection)
void remove() – removes the last element returned by next() from the underlying collection
Now, if you have not seen the Iterator interface before you will take a while to see how to use it.
The basic operation is to process a collection by calling next() to return the next element and repeat
while the hasNext() member function returns true. For example, the following code will print all
the elements in an ArrayList collection (we saw ArrayList in the previous Topic).
ArrayList ilist = new ArrayList();
//.. add some elelemnts
Iterator iter = ilist.iterator();
while (iter.hasNext())
System.out.println(iter.next());

The forEachRemaining() member function is a recent addition to this interface to make use of
lambda expressions. As an example, we can process the above ArrayList identically using the code.
iter=ilist.iterator();
iter.forEachRemaining( i -> System.out.println(i); );
Notice that the second example must create another iterator. Once the iterator reaches the end of the
collection it cannot be restarted. You must get another iterator!
CSC72002 Study Guide Collections
4-7

 Activity 4-1: Generics example ArrayList
1. Read the textbook Section 20.3 (pp 788-789).
2. Implement the above example. Don’t forget to get a new iterator each time you want
to process the collection.
3. Try the remove() iterator member function to remove one object from the collection.
Print out the collection again to make sure you removed the one you thought you did.

We will now look at some of the Java collections.
Lists
We have already used one type of list implemented by the ArrayList class. It is not the only type
of list in the Java collections. In fact, the lists are implemented as shown in the UML class diagram
(Figure X.1).
As you can see the common list methods are specified by in the List interface and the ArrayList and
LinkedList classes implement them as well as some methods unique to each type of list.
It is important to note, and you will see in the reading
below, this is not the actual implementation. The Java
API also introduces several abstract classes that sit
between the interface and concrete implementation.
However, this diagram shows the interfaces and
classes we are likely to use in our programs.
You will recall that interfaces in UML are shown in a
class diagram with italic font. The dashed line
showing inheritance with the open arrow represents
interface implementation.
Some of the important member function of the List
interface, and therefore implemented in both the
ArrayList and LinkedList classes, are as follows.
add(index, elt) – add element at index
addAll(index, collection) – adds collection of elements at index
get(index) – return element at index
indexOf(elt) – returns first index of object elt
lastIndexOf(elt) – returns last index of element
listIterator() – returns a list iterator
remove(index) – removes object at index and returns it
set(index, elt) – replaces the element at index with elt retuning old element
subList(fromIndex, toIndex) – return a sub-list as a List object
Now you should remember from the above diagram that List is a sub-interface of Collection . This
means all the member functions discussed in the previous section are also inherited into the List
interface. The ones listed here are just the new ones for List collections.
You may have noticed that the listIterator() member function does not return an Iterator that
we discussed in the previous section. It instead returns a ListIterator which is a sub-interface of
the Iterator interface. Of course, since List is a sub-interface of Collection, it also specifies the
iterator() method which does return an Iterator. However, the ListIterator is a more
powerful iterator which is only available in List data collections.
The ListIterator has member functions for navigating a list in both a forward direction (inherited
from Iterator) and in a reverse direction. It also allows replacement of elements at the current position
CSC72002 Study Guide Collections
4-8
and insertion of elements. The interface has the following member functions in addition to those
inherited.
add(elt) – adds an element to the list from which this iterator was obtained
hasPrevious() – true if there is an element before the current position
nextIndex() – returns index of next element
previous() – returns previous element in the iterator
previousIndex() – returns index of the previous element
set(elt) – replaces current element and returns the one replaced
Careful when you read these descriptions. An iterator is not the actual collection, it is just an object that
links to the actual collection. The extra methods above allow you to change the original collection
because the ListIterator can maintain links to the original collection.
As an example of using the additional iteration methods, suppose we had a ArrayList
collection declared and initialised as follows.
ArrayList colours = new ArrayList();
colours.add(“red”);
colours.add(“green”);
colours.add(“blue”);
colours.add(“pink”);
Now we can use a ListIterator to print out all the elements just as if it was an Iterator object.
ListIterator liter = colours.listIterator();
while (liter.hasNext())
System.out.println(liter.next());

But we can also print out the list in reverse. Assuming the above code was executed first, the following
code will print out the list backwards. Note that the above code must be executed first to make sure the
current iterator position is past the end of the list.
while (liter.hasPrevious())
System.out.println(liter.previous());

We will try this in the following activity.

 Activity 4-2: The List interface
1. Read the textbook Section 20.4 and 20.4.1 (pp 789-791).
2. Using code like the above, print out each element of an ArrayList object on the
console from first to last, and then print the elements out from last to first, all using the
one ListIterator object.
3. Try replacing an element using the list iterator above. Try moving along the list with
the iterator, say 1 or two elements, then replace the object. Then, to prove it worked,
get another iterator and print the whole collection on the console.

We will now look at ArrayList object.
ArrayList class
ArrayList is a concrete implementation of the List interface. You will already understand
how an ArrayList works because we have used it as an example of generic classes in the previous
Topic. However, the reasons why it is called an “Array” list may not be clear. Now that you know
there is also a LinkedList collection class you will probably be wondering what is the difference.
You will need to choose between the two types of list at some stage.
CSC72002 Study Guide Collections
4-9
The key difference between ArrayList and LinkedList is that is the ArrayList uses an array as
the implementation data structure, hence the name, and LinkedList uses a data structure called a
linked list, or more correctly a doubly linked list. We will discuss linked lists further in the following
section.
You will know from your previous programming that an array is an efficient way to organise data that
is accessed with an index. In the interfaces Collection and List we have seen that an index is an
access mechanism in the methods that are required to be implemented. However, you will also know
from your programming experience that array do have some programming limitations. First, arrays
have a fixed length which means we need to know in advance how many elements are likely to be used.
This puts a limitation on our code and possibly wastes memory space when we never use all the
elements.
An ArrayList data structure hides the limitation of arrays. It allocates an initial array and resizes it
invisibly as you add elements to the data structure. This makes it much easier to use because a
programmer does not have to worry about the array size at all. However, internally it creates and
destroys arrays which may be inefficient when the arrays get large.
The ArrayList class implements all the List members but has some member function unique to
the ArrayList class.
ArrayList() – default constructor which allocates a default size array
ArrayList(initialSize) – allocate initialSize array for the internal list data structure
trimToSize() – reduce the internal array to fit the current number of elements
Most programmer do not have to worry about the last two constructor/member functions. Usually we
just rely on the default array management for our programs because the space usage does not become
an issue. However, in very large arrays or very small memory devices the programmer may have to
manage the memory space used by a program and this constructor and method allow that to be achieved.
It is also possible in some uses of the data structure that result in constant resizing of the implementation
array can cause performance problems. In such cases the programmer can force a very large initial
array with the above constructor, and reduce the array after the data structure is more stable.

 Activity 4-3: ArrayList
1. Create a new ArrayList object (or re-use one you implemented previously). Use the
constructor to initialise the internal array to 10,000 elements. Add a few elements and
then call the trimToSize() method. Did you notice anything different? (Hint:
unless you have a computer built last century you will should not notice any
performance difference)
You have already used the other methods of the ArrayList objects in the previous topic
so we will not repeat the exercise here.

We will now look at the LinkedList collection, which we have not seen before.
LinkedList class
LinkedList is another concrete implementation of the List interface. The internal
implementation is not the efficient array structure of the ArrayList class, but is what is called a doubly
linked list.
A doubly linked list is a collection of objects connected by references in both direction. You will
remember from the Topic on run-time structures that a reference in Java is a directional connection
between a variable or attribute of an object and another object. A doubly-linked list has references in
both directions, that is a reference to the next object and reference to the previous object. Figure x.2
uses the box and arrow diagrams introduced previously in this unit to show references between objects
in a doubly linked list.
CSC72002 Study Guide Collections
4-10
Figure x.2 – doubly linked list
To implement this in Java, each node in the list has hidden two references shown in this diagram, for
example the Java implementation can have two attributes similar to the following.
class Node {
Node next; // reference to the next node in the data structure
Node previous; // reference to the previous node

As we add and delete elements of the data structure, these two references must be updated. You can
probably see how the ListIterator objects can easily implement the next() and previous()
methods. The LinkedList object simply maintains a reference to the current element and is assigned
the next or previous attribute to move up and down the list.
So, what is the difference between an ArrayList and a LinkedList object? There are two
things to consider:
1. The implementation of the ArrayList is more efficient at accessing individual elements but is
inefficient if the number of elements changes frequently because the array must be recreated
frequently. The LinkedList implementation just adds or removes an element using Java
assignment statements.
2. The LinkedList class add some traditional list processing methods that are not implemented in
the ArrayList class. This makes traditional algorithms for processing list more familiar to
programmers and allows implemented of some additional data structures based on lists (see
following sections).
The additional methods added by the LinkedList class are as follows.
getFirst() – return the first element (the head) of the list
addFirst(elt) – add an element to the head of the list
removeFirst() – remove and return the head of the list
getLast() – return the last element (the tail) of the list
addFirst(elt) – add an element to the tail of the list
removeFirst() – remove and return the tail of the list
You should probably have realised that these could have been implemented for an ArrayList object
but were not. The reason is (the author believes) that the add and remove operations would force an
array resize operation which is very inefficient, so the lack of methods helps the user choose the more
efficient LinkedList data structure.
As an example of the linked list structure, the following code adds strings to the start of the list by
querying the user on the console. The loop completes when an empty string is entered.
LinkedList slist = new LinkedList();
Scanner input = new Scanner(System.in);
System.out.println(“Please enter strings and blank to finish”);
String text = input.nextLine();
while (!text.equals(“”))
slist.addFirst(text);
text = input.nextLine();

Note that the efficiency consideration for this choice of LinkedList over an ArrayList are not as
important as if the list was added to with more strings or much more often as an array resize operation
would not be noticed by the user in this case. This does, however, demonstrate the list operations only
available to LinkList collections.
CSC72002 Study Guide Collections
4-11
We can then remove all the strings from the tail of the list displaying them as we go using the following
code. The list will be empty after this code!
while(!slist.isEmpty())
System.out.println(slist.removeLast());

Now this code processes the list from the last element to the first. You should consider carefully how
this works when you implement it in the following activity. It is not uncommon to process lists by
inserting at the start and removing from the end. This is probably a new idea for you.

 Activity 4-4: LinkedList
1. Read the textbook section 20.4.2 (pp 791-793). This section also covers ArrayList
but it allows comparison between the two structures which has been discussed in this
section.
2. Implement the above example of a LinkedList and test it. Think carefully
about why the strings are output in the order that they are. We are adding to the start
of the list and removing from the end of the list which you may not have programmed
before!
3. Modify the above code to print out the list without removing the elements. You can
use a ListIterator that we saw in the previous sections.
4. Modify the above code to print out and empty the list from the first element instead of
the last. As before, make sure you understand why the strings are printed in the order
that you see on the screen.

Next, we will look at a class called Collections which has a variety of static methods useful for
processing lists and collections.
Static methods in the Collections class
Now that we have looked at the collections ArrayList and LinkedList we can have a closer
look at some static methods that are provided in the Collections class (java.util.Collections).
Just in case you missed it, Collections (plural) is a class and Collection (singular) is an
interface we have discussed previously. The Collections class implements some static methods that
take List arguments and some methods that apply to any collection that implements the
Collection interface.
The methods allow sorting, searching, reorganising, copying and filling lists. There are also general
collection methods for finding maximum values, minimum values, comparing lists and counting
specific elements of a collection.
To use these methods there is extensive use of the Comparable and Comparator interface.
We looked in detail at the Comparable interface in the previous Topic as an example of a generic
interface. Implementing Comparable requires implementation of the single method:
int compareTo(E o)
The Comparator interface allows implementation of comparison operation in standalone objects.
It has a single comparison operation:
int compare(E elt1, E elt2)
The difference between the two interfaces requires some thought. The Comparable interface is
implemented in the object of the type to be compared. This means it is bound to that class and will
always produce the same comparison between two objects of that type. The Comparator interface, on
the other hand, implies that the comparison is performed by some object that is usually a different type.
Further, two classes that implement a Comparator interface can do the comparison between the same
objects differently. This means that the same method that takes a Comparator as an argument can
produce different results if a different comparator implementation is given as the argument.
Some of the List based method implemented as static methods in the Collections class are:
CSC72002 Study Guide Collections
4-12
sort(List list) – sorts the list using the Comparable implementation of the elements
sort(List lst, Comparator c) – sorts the list using the comparator to compare elements
binarySearch(List list, Object o) – searches the list for object o returning its index
binarySearch(List list, Object o, Comparator c) – searches the list for object o using
comparator c returning index of object
reverse(List list) – reverses the order of elements in the list
reverseOrder() – returns a Comparator object that provides reverse ordering
shuffle(List list) – randomly shuffles elements in the list
shuffle(List lsit, Random r) – randomly shuffles the lists using the randomising object
copy(List dest, List src) – copies source list to the destination list
nCopies(int n, Object o) – returns a list containing n copies of object o
fill(List list, Object o) – fill existing list with object o
There are quite a few operations here that may be useful to your list programming.
The binarySearch() methods may require more explanation. It assumes the list is sorted before the
method is called. Binary search is an algorithm for quickly finding an element in a sorted data structure
and is important when lists get very large. You may know it as a “divide and conquer” strategy. It
works by selecting elements half way between the start and end points and then comparing values. It
will then know if the element being searched for is before or after the half way point. Knowing that it
recursively picks the half way point again from the selected side. This repeats until the element is found
or there are no elements left to search. This algorithm is much faster than a sequential search through
the list and is applicable to any sorted data. There are faster ways to search ordered data but you would
have to implement them yourself.
The shuffle() method needs some explanation of the Random object. The version that has no Random
object parameter will produce a different arrangement of elements each time it is called with the same
list parameter. To ensure the same shuffled list is produced each time we must use a Random object
parameter with the same seed each time. For example, ensure the same random shuffling is applied to
identical lists we can use the Random object constructor to apply the same random seed. You will see
examples in the reading below.
The reverseOrder() method returns a Comparator object that can be applied to reverse
implemented ordering of the elements of the list. This object can be used in the other methods to
produce reverse ordering, i.e. sort() and binarySearch().
Now some examples of Java code follow. First, we can sort a list in its natural order by calling the
sort() method as follows.
List list2 = Arrays.asList(“one”, “two”, “three”, “four”);
Collections.sort(list2);
System.out.println(list2);
This code displays the following on the console.
[four, one, three, two]
Note that this example also introduces the Array.asList() static method which returns a List object
based on its list of arguments. It makes our simple collection initialisation examples much more concise.
This code also uses the default toString() method of the given list to display the contents of the list.
You would have to override the toString() method in ArrayList or LinkedList objects if you
wanted your own default format.
Now as an example of using a Comparator implementation to sort the list, we can use the
reverseOrder() method. The following code prints the list in reverse order.
Collections.sort(list2, Collections.reverseOrder());
System.out.println(list2);
This displays the following on the console.
CSC72002 Study Guide Collections
4-13
[two, three, one, four]
Now, the above methods only cover those that apply to List objects. Collections also has static
methods that apply to any Collection implementation. These are as follows.
max(Collection c) – returns maximum
max(Collection c, Comparator comp) – returns maximum using comparator
min(Collection c) – returns minimum
min(Collection c, Comparator comp) – returns minimum using comparator
disjoint(Collection c1, Collection c2) – returns true if c1 and c2 have no common
elements
frequency(Collection c, Object o) – returns number of times o appears in collection c
We will look at example of using these methods in the activity below.

 Activity 4-5: The Collections static methods
1. Read textbook Section 20.5 (pp 794-795). The difference between Comparable and
Comparator interfaces is explained at the start of the section but the code does not
show the equivalent Comparable implementation.
2. Read textbook Section 20.6 (pp 795-799).
3. Create a list of at least 5 strings using the asList() method shown above and in the
reading. Print the contents on the console.
4. Sort the list and print the contents again.
5. Sort the list in reverse order using the Comparator generated as shown above. Print it
out again.
6. Create a second list with only two strings that are both different to the ones in the first
list. Copy the new list to the first list and print the result. Make sure you understand
what is printed here.
7. Shuffle the list and print it out again. Verify it is in random order.
8. Print out the maximum and minimum value in the list using the max() and min()
member function.
9. Fill the list with the string “*empty*” and print the list again on the console.
Although there are a lot of exercises here, you should be able to place the code for each one
after the other in the same program and verify the results by looking at the console output.

Next, we look at the stack collection.
The Stack collections
A stack is a data structure that is meant to be accessed in a unique way. It implements a data structure
which allows values to be placed (pushed) into the data structure and then removed (popped) in reverse

order. This is known as a last-in-first-out data structure, or alternatively, a first-in-last-out data
structure.
Some useful members of the Stack class are as follows:
E peek()
E pop()
– get a copy of the object on top of the stack (no pop)
– remove and return the object from the top of the stack

e push(E elt) – push an object onto the stack
bool empty() – return true if stack empty
The Push() member is used to place objects on the stack. For example, we can create a stack and place
four objects on it as follows.
CSC72002 Study Guide Collections
4-14
Stack stuff = new Stack();
stuff.push(“box”);
stuff.push(“plate”);
stuff.push(“toy”);
stuff.push(“ball”);
So far this is like other data types where we use the add() member. To help understand how the stack
data structure works Figure x.3 shows a diagram of the stuff data structure after the above code
sequence.
“toy”
“plate”
“box”
“ball”
more objects pushed here
Peek() returns this object and
PoP() removes it from stack
Figure x.3 – the stuff stack after initialisation.
The similarity ends when we want to examine or remove items from the stack. We can only look at the
top of the stack and remove items from the top of the stack. For example, the following statement will
print out “ball” since the top of the stack is the last item added with the push() method.
System.out.println(stuff.peek());
The pop() operation is like a peek() except that in addition to returning a copy of the top of the stack,
it removes the item from the stack. Continuing the above example, the following additional code
sequence will print “toy” on the console.
stuff.pop();
Console.WriteLine(stuff.pop());
Make sure you understand why “toy” is displayed. Figure x.4 shows the status of the stuff stack after
the above code segment. The first pop() operation removes “ball” from the stack and the second
removes “toy” but prints the “toy” string since it is returned to the program by the pop() method.
“plate”
“box”
Figure 7.3 – the stuff stack after two pop() operations.
When using loops, we also need to know when the stack is empty, which will cause the pop() operation
to fail. We can do this by checking whether the empty() method returns true. For example, the
following code sequence will print all the remaining members in the stack as it removes them one-byone.
while (!stuff.empty())
System.out.println(stuff.pop());
It may not be obvious where a stack data structure is useful. For many applications, a stack can make
your coding much simpler when you need to process data in a last-in-first-out manner.
The Stack class is derived from the Vector collection, which is essentially the same data
structure as the ArrayList collection class. We mention Vector here because it is the base
class of the Stack collection class and it is a different type of collection. The difference between
Vector and ArrayList is that Vector is synchronised, which means that it can be used in parallel
programming without the risk of corrupting the data. We will look at synchronised methods in the
Topic on parallel programming. Because of the added safety of Vector, it is also less efficient than
the ArrayList implementation.
CSC72002 Study Guide Collections
4-15
Also, because the Stack is derived from the Vector class it has many of the List methods that
can be used to access the stack data as we have in the other collections covered so far. For example, we
can print out the contents of the stack using an iterator as follows.
Iterator iter = stuff.iterator();
while (iter.hasNext())
System.out.println(iter.next());
Note that this prints out the stack in order of the data in the data structure. This is the reverse order to
the data printed with the above pop loop!
Normally, because of the choice of the stack data structure, a programmer will only use the specific
Stack class methods. However, there may be occasions to process the stack like a general collection.
For example, the iterator above allows access to the whole stack. Other methods may be useful if used
in special situations, e.g. search() can be used to see if an object is in the stack and the get() method
can be uses to extract individual elements from the middle of the stack.

 Activity 4-6: Stacks
1. Read section 19.8 (pp 803-804). This reading also explains the history of the Vector
class, which has been available since Java 2.
2. Implement the simple stack example above, pushing the elements on the stack and then
printing them all out using the pop() operation as shown.
3. Add some more elements using the push() operation and then print the stack using
the iterator as show above. Notice how this is the reverse order of the data printed in 2.
4. Try some of the inherited List methods, e.g. search() and get().

Next, we look at another data structure called a queue which is related to the stack.
The Queue collection
A queue is a data structure that, in contrast to a stack, implements a first-in-first-out data structure. In
other words, elements are placed at the end of the data structure and extracted from the beginning of the
data structure. It also is implemented as an interface, which means other classes implement the queue
interface, the LinkedList class we have already seen implements the Queue interface.
The Queue interface requires implementation of the following methods.
offer(E elt) – inserts an element in the queue
poll() – removes and returns the head of the queue
peek() – returns without deletion the element at the head of the queue (null if empty)
element() – returns without deletion the element at the head of the queue (exception if empty)
Notice how the last two members are equivalent except for when the queue is empty. The peek()
method behaves like the stack peek() method. The element() methods throws an exception when
the queue is empty.
As an example, the following code creates a queue with the same four string elements as we used in the
stack example.
Queue moreStuff = new LinkedList();
moreStuff.offer(“box”);
moreStuff.offer(“plate”);
moreStuff.offer(“toy”);
moreStuff.offer(“ball”);
Notice how we have created a new queue by creating a LinkedList object and assigned it to the Queue
interface variable. LinkedList implements the Queue interface but other LinkedList methods will
not be available to this object reference. If we wanted to use LinkedList methods as well as the
Queue interface methods, then we would need a LinkedList reference. For example, we could have
replaced the above declaration with the following code.
CSC72002 Study Guide Collections
4-16
LinkedList moreStuff = new LinkedList();
This would make the LinkedList methods also available using the moreStuff reference.
We can remove each element and display it on the console using the poll() operation. Note that this
will print the elements in the reverse order to the stack example in the previous section.
while (moreStuff.peek() != null)
System.out.println(moreStuff.poll());
This code used the peek() method to check that the queue is not empty and to terminate the loop when
it is.
In this case, we can also call all the LinkedList methods to access the data. However, other data
structures that implement the queue interface may not have the same methods so it is best to just assume
that the queue methods are available.
In the reading below you will see there are also Deque and PriorityQueue data structures. While
these may be useful to you in future, we will just cover the basic Queue structure in this Topic.

 Activity 4-7: Queues
1. Read section 20.9 (pp 805-807). Just skim the information on the DeQue interface and
the PriorityQueue class as you are not required to use this in this unit.
2. Implement the simple queue example above, adding elements to the queue and then
printing them all out using the poll() operation.
3. Add some more elements using the offer() operation and then print the stack using
an iterator. Notice how this is the same order as the data printed in 2.

Next, we look at sets.
Sets
There are several kinds of sets implemented in the Java Collection framework. All implement the
Set interface so that a common set of methods can be applied to all sets. We will look at the
HashSet implementation but there are also TreeSet and LinekedHashSet classes that
we will not have time to examine.
A set models a mathematical set. It is different to the collections we have looked at so far because a set
has the property at no two elements are equal. Here “equal” means the Object class equal() method
returns true, or a overridden definition of the equal() method returns true.
The Set interface implements the Collection and Iterable interfaces that we have
seen before. Some of the Set methods are as follows.
add(E o) – add an object to a set if it is not already a member
addAll(Collection c) – add a collection to the set
clear() – empty the set
contains(o) – returns true if the object is in the set
containsAll(Collection c) – returns true if all the collection is in the set
isEmpty() – returns true if the set is empty
iterator() – returns an iterator for all the elements
remove(o) – removes an object from the set and returns true if success
removeAll(Collection c) – removes collection from set and returns true if all removed
retainAll(Collection c) – retains only the objects that are in the given collection
size() – returns the size of the set
CSC72002 Study Guide Collections
4-17
toArray(E[] a) – returns an array containing all the elements of the set
If you are familiar with mathematical sets than you can probably spot how the common set operations
correspond with the mathematical set operations:
set union corresponds to addAll()
set intersection corresponds to retainAll()
set element-of corresponds to contains()
set difference corresponds to removeAll()
Now the concreate implementation we will look at is the HashSet class. A HashSet is
implemented using what is known as a hash table. It is a very efficient implementation that allows
looking up an element to be achieved using very few operations. It works by having a computation of
a hash code associated with every object that is to be stored (you may remember the hash() member
function of the Object class which computes a hash code for every object). The hash code is mapped
to unique entries in the hash table. The objects themselves are stored at the location specified by the
hash table. More than one object may map to the same hash code so when there is a clash the objects
stored there must be searched in sequence to check if the object is stored. The implementation of
HashSet automatically adjusts the size of the hash table so the search for an object never has too
many objects stored at the one hash code.
Luckily, the implementation of a HashSet object is hidden to us so we do not have to worry about
the details of how the hash table is implemented. There is a constructor to allow us to specify the size
of the hash table but the default size will be fine for our purposes.
The following code creates a set and adds some elements to the set. Notice that we add the same element
twice.
Set colours = new HashSet();
colours.add(“red”);
colours.add(“white”);
colours.add(“blue”);
colours.add(“puce”);
colours.add(“blue”);
We can then use an iterator to print out the contents of the set as follows.
Iterator iter = colours.iterator();
while(iter.hasNext())
System.out.println(iter.next());
This prints on the console the following values.
red
puce
white
blue
Notice that the string “blue” is printed only once. This is because the add() operation only adds unique
values and does return an error when a duplicate value is added. You should also note that the objects
are printed out in a different order than they were inserted in the HashSet object. A HashSet object
does not maintain an ordering (however a TreeSet does).
CSC72002 Study Guide Collections
4-18

 Activity 4-8: HashSet examples
1. Read section 21.1 and 21.2.1 (pp 820-823). This reading has a UML diagram of how
all the Set implementations are derived.
2. Implement the above HashSet object and display it on the console. Make sure you add
the same string twice and verify that each element is only added once.
3. Create another hash set object and add some different elements. Use the addAll()
method to add it to the original set. Verify that it acts like set union by printing out the
values.
4. Create another hash set object with several strings that are also in the previous
collection. Use the retainsAll() method of the set from 3 with this as argument.
Verify that it acts like set intersection by printing out the values.
5. Create another HashSet object with a few identical strings to the set object in 4 and
use the removeAll() method of the set in 4. Verify that it acts like set subtraction by
printing out the values.

Next, we look at maps.
Maps
A map is yet another data structure that is different than the previous ones because it has two data types
involved. A map object maps a key object to a value object. The Map interface defines the
methods required for a map object. As you can see there are two type parameters: K corresponding to
the key type and V corresponding to the type of the value object. Like we did for sets, we will look at
the Map interface and then look at one of the implementations in the HashMap class.
On way to think of a map as being like a database table. The key is the unique object used to look up
the value (record) associated with the key. In a map in the Java Collection Framework, it is not
uncommon for the key to be also part of the stored object.
Probably the best way to understand a map is to look at the methods that can be applied. A Map
implementation requires the following methods (amongst others).
get(key) – return object (type V) stored with this key in the map
put(K key, V val) – associate val with key in the map
clear() – remove all entries in the map
containsKey(key) – returns true if the key is associated with an object in the map
containsValue(val) – returns true id val stored in the map
entrySet() – returns a set object with all the key/value pairs in the map
isEmpty() – returns true if map empty
remove(key) – removes key/value pair associated with this key
size() – return number of key/value pairs in map
keySet() – returns set of all keys in map
values() – returns collection of all values in map
Now the Map class has an inner interface called Map.Entry which allows access to the
key/value pair data as a separate object. This is an alternate way to process a map. It is an interface to
key/value pair objects that have the following methods implemented.
getKey() – return the key
getValue() – return the value
setValue(val) – replace the value with val
CSC72002 Study Guide Collections
4-19
To see how this all works we will need to look at a concrete implementation of the interface. As with
sets, we will look at the hash table implementation call HashMap and we will leave the
LinkedHashMap and TreeMap implementations due to lack of time in this unit.
The following code creates a new HashMap object with String keys and Integer values. We add
four key/value pairs to collection.
Map map1 = new HashMap();
map1.put(“red”, 7);
map1.put(“white”, 1);
map1.put(“blue”, 3);
map1.put(“green”, 1);
Now we can retrieve any value using the get() method. For example, to retrieve the value associated
with the string “red” we can code:
String redVal = map1.get(“red”);
If we want to print all the key/value pairs we can use the default toString() implementation, e.g.
System.out.println(map1);
Which prints on the console the following string.
red=7, green=1, white=1, blue=3
Notice again that the HashMap implementation does not maintain the ordering of the keys or values.
As with sets, the TreeMap implementation does maintain the ordering.
If we want to print our own format we have two ways to access all the entries. First, we can extract all
the keys and then print the data separately, e.g.
Set keys = map1.keySet();
Iterator iter = keys.iterator();
while (iter.hasNext())
String key = iter.next();
System.out.println(“key = “+ key + “, value = ” + map1.get(key));

The second way to process all the data is to extract all of the key/value pairs as a set of
Map.Entry objects. An example of this methods is as follows.
Set> ents = map1.entrySet();
Iterator> iter2 = ents.iterator();
while (iter2.hasNext())
Map.Entry ent = iter2.next();
System.out.println(“key = “+ ent.getKey()
+ “, value = ” + ent.getValue()
);

Both of the above code segments print the following.
key = red, value = 7
key = green, value = 1
key = white, value = 1
key = blue, value = 3
The choice of whether to process a set of individual keys or a set of key/value pair objects is up to you.
We have not shown it here but there are other ways to process a Map object. For example, if you did
not care about the keys, the getValues() method will return a set of values to be processed using the
methods in the Set interface.
CSC72002 Study Guide Collections
4-20

 Activity 4-9: Maps
1. Read Section 21.5 (pp 832 – 835). You do not have to worry about the TreeMap
details, though there is an example of using the TreeMap class constructor to sort a
HashMap that may be useful to you.
2. Implement the above HashMap and print out the key/value pairs in each of the three
ways shown.
3. Implement another HashMap, this time with both keys and values as strings, i.e.
HashMap. Add some keys and values, e.g. use first names and
last names like key “Donald” and value “Duck”. Print out the values using one of the
techniques shown.
4. With the HashMap from 3, remove one of the key/value pairs.
5. With the HashMap from 3, print the number of key/value pairs and print all the keys
(without values).

HashMap objects are very useful in many programming applications.
Summary
In this Topic we have looked all the Java Collection Framework. We have not looked at all the Java
collections as this would have taken too long. However, we have looked at one of the implementations
of each of the general data structures available.
We started by looking at the Iterator interface which allows us to process collections. We then
looked at the Collection interface which provides common methods for all the Java collection
classes. Lists were then examined which provide a way to store an ordering of objects. The
Collections class provides a set of static methods for processing any type of collection. Stacks and
queues were then examined and we saw how these enforce an access mechanism on the data structure.
Stacks are last-in-last-out data structure, whereas queues are first-in-first-out. We then looked at the
Set interface and its implementation in HashSet objects which are collections that have unique
elements and are based on the mathematic sets you have learned about previously. Finally, we looked
the Map interface and its implementation in HashMap objects which are storage for key/value pairs.

CLICK HERE TO GET A PROFESSIONAL WRITER TO WORK ON THIS PAPER AND OTHER SIMILAR PAPERS

CLICK THE BUTTON TO MAKE YOUR ORDER

YOU MAY ALSO READ ...  The ethical theories called RELATIVISM and SITUATION ETHICS seem to be rampant in our society today many times