ITB6008
Unit 8: Data Structures and The Java Collection Classes
Data Structures
Data Structure :
• A collection of data organised in some fashion
• Manages a collection/group of data items (objects)
• Provide a range of operations to work on the data:
• Insert/Add
• Remove
• Sort
• Find/Search
• Hides the implementation of the above actions from the
programmer’s view
• An example of a data structure we already learned about is the
ArrayList. Java provides several more data structures – commonly
know as the Java Collections Framework.
Java Collections Framework
<<interface>>
Collection
<<interface>> <<interface>> <<interface>>
Set List Queue
Hash Set <<interface>> ArrayList
Sorted Set Linked List Priority Queue
Linked Hash Set <<interface>>
Navigable Set
Tree Set
Java Collections Framework - Map
<<interface>>
Map
Maps don’t extend from
[Link] but
they are still Abstract Map <<interface>>
Sorted Map
considered to be part
of the Collections
Framework in Java.
Hash Map
<<interface>>
Navigable Map
Tree Map
Java Collections Framework - Benefits
• Reduces programming effort: By providing useful data
structures and algorithms, the Collections Framework frees you
to concentrate on the important parts of your program rather
than on the low-level "plumbing" required to make it work
• Increases program speed and quality: This Collections
Framework provides high-performance, high-quality
implementations of useful data structures and algorithms.
• Allows interoperability among unrelated APIs: The collection
interfaces are the language by which APIs pass collections back
and forth.
• Fosters software reuse: New data structures that conform to
the standard collection interfaces are by nature reusable.
Collections – Visual Interpretation
• A Collection is a class which provides an interface to the data structure.
• The Collection Object has some set of elements that it manages
The collection object
The elements
The exact manner in which it manages them is determined by
the type of data structure it implements internally
Variety of Ways to Manage Collections
• There are different ways to organise a collection of
data of some common type:
• List
• Map
• Set
ADT: List
• The List ADT is for an ordered collection of elements
accessed by integer indexes
• You can add to the end of the list
• You can access any element of the list using the
element’s index
• You can remove an element at a particular index – other
elements will be “moved left” by one index.
• You can search for an element
• If the list is sorted, you can search relatively quickly.
ADT: Map
• The Map ADT is a collection of key-value pairs.
• The key is some value that uniquely maps to a particular
element
• Examples:
• a Dictionary contains words, which maps to definitions of the
word.
• A Customer number maps to the corresponding Customer object
• An account number maps to the corresponding Account object
• Using the key, you can quickly obtain the associated data
(the value)
• Multiple keys could map to the same value (alias)
ADT: Set
• The Set ADT is a collection of elements that is guaranteed to
contain no duplicates
• Often Sets are compared against each other, or joined
• Find the difference
• Find the similarities
• Find the combination of the elements
• Example:
• Find the commonalities between set of products purchased by
different customers – e.g. does everyone who bought bread, also
buy milk?
• Find the differences between people – what things do people
generally buy when they buy socks
Implementations of Collections
• Collections can generally be implemented with two
underlying implementation structures : array-based
structures or link-based structures.
array
Linked-list
Arrays
• Built-in support in the Java programming language, in
different forms (both static & dynamic).
• Available in almost every high-level programming
language.
• Map easily to underlying machine memory
architecture.
• Use indices to access individual elements.
• Access speed is typically constant – independent of an
element’s position.
Linked-List
• Can be implemented in every language that supports
references or pointers.
• Each element of the data structure (called a node), contains
2 things:
• A reference to the actual data,
• a reference to another node, (i.e. a “link” or component of the
structure)
• The final node typically has a link to “null”
• Elements are not necessarily stored in consecutive positions
in memory. (cf. Array)
• Access speed is dependent of an element’s position in the
Generics
• Generics enable types (classes and interfaces) to be
parameters when defining classes, interfaces and methods
• Similar to formal parameters used in method declarations,
type parameters provide a way for you to re-use the same
code with different inputs
• The difference is that the inputs to formal parameters are
values, while the inputs to type parameters are types.
Generics
• “Generics” was introduced in Java 5.0
• Example:
public class Example<T>
{ Type Parameter
private T data;
public void setData(T newData)
public Example<String> word;
{ data = newData; }
…
public T getData()
{ return data; } word = new Example<String>();
}
word’s setData() method will
expect a String reference
Generics
• Generics add stability to your code by making more of your bugs detectable
at compile time – much easier to deal with bugs at compile time than at
runtime
• It was added to provide compile-time type checking and removing risk of
ClassCastException that was common while working with collection classes
Before Generics was introduced : After Generics was introduced :
Type casting leading
List list = new ArrayList(); to List<String> list1 = new ArrayList<String>();
[Link]("abc"); ClassCastException // java 7 ? List<String> list1 = new
at runtime
[Link](new Integer(5)); //OK ArrayList<>();
[Link]("abc");
for(Object obj : list){ [Link](new Integer(5));
String str=(String) obj;
} Compile error – with
Generics errors can
for(String str : list1){
be found at compile //no type casting needed, avoids
time
//ClassCastException
}
Organisation: The Core Collections Interfaces
Collection
Collection Map
Map
Set
Set List
List SortedMap
SortedMap
SortedSet
SortedSet
The Collection Interface
public interface Collection<E>
{
// Basic Operations
Collection: int size();
boolean isEmpty();
an abstract boolean contains(Object o);
supertype of all boolean add(E o);
collections boolean remove(Object o);
Iterator<E> iterator();
// Bulk Operations
boolean containsAll(Collection c);
boolean addAll(Collection <?Extends E>);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
// Array Operations
Object [ ] toArray();
<T> T[ ] toArray(T[]a);
}
Interfaces of the Core Collections
List
single-value elements
ordered (sequence); allows duplicates; indexed access
includes ArrayList & LinkedList
example: help desk schedule
Set
no duplicates; unordered (not stored in the order in which they are
inserted)
includes HashSet & TreeSet
example: students in a class
Map
Key-value map (unique keys); keyed access
includes HashMap & TreeMap
Unordered (not stored in the order in which they are inserted)
example: student-address pairs in a database
The List Interface
public interface List extends Collection
{
// Positional Access
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
boolean addAll(int index, Collection<?Extends E> c);
// Search
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int from, int to);
}
The Set Interface
public interface Set extends Collection
{
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element);
boolean remove(Object o);
Iterator<E> iterator();
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? Extends E> c);
boolean removeAll(Collection<?> c);
boolean retainAll(Collection<?> c);
void clear();
Object[] toArray();
Object[] toArray(Object a[]);
}
The Map Interface (incomplete here…)
public interface Map
{
Object put(K key, V value);
Object get(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
public Set<K> keySet();
public Collection<v> values();
public Set<[Link]><K,V> entrySet();
// Interface for entrySet elements
public interface Entry
{
K getKey();
V getValue();
V setValue(V value);
}
The Basis for All Implementations
• Array-based Structure
• Link-based structure
• Tree (a more complex link-based structure)
• Aim to get a “balanced” tree to minimize access time
• Hashtable (combines links and arrays)
• uses "hash values" to determine position
• very fast lookup
Java Collections Implementations
For each Interface, you can choose from one or more
implementations (classes)
• For List
• ArrayList (constant access time, used most of the time);
• LinkedList (fast insertion)
• For Set
• HashSet (faster; used most of the time);
• TreeSet (sorted)
• For Map
• HashMap (fast);
• TreeMap (sorted)
Java Collections Implementations
implementations
ha sht a bl array tre e lin ke d lis
e t
interfaces
List
List ArrayList
ArrayList LinkedList
LinkedList
Set
Set HashSet
HashSet TreeSet
TreeSet
Map
Map HashMap
HashMap TreeMap
TreeMap
How to Use the Framework (typical steps)
• Choose the interface (the functionality required),
• eg. List
• Choose the implementation (class),
• eg. LinkedList
• Declare an instance of the Collection using the Interface type,
• eg. List<Person> myCollection;
• Create an instance of the Collection using the Implementation
type, and assign that to the Interface instance,
• eg. myCollection = new LinkedList<Person>();
• Start using the collection via its Interface methods,
• eg. [Link](aPerson);
Example : List
• We want a List if the following requirements are to
be satisfied :
• Ordered but unsorted collection
• Ordered – the order in which elements are added is the order
in which they are stored
• Unsorted – no particular sorting of elements, e.g. alphabetical
order
• Ability to add and remove objects easily
• Ability to store duplicate objects
Example cont’d…
• The List Interface features:
• An ordered collection – promises to maintain elements in a
particular sequence
• Provides a list iterator for traversing and maintaining the list
(more about this later)
• Once we have chosen the List interface, we have two
implementations to choose from
ArrayList<E>
LinkedList<E>
Example cont’d…
• ArrayList
• the general purpose container
• Fast random access
• Slow insertion and deletion of elements within the list
• Performance issues
• Resizing - expensive
• Performance can be very slow when there are a large number
of elements.
Example cont’d…
• LinkedList
• more powerful than the arrayList
• Provides optimal sequential access
• Fast insertion and deletion of elements within the list
• Slow for random access
• Methods add extra functionality – can be used as a
stack or a queue
Example cont’d…
• We would choose ArrayList :
• If we want to randomly access elements in constant time
(takes the same amount of time to access the last, middle
or first element)
• We would choose LinkedList :
• If we want to add and remove elements in order and don’t
need random access
Example cont’d…
• Our Code:
public class AClass
{
List <Things> myListCollection; // a List of “Things”
...
public AClass()
{
myListCollection = new ArrayList<Things>(); // use an ArrayList
// or
myListCollection = new LinkedList<Things>(); // use a Linked-List
}
}
Example : Set
• We want a Set if the following requirements are to
be satisfied :
• Unordered collection
• Ability to add and remove objects easily
• Ability to reject duplicate objects
Example cont’d…
• Once we have chosen the Set interface, we have
two implementations to choose from :
• HashSet
• TreeSet
Example cont’d…
• We would choose HashSet :
• If we have many unique elements and access them
frequently
(This is the fastest type of collection)
• We would choose TreeSet :
• If we want to always have elements returned in sorted
order
Example cont’d…
• Our Code:
public class AClass
{
Set<Things> mySetCollection;
...
public AClass()
{
mySetCollection = new HashSet<Things>();
// or
mySetCollection = new TreeSet<Things>();
}
}
Set Example
“New York” actually
only added once to
Set
public class SetExample { Output :
Create new HashSet Set contains : [San Francisco, New York, Paris, Beijing, London]
public static void main(String[] args) {
SAN FRANCISCO
Set<String> set = new HashSet<String>(); NEW YORK Elements of HashSet
PARIS printed in
BEIJING UpperCase
[Link]("London"); LONDON
[Link]("Paris"); Code to add “New Treeset contains : [Beijing, London, New York, Paris, San Francisco]
[Link]("New York"); York” twice to Set
[Link]("San Francisco"); Elements of TreeSet
[Link]("Beijing"); Print out contents of printed in sorted
[Link]("New York"); HashSet aphabetical order
[Link]("Set contains : " + set);
Iterator is created for
Set
Iterator<String> iterator = [Link]();
while ([Link]()){ Loop over Set using
[Link]([Link]().toUpperCase()); iterator converting
all elements to
}
UpperCase and
printing
Set<String> treeSet = new TreeSet<String>(set);
[Link]("Treeset contains : " + treeSet); Create new TreeSet
}
} Print out contents of
TreeSet
Implementations of the Map Interface
• HashMap
• Stores a pair which represents a key and a value associated
with that key
• Examples
• Name and phone number
• Employee id and employee object
• And many more possibilities, eg. the value could be
another collection
• An unordered collection – makes no guarantees about the
order in which the objects will be stored.
• Uses a hashcode created from the key element to provide
very fast access to elements
Implementations of the Map Interface cont’d..
• TreeMap
• Same as the HashMap except that the elements are
guaranteed to be returned for viewing in sorted order.
(Note this does not mean stored in sorted order)
• To have keys stored in sorted order use SortedMap
Example : Map
The following exercise provides an example of storing employee information with an
associated employee ID in a Map. We have an “Employee” class to store employee info
and the main class “MapExercise” in which we use the Map.
public class Employee {
private int CPR;
private String name;
private String address;
private double salary;
public Employee() {
public Employee(int cpr, String name, String address, double salary) {
[Link] = cpr;
[Link] = name;
[Link] = address;
[Link] = salary;
}
//Getters and Setters for above attributes………
Example : Map
Scanner in = new Scanner([Link]); Create new HashMap,
Map<Integer, Employee> employees = new HashMap<Integer, Employee>(); key is the employee ID,
value is the employee object
Employee employee1 = new Employee(19958123, "Ahmed Ali", "Isa Town", 800);
Employee employee2 = new Employee(19973214, "Mohammed Abdulla", "Riffa", 900);
Employee employee3 = new Employee(19925879, "Maryam Hussain", "Juffair", 1000);
//Add employee objects to Map with associated id
[Link](1234, employee1);
[Link](5678, employee2); Add three employee objects to
[Link](9875, employee3); Map with respective ID’s
//Read in and store employee ID
[Link]("Please enter the ID of the employee whose information you wish to display :");
int id = [Link]();
//Print out name and address of particular employee
Use id from user as key for Map
String name = [Link](id).getName();
to retrieve corresponding
String address = [Link](id).getAddress();
employee object, then get name
[Link]("Name : " + name + ", " + "Address : " + address);
and address and print out
//Can extract the set of keys from the Map and store in a separate Set
The keySet() method can be
Set<Integer> ids = [Link]();
used to extract the Set of
[Link]("Use of \"for each\" loop to iterate over Set");
keys from the Map
[Link]("Print the list of employee id's");
for (Integer employeeID : ids){
[Link]("id = " + employeeID); A “for each” loop is used to
} iterate over the Set so that each
ID can be printed out
Example : Map
Continued……… Here we want to print out the names and addresses
of all employees. We need to iterate over the
[Link](""); contents of the Map.
[Link]("Map Contents : ");
//Create iterator for Set of keys Step 1 : Extract set of keys from Map and store in
Iterator<Integer> it = [Link](); Set, “ids” (already completed).
while ([Link]()) {
int ID = [Link](); Step 2 : Create an iterator using the Set “ids”.
[Link]("Name : " + [Link](ID).getName());
[Link]("Address : " + [Link](ID).getAddress()); Step 3 : Use iterator to loop through set of keys. In
} each iteration use current key to access Map
value(employee object) and print name and address.
//Apply salary increase to all employees
[Link]("Please enter salary increase (as decimal between 0 and 1)");
double increase = [Link]();
int count = 0; To apply a salary increase to
all employees we need iterate
Iterator<Integer> it2 = [Link](); over contents of Map – we
while ([Link]()) { use an iterator to do this.
[Link]("count = " + count);
int ID = [Link](); Calculate new salary with
double newSalary = [Link](ID).getSalary() + ([Link](ID).getSalary() * increase); increase and overwrite
[Link](ID).setSalary(newSalary); original salary then print
[Link](" ID = " + ID + ", " + [Link](ID).getSalary()); out employee ID and new
} salary.
Example : Map
Here we want to print out the id, name and address of
Continued........
each employee. We need to iterate over the contents
of the Map. This is an alternate way to do this.
//alternate way to interate through values in a Map
//Print out the contents of the Map
[Link]("Map Contents : (Alternate way)"); Step 1 : Create a Set of Map entries using the
entrySet() method. Each entry in the Set contains a
Set<[Link]<Integer, Employee>> entrySet = [Link](); key and a value.
for ([Link]<Integer, Employee> entry: entrySet){
[Link]([Link]() + ", Name : " + [Link]().getName() + ", Address : " + [Link]().getAddress());
}
Step 2 : Use a “for each” loop to iterate over each
item in the Set “entrySet”. Use the getKey() and
getValue() methods to access the key and value of
each item respectively.
Practical
• Complete exercise 2
Appendix
Example : Map
• Adding elements:
put(K key,V value)
Map<String,Integer> map1 =
new HashMap<String,Integer>();
Map<String,Integer> map2 =
new TreeMap<String,Integer>();
. . .
for (String s: names)
{ [Link](s, number1);
[Link](s, number1);
}
Example : Map cont’d…
• Getting a value
• Value get(Object key)
• Returns the value specified by the key
Integer iD = [Link]("Joe");
[Link]("Joe's student id is “
+ [Link]());
Example : Map cont’d…
• Getting keySet() of the Map returns a Set of keys.
• Getting the values of the Map returns a collection
(set or list) of the Map entries
• We can now use these in the same way as we can
use Collections
Set<String> myKeySet = new HashSet<String>();
Collection<String> myValues = new HashSet<String>();
myKeySet = [Link]();
myValues = [Link]();