The Collection interface – basic operations

Technology: Core Java

Concepts

Copyright © 2013 TATA Consultancy Services Limited TCS

CONFIDENTIAL1
 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(Set,List,Queue,Map)
Implementations(Hashset,Linked
hashset,Treeset,ArrayList,linkedset,vector,Priority
Queue,Dequeue,hashmap,Treemp,Linkedhash map)
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.
5
COLLECTION HIERARCHY

6
TCS
The Collection interface – basic operations
• Basic operations in collection interface:
add(object): this method used to add an object to
collection.
int size(): returns the number of elements in the
collection
equals(Object o): compares the specified object with
this collection for equality
• boolean isEmpty(): checks if a collection is empty
• boolean contains(Object element): checks
whether a given object is present in the collection

• boolean remove(Object element): removes an

element from the collection
• Iterator<E> iterator: provides an iterator over the
collection
7
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.

8
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.

9
 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

TreeMa
p
Map HashMap (sorted LinkedHashMap
)

Note the naming convention

LinkedList also implements queue and there is a PriorityQueue implementation (implemented with heap)
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 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 11
remove method can be called only once per call to
 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.

Since List is an Interface, we cannot create objects from it.

In order to use functionalities of List interface, we can use
these classes: ArrayList, LinkedList,Vector,Stack.

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


Use java.util.list package to implement list

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

It maintains insertion order.

Hetrogenous objects are allowed(diff objects from diff
class)

15
TCS
 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
 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] 17
Is arraylist empty? false TCS
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
{
private String empNo; Company techSmart = new Company()
private String name; Employee emp1 = new Employee("121","Bob")
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
 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

20
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>();

21
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 22

 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

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
 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.

25
 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.

26
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.

27
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);
}
} 28
 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());
}
} 29
}
 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.

30
 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());
}
}
} 31
 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.

32
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.

33
 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){
34
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;
} 35
import java.util.*;
class NameComparator implements Comparator<Student>{
public int compare(Student s1,Student s2){
return s1.name.compareTo(s2.name);
}
}

36
//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);
} 37
38
 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.

39
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

40
 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

41
 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
42
 Thank You

Copyright © 2013 TATA Consultancy Services Limited

43
TCS