Java Collection fundamentals and Uses Unit

Java Collection

1. 1
Java Collections

2. 2
Java 2 Collections
•A collection is an object that groups multiple
elements into a single unit
•Very useful
»store, retrieve and manipulate data
»transmit data from one method to another
•Java Collections can achieve all the operations that you
perform on a data such as searching, sorting, insertion,
manipulation, and deletion.

3. 3-February-2003 3
Collections Framework
•Unified architecture for representing and
manipulating collections.
•A collections framework contains three things
»Interfaces
»Implementations
»Algorithms

4. 3-February-2003 4
Collections Framework Diagram
•Interfaces, Implementations, and Algorithms
•From Thinking in Java, page 462

5. 3-February-2003 5
Collection Interface
•Defines fundamental methods
»int size();
»boolean isEmpty();
»boolean contains(Object element);
»boolean add(Object element); // Optional
»boolean remove(Object element); // Optional
»Iterator iterator();
•These methods are enough to define the basic
behavior of a collection
•Provides an Iterator to step through the elements in
the Collection

6. 3-February-2003 6
Iterator Interface
•Defines three fundamental methods
»Object next()
»boolean hasNext()
»void remove()
•These three methods provide access to the
contents of the collection
•An Iterator knows position within collection
•Each call to next() “reads” an element from the
collection
»Then you can use it or remove it

7. 3-February-2003 7
Iterator Position

8. 3-February-2003 8
Example - SimpleCollection
public class SimpleCollection {
public static void main(String[] args) {
Collection c;
c = new ArrayList();
System.out.println(c.getClass().getName());
for (int i=1; i <= 10; i++) {
c.add(i + " * " + i + " = "+i*i);
}
Iterator iter = c.iterator();
while (iter.hasNext())
System.out.println(iter.next());
}
}

9. List Interface
3-February-2003 9

10. List Interface
3-February-2003 10

11. 3-February-2003 11
List Interface Context
Collection
List

12. 3-February-2003 12
List Interface
•The List interface adds the notion of order to a
collection
•The user of a list has control over where an element is
added in the collection
•Lists typically allow duplicate elements
•Provides a ListIterator to step through the elements in
the list.

13. 3-February-2003 13
ListIterator Interface
•Extends the Iterator interface
•Defines three fundamental methods
»void add(Object o) - before current position
»boolean hasPrevious()
»Object previous()
•The addition of these three methods defines the basic
behavior of an ordered list
•A ListIterator knows position within list

14. 3-February-2003 14
Iterator Position - next(), previous()

15. 3-February-2003 15
ArrayList and LinkedList Context
ArrayListLinkedList
Collection
List

16. 3-February-2003 16
List Implementations
•ArrayList
»low cost random access
»high cost insert and delete
»array that resizes if need be
•LinkedList
»sequential access
»low cost insert and delete
»high cost random access

17. 3-February-2003 17
ArrayList overview
•Constant time positional access (it’s an array)
•One tuning parameter, the initial capacity
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException(
"Illegal Capacity: "+initialCapacity);
this.elementData = new Object[initialCapacity];
}

18. 3-February-2003 18
ArrayList methods
•The indexed get and set methods of the List interface are
appropriate to use since ArrayLists are backed by an array
»Object get(int index)
»Object set(int index, Object element)
•Indexed add and remove are provided, but can be costly if
used frequently
»void add(int index, Object element)
»Object remove(int index)
•May want to resize in one shot if adding many elements
»void ensureCapacity(int minCapacity)

19. 3-February-2003 19
LinkedList overview
•Stores each element in a node
•Each node stores a link to the next and previous
nodes
•Insertion and removal are inexpensive
»just update the links in the surrounding nodes
•Linear traversal is inexpensive
•Random access is expensive
»Start from beginning or end and traverse each node while
counting
•Java LinkedList class uses a doubly linked list to store the
elements.

20. 3-February-2003 20
LinkedList entries
private static class Entry {
Object element;
Entry next;
Entry previous;
Entry(Object element, Entry next, Entry previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
private Entry header = new Entry(null, null, null);
public LinkedList() {
header.next = header.previous = header;
}

21. 3-February-2003 21
LinkedList methods
•The list is sequential, so access it that way
»ListIterator listIterator()
•ListIterator knows about position
»use add() from ListIterator to add at a position
»use remove() from ListIterator to remove at a position
•LinkedList knows a few things too
»void addFirst(Object o), void addLast(Object o)
»Object getFirst(), Object getLast()
»Object removeFirst(), Object removeLast()

22. Difference Between ArrayList and LinkedList
3-February-2003 22
ArrayList LinkedList
1) ArrayList internally uses
a
 
dynamic array 
to store the
elements.
LinkedList internally uses a
 
doubly
linked list 
to store the elements.
2) Manipulation with ArrayList
is
 
slow 
because it internally uses an
array. If any element is removed from
the array, all the other elements are
shifted in memory.
Manipulation with LinkedList
is
 
faster 
than ArrayList because it
uses a doubly linked list, so no bit
shifting is required in memory.
3) An ArrayList class can
 
act as a
list 
only because it implements List
only.
LinkedList class can
 
act as a list and
queue 
both because it implements
List and Deque interfaces.
4) ArrayList is
 
better for storing and
accessing 
data.
LinkedList is
 
better for
manipulating 
data.

23. Difference Between ArrayList and LinkedList
3-February-2003 23
ArrayList LinkedList
5) The memory location for the
elements of an ArrayList is
contiguous.
The location for the elements of a
linked list is not contagious.
6) Generally, when an ArrayList is
initialized, a default capacity of 10 is
assigned to the ArrayList.
There is no case of default capacity in
a LinkedList. In LinkedList, an empty
list is created when a LinkedList is
initialized.
7) To be precise, an ArrayList is a
resizable array.
LinkedList implements the doubly
linked list of the list interface.

24. Vector
•The Vector class is designed to function as a dynamic array
that can expand or shrink according to the application’s needs.
•We can access the objects of the Vector using the indices.
•It maintains the insertion order and stores duplicate elements.
• It is found in the java.util package and implements the List
interface
•There are four different types of Vector constructors.
Vector<T> vector = new Vector<T>();
Vector<T> vector = new Vector<T>(int size);
Vector<T> vector = new Vector<T>(int size, int capacityIncrement);
Vector<T> vector = new Vector(Collection<T> collection);
3-February-2003 24

25. ArrayList Vs Vector
3-February-2003 25
ArrayList Vector
1) ArrayList is
 
not synchronized. Vector is
 
synchronized.
2) ArrayList
 
increments 50% 
of current
array size if the number of elements
exceeds from its capacity.
Vector
 
increments 100% 
means doubles
the array size if the total number of
elements exceeds than its capacity.
3) ArrayList is
 
not a legacy 
class. It is
introduced in JDK 1.2.
Vector is a
 
legacy 
class.
4) ArrayList is
 
fast 
because it is non-
synchronized.
Vector is
 
slow 
because it is
synchronized, i.e., in a multithreading
environment, it holds the other threads in
runnable or non-runnable state until
current thread releases the lock of the
object.
5) ArrayList uses the
 
Iterator 
interface
to traverse the elements.
A Vector can use the
 
Iterator 
interface
or
 
Enumeration 
interface to traverse the
elements.

26. Stack
•The
 
stack 
is a linear data structure that is used to store the
collection of objects.
•It is based on
 
Last-In-First-Out 
(LIFO).
•Java collection 
framework provides many interfaces and
classes to store the collection of objects.
•Stack is a class that falls under the Collection framework that
extends the Vector class.
•Stack class 
that provides different operations such as push,
pop, search, etc.
3-February-2003 26

27. Set Interface
3-February-2003 27
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.

28. Set Interface
3-February-2003 28

29. 3-February-2003 29
Set Interface Context
Collection
Set

30. 3-February-2003 30
Set Interface
•Same methods as Collection
»different contract - no duplicate entries
•Defines two fundamental methods
»boolean add(Object o) - reject duplicates
»Iterator iterator()
•Provides an Iterator to step through the elements
in the Set
»No guaranteed order in the basic Set interface
»There is a SortedSet interface that extends Set

31. Set Hierarchy
3-February-2003 31

32. 3-February-2003 32
HashSet and TreeSet Context
HashSetTreeSet
Collection
Set

33. 3-February-2003 33
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.
•Find and add elements very quickly
»uses hashing implementation in HashMap
•Hashing uses an array of linked lists
»The hashCode() is used to index into the array
»Then equals() is used to determine if element is in the (short) list
of elements at that index
•No order imposed on elements
•The hashCode() method and the equals() method must be compatible
»if two objects are equal, they must have the same hashCode()
value

34. LinkedHashSet
•Java LinkedHashSet class is a Hashtable and Linked list
implementation of the Set interface. It inherits the HashSet
class and implements the Set interface.
The important points about the Java LinkedHashSet class are:
•Java LinkedHashSet class contains unique elements only like
HashSet.
•Java LinkedHashSet class provides all optional set operations
and permits null elements.
•Java LinkedHashSet class is non-synchronized.
•Java LinkedHashSet class maintains insertion order.
3-February-2003 34

35. 3-February-2003 35
TreeSet
•Elements can be inserted in any order
•The TreeSet stores them in order
»Red-Black Trees out of Cormen-Leiserson-Rivest
•An iterator always presents them in order
•Java TreeMap is non synchronized.
•Default order is defined by natural order
»objects implement the Comparable interface
»TreeSet uses compareTo(Object o) to sort
•Can use a different Comparator
»provide Comparator to the TreeSet constructor

36. 3-February-2003 36
Map Interface Context
Map

37. 3-February-2003 37
Map Interface
•Stores key/value pairs
•Maps from the key to the value
•Keys are unique
»a single key only appears once in the Map
»a key can map to only one value
•Values do not have to be unique

38. 3-February-2003 38
Map methods
Object put(Object key, Object value)
Object get(Object key)
Object remove(Object key)
boolean containsKey(Object key)
boolean containsValue(Object value)
int size()
boolean isEmpty()

39. 3-February-2003 39
Map views
•A means of iterating over the keys and values in a Map
•Set keySet()
»returns the Set of keys contained in the Map
•Collection values()
»returns the Collection of values contained in the Map.
This Collection is not a Set, as multiple keys can map
to the same value.
•Set entrySet()
»returns the Set of key-value pairs contained in the Map.
The Map interface provides a small nested interface
called Map.Entry that is the type of the elements in this
Set.

40. 3-February-2003 40
HashMap and TreeMap Context
HashMapTreeMap
Map

41. HashMap Vs. HashSet
3-February-2003 41
HashMap HashSet
Java HashMap is a hash table
based implementation of Map
interface.
HashSet is a Set. It creates a
collection that uses a hash table
for storage.
HashMap implements
 
Map,
Cloneable, and
Serializable 
interface es.
HashSet implements
 
Set,
Cloneable, Serializable,
Iterable 
and 
Collection 
interfaces
.
In HashMap we store a
 
key-value
pair. It maintains the mapping of
key and value.
In HashSet, we store
 
objects.
It does not allow
 
duplicate keys,
but
 
duplicate values 
are 
allowed.
It does not allow
 
duplicate
values.
It can contain a
 
single null
key 
and 
multiple null values.
It can contain
 
a single null value.

42. HashMap Vs. HashSet
3-February-2003 42
HashMap uses the
 
put() 
method
to add the elements in the
HashMap.
HashSet uses the
 
add() 
method to
add elements in the HashSet.
HashMap is
 
faster/
 than HashSet
because values are associated
with a unique key.
HashSet is
 
slower 
than HashMap
because the member object is
used for calculating hashcode
value, which can be same for two
objects.
Only
 
one 
object is created during
the add operation.
There are
 
two 
objects created
during put operation, one
for
 
key 
and one for 
value.
HashMap internally
uses
 
hashing 
to store objects.
HashSet internally uses
a
 
HashMap 
object to store
objects.
Always prefer when we do not
maintain the
 
uniqueness.
It is used when we need to
maintain the
 
uniqueness 
of data.

43. 3-February-2003 43
HashMap and TreeMap
•HashMap
»The keys are a set - unique, unordered
»Fast
•TreeMap
»The keys are a set - unique, ordered
»Same options for ordering as a TreeSet
•Natural order (Comparable, compareTo(Object))
•Special order (Comparator, compare(Object, Object))

44. HashMap/TreeMap
3-February-2003 44
HashMap TreeMap
HashMap contains value
based on the key.
TreeMap also contains value
based on the key.
It may have a single null key
and multiple null values.
TreeMap is sorted by keys.
HashMap does not maintain
order while iterating.
It contains unique elements.
It contains unique elements.It cannot have a null key but
have multiple null values.
It works on the principle of
hashing.
It stores the object in the tree
structure.

45. Comparator interface
•Java Comparator interface
 is used to order the
objects of a user-defined class.
•This interface is found in java.util package and
contains 2 methods compare(Object
obj1,Object obj2) and equals(Object element).
•It provides multiple sorting sequences, i.e.,
you can sort the elements on the basis of any
data member, for example, rollno.
3-February-2003 45

46. Comparable interface
•Java Comparable interface is used to order the
objects of the user-defined class.
•This interface is found in java.lang package
and contains only one method named
compareTo(Object).
•It provides a single sorting sequence only, i.e.,
you can sort the elements on the basis of single
data member only.
3-February-2003 46

47. compareTo method
•It is used to compare the current object with
the specified object.
•It returns positive integer, if the current object
is greater than the specified object.
•negative integer, if the current object is less
than the specified object.
•zero, if the current object is equal to the
specified object.
3-February-2003 47

48. 3-February-2003 48
Utilities Context

49. 3-February-2003 49
Utilities
•The Collections class provides a number of static
methods for fundamental algorithms
•Most operate on Lists, some on all Collections
»Sort, Search, Shuffle
»Reverse, fill, copy
»Min, max
•Wrappers
»synchronized Collections, Lists, Sets, etc
»unmodifiable Collections, Lists, Sets, etc

50. 3-February-2003 50
Legacy classes
•Still available
•Don’t use for new development
»unless you have to, eg, J2ME, J2EE in some cases
•Retrofitted into Collections framework
•Hashtable
»use HashMap
•Enumeration
»use Collections and Iterators
»if needed, can get an Enumeration with
Collections.enumeration(Collection c)

51. 3-February-2003 51
More Legacy classes
•Vector
»use ArrayList
•Stack
»use LinkedList
•BitSet
»use ArrayList of boolean, unless you can’t stand the
thought of the wasted space
•Properties
»legacies are sometimes hard to walk away from …
»see next few pages

52. 3-February-2003 52
Properties class
•The Properties class in Java is used to manage a collection of
key-value pairs, similar to a hashtable.
•It is specifically designed to work with strings for both keys
and values. This makes it particularly useful for storing
configuration settings or other data that can be easily
represented as text.
•Located in java.util package
•Special case of Hashtable
»Keys and values are Strings
»Tables can be saved to/loaded from file

53. Properties Methods
3-February-2003 53

54. 3-February-2003 54
System properties
•Java VM maintains set of properties that
define system environment
»Set when VM is initialized
»Includes information about current user, VM
version, Java environment, and OS configuration
Properties prop = System.getProperties();
Enumeration e = prop.propertyNames();
while (e.hasMoreElements()) {
String key = (String) e.nextElement();
System.out.println(key + " value is " +
prop.getProperty(key));
}