COLLECTIONS

(An easy way to manage

Objects)
The “LinkedList” class
• LinkedList implements the List interface.

• It Uses Doubly Linked List internally.

• No initial capacity

• Capacity/size increases as elements are added

• Insertion order is preserved

• Good choice when frequent operations are adding and

removing and worst when frequent operation is retrieval
Internal Mechanism Of LinkedList
• A LinkedList is an organized collection of elements called
as nodes where each node contains an item ,a reference
to the next element and a reference to the previous
element
Adding Elements In The LinkedList
LinkedList <String>cities = new LinkedList<String>();
cities.add(“Bhopal”);
cities.add(“Paris”);
cities.add(“Delhi”);

The above code will create three nodes having “Bhopal” ,

“Paris” and “Delhi” as their contents and references of
three nodes adjusted to point to previous and next nodes
“Bhopal” ”Paris” ”Delhi”
Adding Elements In The LinkedList
Now suppose we want to add “New York” at position 3
then we would write

cities.add(2,”New York”);

To make this adjustment , three steps will be done:

a. Creating a new node with “New York”
b. Breaking links of “Paris” and “Delhi”
c. Adjust links of “Paris””NewYork” as well as
“NewYorkDelhi”
“Bhopal” ”Paris” ”NewYork” ”Delhi”
Getting Element From The LinkedList
•To get a particular element from LinkedList we use the
same method called get( ) passing it the index no .

•Example
System.out.println(cities.get(1));// Paris
Getting Element From The LinkedList
•Although LinkedList provides us a get( ) method , but
when we use it to access a particular element then it
internally traverses the complete list upto the element
required .

•On the other hand if we use ArrayList then directly the

element is accessed based on index no.

•Thus ArrayList supports Random Access , while

Linked List supports Sequential Access
Summary Of Benefits
1. Maintains the insertion order of elements

2. Efficient for adding and removing elements from the

middle of the list

3. Good for sequential access , but not for random access

The Set Interface
1. The Set interface extends Collection interface

2. A Set is a collection that cannot contain duplicate

elements.

3. A Set is NOT an ordered collection

4. Unlike List and arrays, Set does NOT support indexes

or positions of it’s elements.
Implementation Classes Of Set
There are 2 implementation classes of Set interface:
1- HashSet
2- TreeSet

The HashSet represents a set backed by a hash table

providing constant lookup−time access to unordered
elements.

The TreeSet maintains its elements in a sorted order within

a BST
The HashSet Class
1.This class implements the Set interface

2.It internally uses a hash table for storage and applies a

mechanism called hashing for storage and retrieval of data

3.It makes no guarantee as to the iteration order of the

set
Inserting Elements In HashSet
• To insert an element in the HashSet , we have to call the
method add( )

• This method has following prototype:

• Prototype:

• public boolean add(Object)

Inserting Elements In HashSet
• It accepts an Object as argument and adds that Object in
the HashSet . If adding is successful it returns true
otherwise it returns false.
• For Ex:

HashSet<String> HSet = new HashSet<String>();

HSet.add("C");
HSet.add("A");
HSet.add("B");
Exercise 5
• WAP to store names of first four months in the HashSet
and them print them .
What is an Iterator ?
1.The List and Set collections provide iterators, which are
like pointers that allow going over all the elements of a
collection in sequence

2.To access a collection through an iterator, we have to

obtain the object of type Iterator which is done by calling
the method called iterator( ) , available in all Collection
classes
What is an Iterator ?
3. The prototype of this method is:

public Iterator iterator( )

4.By using this Iterator object, we can access each

element in the collection, one element at a time
Methods Of Iterator
1. public boolean hasNext( ) : Checks whether there is
an element present in the Collection to be accessed . If
an element is present it returns true otherwise it returns
false

2. public Object next( ) : Moves the internal pointer to the

next position and returns the element present there. If
no element is present then it throws
NoSuchElementException
Working Of Iterator
Suppose we write the statement:
Iterator it = hs.iterator();

When the above statement runs , the internal pointer of

the Iterator called Cursor starts pointing to the position
which is before first element of the Collection.
Working Of Iterator
Now , when we write the following code:
it.hasNext();
it.next();
the Cursor starts pointing to the FIRST element in the
Collection
Working Of Iterator
If we again write the following code:
it.hasNext();
it.next();
the Cursor starts pointing to the SECOND element in the
Collection
Working Of Iterator
Repeating this process finally sends the Cursor to the
LAST element of the Collection

After reading the final element, if we run code

it.hasNext()
then it returns “false” value.
Steps To Use Iterator
In general, to use an iterator to cycle through the contents
of a collection, follow these steps:

1. Obtain an iterator to the start of the collection by calling

the collection's iterator( )

2. Set up a loop that makes a call to hasNext( ). Have the

loop iterate as long as hasNext( ) returns true.

3. Within the loop, obtain each element by calling next( ).

Example
HashSet <String> hs=new HashSet<String>();
hs.add("January");
hs.add("February");
hs.add("March");
hs.add("April");
Iterator it=hs.iterator();
while(it.hasNext())
{
String s=(String)it.next();
System.out.println(s);
}
Exercise 6
Modify the ArrayList program and traverse the ArrayList
using iterator
A Very Important Point !
import java.util.*;
public class HashsetDemo {
public static void main(String[] args) {
HashSet <String> hs=new HashSet<String>();
hs.add("Amit");
hs.add("Sumit");
hs.add("Amit");
System.out.println(hs);

}
}
Output:
[Amit, Sumit]
 Now Again Guess The Output ?
class Student class HashSetDemo{
{ public static void main(String[] args) {
HashSet <Student> hs;
private String name;
hs=new HashSet<Student>();
public Student(String name) Student s1=new Student("Amit");
{ Student s2=new Student("Sumit");
this.name=name; Student s3=new Student("Amit");
hs.add(s1);
}
hs.add(s2);
hs.add(s3);
public String toString() System.out.println(hs);
{ }
return name; }
Output:
}
[Amit , Sumit , Amit]

}
Why Duplicates Were Not Removed ?
• This is because when we add a new object to HashSet , then java
searches it in the hash table using it’s hash code .

• And if no object is found with the matching hash code then it

inserts the new object in the HashSet

• Now this raises a question “ what is a hash code ?”

• The hash code of a Java object is simply an integer allotted by

the JVM to uniquely identify an object.

• To get the hash code of an object we can call the method

hashCode( ) which is inherited by every class from the class
Object
Why Duplicates Were Not Removed ?
• But with respect to Collections , hash code should not be
unique for every object.

• As per Collections , if two objects are equals then these

two objects should return same hash code.

• So we have to override hashcode() method of a class in

such way that if two objects are equal, then those two
objects must return same hash code
Why Duplicates Were Not Removed ?
• But , since we have not overridden hashCode( ) method
in our Student class so we got two student objects having
the same name.
What Other Method We Should Override With
hashCode( )?
• We should also override equals( ) alongwith hashCode( )
because the HashSet also calls equals( ) along-with
hashCode( ) to match the actual value.

• This is called hashcode-equals contract in java

Exercise 7
Write a program to implement a Library Management
System with the following features:

1. It should contains Books where each Book has a

name , an author and price.

2. All the books must be unique i.e. it should not accept a

Book if it is already present

3. Retrieval of Book should be as fast as possible

Exercise 7
The program should have 3 classes:
1. Book : should contain 3 data members called name ,
author and price . Also provide appropriate constructor
and other important methods

2. Library: should contain a HashSet of Book . Also

provide 3 methods called addBook( ), getBookCount()
and getAllBooks( )

3. UseLibrary: This will be our driver class . It will contain

code to create 4 Book objects , add them to the Library
and display their details.