The Collection interface – basic operations

Technology: Core Java

Concepts - Day 2

Copyright © 2013 TATA Consultancy Services Limited TCS CONFIDENTIAL

1
 COLLECTION

A collections(container) is simply an object that groups

multiple elements into a single unit.
Used to store, retrieve, manipulate, and communicate
aggregate data.
Collection framework is a unified architecture for
representing and manipulating collections.
All collection frameworks contain the following:
Interfaces
Implementations
Algorithms
The main difference between Collection and Collections is that Collection is the root
interface of Java Collections Framework while Collections is a utility class
which is a member of the Java Collections Framework.

2
COLLECTION HIERARCHY

3
TCS CONFIDENTIAL
Collection : Root interface with basic methods like add(), remove(),
contains(), isEmpty(), addAll(), ... etc.

Set : Doesn't allow duplicates. Example implementations of Set

interface are HashSet (Hashing based) and TreeSet (balanced
BST based). Note that TreeSet implements SortedSet.

List : Can contain duplicates and elements are ordered. Example

implementations are LinkedList (linked list based) and
ArrayList (dynamic array based)

Queue : Typically order elements in FIFO order .

Deque : Elements can be inserted and removed at both ends. Allows

both LIFO and FIFO.

Map : Contains Key value pairs. Doesn't allow duplicates. Example

implementation are HashMap and TreeMap.
TreeMap implements SortedMap.

The difference between Set and Map interface is that in Set we

have only keys, whereas in Map, we have key, value pairs.

4
5
6
7
 General-purpose Implementations

Interfaces Implementations

Hash table Resizable array Tree Linked list Hash table + Linked list
(sorted)

TreeSet
Set HashSet (sorted) LinkedHashSet

LinkedList
List ArrayList

Queue

TreeMap
Map HashMap (sorted) LinkedHashMap

Note the naming convention

LinkedList also implements queue and there is a PriorityQueue implementation (implemented with heap)
8
The Collection interface – basic operations
• Basic operations in collection interface:
–int size(): returns the number of elements in the collection
–boolean isEmpty(): checks if a collection is empty
–boolean contains(Object element): checks whether a given
object is present in the collection
–boolean add(Object element): adds given element to the
collection.
–boolean remove(Object element): removes an element from the
collection
–Iterator<E> iterator: provides an iterator over the collection

9
The Collection interface – bulk operations
• containsAll — returns true if the target Collection contains all of
the elements in the specified Collection.
• addAll — adds all of the elements in the specified Collection to the
target Collection.
• removeAll — removes from the target Collection all of its elements
that are also contained in the specified Collection.
• retainAll — removes from the target Collection all its elements that
are not also contained in the specified Collection. That is, it retains
only those elements in the target Collection that are also
contained in the specified Collection.
• clear — removes all elements from the Collection.

10
The Collection interface – traversing collections
•for-each Construct
Allows to traverse through a collection.
for(Object o: collection)
{
//code
}
•Iterators
An iterator is an object that enables t traverse through a collection
and to remove elements from the collection selectively, if required.
– Iterator interface has following methods
• boolean hasNext(): returns true if the iteration has more
elements
• Object next(): returns the next element in the iteration
• void remove(): removes the last element that was returned by
call of next() on the collection. The remove method can be
called only once per call to next(). 11
 LIST

A list is a ordered collection of objects.

Users have control on where new element in the list should be
added.
List can contain duplicated element.
It is growable array.
It gives us fast iteration and fast random access.

12
TCS CONFIDENTIAL
 public interface List<E>
extends Collection<E>

To instantiate the List interface, we must use :

List <data-type> list1= new ArrayList();
List <data-type> list2 = new LinkedList();

13
public interface List<E>
extends Collection<E>
public interface List<E> extends Collection<E> {
// Positional access
E get(int index);
E set(int index, E element); //optional
boolean add(E element); //optional
void add(int index, E element); //optional
E remove(int index); //optional
boolean addAll(int index,
Collection<? extends E> c); //optional

// Search
int indexOf(Object o);
int lastIndexOf(Object o);

// Iteration
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);

// Range-view
List<E> subList(int from, int to);
}

14
 ARRAYLIST

Java ArrayList class uses a dynamic array for storing

the
elements. It inherits AbstractList class and implements
List interface.
⚫ can contain duplicate elements.
⚫ Null insertion is possible
⚫ maintains insertion order.
⚫ Hetrogenous objects are allowed

15
TCS CONFIDENTIAL
 METHODS OF ARRAYLIST
import java.util.ArrayList;
public class MyBasicArrayList {
public static void main(String[] a){
ArrayList<String> al = new ArrayList<String>();
//add elements to the ArrayList
al.add("JAVA");
al.add("C++");
al.add("PERL");
al.add("PHP");
System.out.println(al);
//get elements by index
System.out.println("Element at index 1: "+al.get(1));
System.out.println("Does list contains JAVA?
"+al.contains("JAVA"));
16
TCS CONFIDENTIAL
 METHODS OF ARRAYLIST
//add elements at a specific index
al.add(2,"PLAY");
System.out.println(al);
System.out.println("Is arraylist empty? "+al.isEmpty());
System.out.println("Index of PERL is "+al.indexOf("PERL"));
System.out.println("Size of the arraylist is: "+al.size());
}}
OUTPUT:
[JAVA, C++, PERL, PHP]
Element at index 1: C++
Does list contains JAVA? true
[JAVA, C++, PLAY, PERL, PHP]
Is arraylist empty? false
Index of PERL is 3
Size of the arraylist is: 5
17
TCS CONFIDENTIAL
A sample code using ArrayList
import java.util.*;
class Company
{
ArrayList<Employee> employeeRegister = new ArrayList<Employee>();

public void addEmployee(Employee anEmployee)

{employeeRegister.add(anEmployee);}

public void modifyEmployeeName(String empNo, String newName)

{
for(Employee anEmployee : employeeRegister)
if(empNo.equals(anEmployee.getEmpNo()))
anEmployee.setName(newName);
}
}

class Employee
{ Company techSmart = new Company()
private String empNo; Employee emp1 = new Employee("121","Bob")
private String name;
Employee emp2 = new Employee("232","Linda")
Employee(String empNo, String name)
techSmart.addEmployee(emp1)
{ techSmart.addEmployee(emp2)
this.name = name; techSmart.modifyEmployeeName("121","Bob Jr.")
this.empNo = empNo; emp1.name
} "Bob Jr."
public String getEmpNo()
{return empNo;}

public String getName()

{return name;}

public void setName(String name)

{this.name = name;} 18
}
import java.util.*;
class ArrayList2{
public static void main(String args[]){
ArrayList<String> list=new ArrayList<String>();//Creating arraylist
list.add("Ravi");//Adding object in arraylist
list.add("Vijay");
list.add("Ravi");
list.add("Ajay");
//Traversing list through Iterator
Iterator itr=list.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
}

19
Link list

20
 LinkedList class

Java LinkedList class uses a doubly linked list to store the elements. It provides a
linked-list data structure. It inherits the AbstractList class and implements List and
Deque interfaces.

⚫ can contain duplicate elements.

⚫ Null insertion is possible
⚫ maintains insertion order.
⚫ is non synchronized.
⚫ Hetrogenous objects are allowed
⚫ manipulation is fast because no shifting needs to occur.
⚫ Best for frequent insertion and deletion in middle

21
public interface Set<E>
extends Collection<E>

Set — a collection that cannot contain duplicate elements. This

interface models the mathematical set abstraction and is used to
represent sets, such as the cards comprising a poker hand, the
courses making up a student's schedule, or the processes
running on a machine.
Set<data-type> s1 = new HashSet<data-type>();
Set<data-type> s2 = new LinkedHashSet<data-type>();
Set<data-type> s3 = new TreeSet<data-type>();

22
public interface Set<E>
extends Collection<E>

public interface Set<E> extends Collection<E> {

// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional
boolean remove(Object element); //optional
Iterator<E> iterator();

// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional
boolean removeAll(Collection<?> c); //optional
boolean retainAll(Collection<?> c); //optional
void clear(); //optional

// Array Operations
Object[] toArray();
<T> T[] toArray(T[] a);
}

Note: nothing added to Collection interface – except no duplicates allowed 23

 HashSet

import java.util.*;
class HashSet2{
public static void main(String args[]){
//Creating HashSet and adding elements
HashSet<String> set=new HashSet<String>();
set.add("Ravi");
set.add("Vijay");
set.add("Ravi");
set.add("Ajay");
//Traversing elements
Iterator<String> itr=set.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
}

24
 Java HashSet

Java HashSet class is used to create a collection that uses a hash table for storage. It
inherits the AbstractSet class and implements Set interface.

⚫ contains unique elements only.

⚫ allows null value.
⚫ doesn't maintain the insertion order. Here, elements are inserted on the basis of their
hashcode.
⚫ is the best approach for search operations.
⚫ Heterogenous allowed
⚫ Best for searching due to hashcode alogorithm

25
 LinkedHashSet

It inherits HashSet class and implements Set interface.

The important points about Java LinkedHashSet class are:

Java LinkedHashSet class contains unique elements only like HashSet.

Java LinkedHashSet class provides all optional set operation and permits null
elements.
Java LinkedHashSet class is non synchronized.
Java LinkedHashSet class maintains insertion order.

26
 TreeSet class

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits
AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet
class are stored in ascending order.

The important points about Java TreeSet class are:

Java TreeSet class contains unique elements only like HashSet.

Java TreeSet class access and retrieval times are quiet fast.
Java TreeSet class doesn't allow null element.
Java TreeSet class is non synchronized.
Java TreeSet class maintains ascending order.

27
public interface Map<K,V>

Map — an object that maps keys to values. A Map cannot

contain duplicate keys; each key can map to at most one value.

28
public interface Map<K,V>
public interface Map<K,V> {

// Basic operations
V put(K key, V value);
V get(Object key);
V remove(Object key);
boolean containsKey(Object key);
boolean containsValue(Object value);
int size();
boolean isEmpty();

// Bulk operations
void putAll(Map<? extends K, ? extends V> m);
void clear();

// Collection Views
public Set<K> keySet();
public Collection<V> values();
public Set<Map.Entry<K,V>> entrySet();

// Interface for entrySet elements

public interface Entry {
K getKey();
V getValue();
V setValue(V value);
} 29
}
 Java Hashtable class

Java Hashtable class implements a hashtable, which maps keys to values. It inherits
Dictionary class and implements the Map interface.

⚫ A Hashtable is an array of a list. Each list is known as a bucket. The position of the
bucket is identified by calling the hashcode() method. A Hashtable contains values
based on the key.
⚫ contains unique elements.
⚫ doesn't allow null key or value.
⚫ is synchronized and is legacy
import java.util.*;
class Hashtable1{
public static void main(String args[]){
Hashtable<Integer,String> hm=new Hashtable<Integer,String>();

hm.put(100,"Amit");
hm.put(102,"Ravi");
hm.put(101,"Vijay");
hm.put(103,"Rahul");

for(Map.Entry m:hm.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
} 30
}
 Java HashMap class

Java HashMap class implements the map interface by using a hash table. It
inherits AbstractMap class and implements Map interface.

⚫ contains values based on the key.

⚫ contains only unique keys.
⚫ allows null key or value.
⚫ is non synchronized.
⚫ maintains no order.

31
 Java HashMap class

import java.util.*;
class HashMap1{
public static void main(String args[]){
HashMap<Integer,String> hm=new HashMap<Integer,String>();
System.out.println("Initial list of elements: "+hm);
hm.put(100,"Amit");
hm.put(101,"Vijay");
hm.put(102,"Rahul");

System.out.println("After invoking put() method ");

for(Map.Entry m:hm.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}

hm.putIfAbsent(103, "Gaurav");
System.out.println("After invoking putIfAbsent() method ");
for(Map.Entry m:hm.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
HashMap<Integer,String> map=new HashMap<Integer,String>();
map.put(104,"Ravi");
map.putAll(hm);
System.out.println("After invoking putAll() method ");
for(Map.Entry m:map.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
}
} 32
 Java TreeMap class

Java TreeMap class is a tree based implementation. It provides an efficient means

of storing key-value pairs in sorted order.

The important points about Java TreeMap class are:

Java TreeMap contains values based on the key. It implements the NavigableMap
interface and extends AbstractMap class.
⚫ Java TreeMap contains only unique elements.

⚫ Java TreeMap cannot have a null key but can have multiple null values.

⚫ Java TreeMap is non synchronized.

⚫ Java TreeMap maintains ascending order.

33
Note on Comparator interface

Comparator is another interface (in addition to Comparable)

provided by the Java API which can be used to order objects.
You can use this interface to define an order that is different from
the Comparable (natural) order.

34
 Comparable interface
import java.util.*;
import java.io.*;
class Student implements Comparable<Student>{
int rollno;
String name;
int age;
Student(int rollno,String name,int age){
this.rollno=rollno;
this.name=name;
this.age=age;
}
public int compareTo(Student st){
if(age==st.age)
return 0;
else if(age>st.age)
return 1;
else
return -1;
}
}
//Creating a test class to sort the elements
public class TestSort3{
public static void main(String args[]){
ArrayList<Student> al=new ArrayList<Student>();
al.add(new Student(101,"Vijay",23));
al.add(new Student(106,"Ajay",27));
al.add(new Student(105,"Jai",21));

Collections.sort(al);
for(Student st:al){
35
System.out.println(st.rollno+" "+st.name+" "+st.age);
 Comparator
Student.java
class Student{
int rollno;
String name;
int age;
Student(int rollno,String name,int age){
this.rollno=rollno;
this.name=name;
this.age=age;
}
}
AgeComparator.java
import java.util.*;
class AgeComparator implements
Comparator<Student>{
public int compare(Student s1,Student s2){
if(s1.age==s2.age)
return 0;
else if(s1.age>s2.age)
return 1;
else
return -1;
} 36
import java.util.*;
class NameComparator implements Comparator<Student>{
public int compare(Student s1,Student s2){
return s1.name.compareTo(s2.name);
}
}

37
//Java Program to demonstrate the use of Java Comparator
import java.util.*;
import java.io.*;
class TestComparator{
public static void main(String args[]){
//Creating a list of students
ArrayList<Student> al=new ArrayList<Student>();
al.add(new Student(101,"Vijay",23)); Sorting by Name
al.add(new Student(106,"Ajay",27)); 106 Ajay 27
al.add(new Student(105,"Jai",21));
105 Jai 21
System.out.println("Sorting by Name"); 101 Vijay 23
//Using NameComparator to sort the elements
Collections.sort(al,new NameComparator());
//Traversing the elements of list Sorting by Age
for(Student st: al){ 105 Jai 21
System.out.println(st.rollno+" "+st.name+" "+st.age);
}
101 Vijay 23
106 Ajay 27
System.out.println("sorting by Age");
//Using AgeComparator to sort the elements
Collections.sort(al,new AgeComparator());
//Travering the list again
for(Student st: al){
System.out.println(st.rollno+" "+st.name+" "+st.age);
} 38
39
40
 Summary

Collections framework makes data processing and

manipulation easier.

ArrayList supports dynamic arrays that can grow as

needed.

Set is a Collection of dissimilar elements where duplicates

are not allowed.

Lists,Sets and Maps differ based on the use of duplicate

values and null values.

41
QUE – 1: ArrayList
ASSIGNMENT
Create a class Book with below attributes:
int - id
String - title
double - price
int - pages
String - author
Make all the attributes private. Create corresponding getters
and setters.
Create a constructor which takes all parameters in the above
sequence. The constructor should set the value of attributes to
parameter values inside the constructor.
Create a class BookDemo with main method

42
 ASSIGNMENT

Create the below static method searchBookById in the

BookDemo class.

searchBookById(ArrayList<Book> objList)

This method will take Array List of Book objects and id as

input and returns the position of the id if found or -1 if not
found.

Create an Array List of 5 Book objects in the main method

Call the above static method from the main method

43
 EXTRA ASSIGNMENTS
TOPIC: Map

Create a static Map object of type <int,Book> in the

BookDemo class with id as the key and Book object as the
value.

Create a method addBook in the BookDemo class which will

take Book object as the input parameter

The method adds the id of the input object as the key to

the map and the input object as the value for the same.

Create a method displayBookMap in the BookDemo class.

The method displays all the elements in the map with the
key and value.
Call the above methods from the main method
44
 Thank You

Copyright © 2013 TATA Consultancy Services Limited

45
TCS CONFIDENTIAL