Collections Overview

1. Introduction
The Java Collections Framework standardizes the way in which groups of objects are handled
by programs.
Collections were not part of the original Java release and were added in J2SE 1.2.
Before collections, Java used ad hoc classes such as:
 Dictionary
 Vector
 Stack
 Properties
These classes were useful, but they lacked a central, unifying theme.

2. Problems with Old Collection Classes

The way Vector was used was different from the way Properties was used.
The early ad hoc approach was not designed to be easily extended or adapted.
Because of these problems, collections were introduced as a better solution.

3. Goals of the Collections Framework

a) High Performance
The framework had to be high-performance.
It provides efficient implementations of:
 Dynamic arrays
 Linked lists
 Trees
 Hash tables
b) Similar Usage
Different types of collections work in a similar manner.
This provides a high degree of interoperability between collections.

c) Easy Extension
Extending or adapting a collection is easy.
The framework is built on a set of standard interfaces.
Standard implementations include:
 LinkedList
 HashSet
 TreeSet
You can use these classes directly or create your own collection.

4. Special and Partial Implementations

Some special-purpose implementations are provided for convenience.
Partial implementations help in creating new collection classes easily.

5. Arrays and Collections

Mechanisms are provided to allow the integration of standard arrays into the Collections
Framework.

6. Algorithms
Algorithms are an important part of collections.
They are defined as static methods in the Collections class.
They work on all collections and provide a standard way to manipulate data.

7. Iterator Interface
The Iterator interface provides a standard way to access elements of a collection one at a
time.
It allows enumerating the contents of a collection.
Because every collection provides an iterator, the same code can be used to traverse different
collections like sets and lists.

8. Spliterator (JDK 8)
JDK 8 introduced spliterator.
Spliterators support parallel iteration.
Interfaces include:
 Spliterator
 Nested interfaces for primitive types

9. Primitive Iterators
Iterator interfaces are also available for primitive types, such as:
  PrimitiveIterator
 [Link]

10. Maps
The framework also includes map interfaces and classes.
Maps store key/value pairs.
Maps are not collections in the strict sense, but a collection view of a map can be obtained to
process map elements as a collection.

11. Retrofitting Old Classes

The collection mechanism was added to some original [Link] classes.
No old class was deprecated.
Collections simply provide a better way of doing things.

The Collection Interfaces

1. Introduction
The Collections Framework defines several core interfaces.
These interfaces are important because they determine the fundamental nature of the collection
classes.
The concrete classes simply provide different implementations of the standard interfaces.
So, understanding interfaces is necessary before studying collection classes.

2. Core Collection Interfaces

The interfaces that underpin collections are summarized below.
2.1 Collection
 Enables you to work with groups of objects
 It is at the top of the collections hierarchy

2.2 List
 Extends Collection
 Handles sequences (lists of objects)

2.3 Set
 Extends Collection
 Handles sets
 Sets must contain unique elements

2.4 SortedSet
 Extends Set
 Handles sorted sets

2.5 NavigableSet
 Extends SortedSet
  Handles retrieval of elements based on closest-match searches

2.6 Queue
 Extends Collection
 Handles special types of lists
 Elements are removed only from the head

2.7 Deque
 Extends Queue
 Handles a double-ended queue

3. Other Important Interfaces

In addition to the collection interfaces, collections also use:
 Comparator
 RandomAccess
 Iterator
 ListIterator
 Spliterator
These interfaces are described in detail later in the chapter.

3.1 Comparator
 Defines how two objects are compared

3.2 Iterator, ListIterator, Spliterator

 Used to enumerate the objects within a collection
 Provide a standard way to access elements

3.3 RandomAccess
 When a list implements RandomAccess, it indicates that the list supports efficient,
random access to its elements

4. Optional Methods in Collection Interfaces

To provide greater flexibility, the collection interfaces allow some methods to be optional.
 Optional methods enable you to modify the contents of a collection
 Collections that support these methods are called modifiable
 Collections that do not allow their contents to be changed are called unmodifiable

5. UnsupportedOperationException
If an attempt is made to use one of the optional methods on an unmodifiable collection, an
UnsupportedOperationException is thrown.

6. Built-in Collections
All the built-in collections are modifiable.
The Collection Interface – Simple Notes
1. Introduction
The Collection interface is the foundation of the Collections Framework.
Any class that defines a collection must implement Collection.
It is a generic interface:
interface Collection<E>
Here, E specifies the type of objects the collection holds.

2. Collection and Iterable

Collection extends the Iterable interface.
Because of this:
 All collections can be used in a for-each loop
 Only classes that implement Iterable can be used in such loops

3. Methods of Collection Interface

The Collection interface declares core methods that all collections have.
Understanding these methods is necessary to understand the framework.
Some methods may throw exceptions:
 UnsupportedOperationException – if modification is not allowed
 ClassCastException – incompatible object types
 NullPointerException – null elements not allowed
 IllegalArgumentException – invalid argument

4. Important Methods of Collection Interface

Method Description
Adds obj to the invoking collection. Returns true if obj
boolean add(E obj) was added. Returns false if obj is already a member
and duplicates are not allowed.
boolean addAll(Collection<? Adds all elements of c to the invoking collection. Returns
extends E> c) true if the collection changed.
void clear() Removes all elements from the invoking collection.
Returns true if obj is an element of the invoking
boolean contains(Object obj)
collection.
boolean containsAll(Collection<?> Returns true if the invoking collection contains all
c) elements of c.
boolean equals(Object obj) Returns true if the invoking collection and obj are equal.
int hashCode() Returns the hash code for the invoking collection.
boolean isEmpty() Returns true if the invoking collection is empty.
Iterator<E> iterator() Returns an iterator for the invoking collection.
default Stream<E>
parallelStream() Returns a stream that supports parallel operations.
 Method Description
boolean remove(Object obj) Removes one instance of obj. Returns true if removed.
boolean removeAll(Collection<?>
c) Removes all elements of c. Returns true if changed.
default boolean
removeIf(Predicate<? super E> Removes elements that satisfy the predicate.
predicate)
boolean retainAll(Collection<?>
c) Retains only elements in c. Returns true if changed.
int size() Returns the number of elements.
default Spliterator<E>
spliterator() Returns a spliterator for the collection.
default Stream<E> stream() Returns a sequential stream.
default <T> T[]
Returns an array created by arrayGen. Throws
toArray(IntFunction<T[]>
arrayGen) ArrayStoreException if incompatible.
Object[] toArray() Returns an array of elements.
<T> T[] toArray(T[] array) Returns elements in array or a new array if required.

Add & Remove Operations

 boolean add(E obj)
Adds an object to the collection
 boolean addAll(Collection<? extends E> c)
Adds all elements of another collection
 boolean remove(Object obj)
Removes one instance of the object
 boolean removeAll(Collection<?> c)
Removes all elements of another collection
 boolean retainAll(Collection<?> c)
Keeps only elements present in another collection
 void clear()
Removes all elements

Search Operations
 boolean contains(Object obj)
Checks if object exists
 boolean containsAll(Collection<?> c)
Checks if all elements exist

Size and Status

int size()
Returns number of elements
 boolean isEmpty()
Checks if collection is empty

Iterator and Streams

  Iterator<E> iterator()
Returns an iterator
 Spliterator<E> spliterator()
Returns a spliterator
 Stream<E> parallelStream()
Returns a parallel stream

Utility Methods
 boolean equals(Object obj)
Compares collections
 int hashCode()
Returns hash code
 boolean removeIf(Predicate<? super E> predicate)
Removes elements that satisfy a condition

The List Interface

The List interface extends Collection and declares the behavior of a collection that stores a
sequence of elements.
 Elements can be inserted or accessed by their position in the list.
 A zero-based index is used (first element is at index 0).
 A list may contain duplicate elements.
List is a generic interface and has this declaration:
interface List<E>
Here, E specifies the type of objects that the list will hold.

Exceptions Used by List Methods

Several List methods can throw exceptions:
 UnsupportedOperationException
Thrown if the list cannot be modified (for example, unmodifiable lists).
 ClassCastException
Generated when an object is incompatible with the elements in the list.
 IndexOutOfBoundsException
Thrown if an invalid index is used.
 NullPointerException
Thrown if a null object is stored and null elements are not allowed.
 IllegalArgumentException
Thrown if an invalid argument is used.

List-Specific Behavior
 List changes the behavior of:
o add(E)
o addAll(Collection)
These methods add elements to the end of the list.
 List also adds index-based methods such as:
o add(int, E)
 o addAll(int, Collection)
These methods insert elements at a specific index.

Table 20-2: The Methods Declared by List

Method Description
Inserts obj into the invoking list at the index passed
void add(int index, E obj) in index. Any preexisting elements at or beyond the
point of insertion are shifted up.
boolean addAll(int index, Inserts all elements of c into the invoking list at
Collection<? extends E> c) position index. Returns true if the list changes.
E get(int index) Returns the element at position index.
int indexOf(Object obj)
Returns the index of the first instance of obj in the
invoking list. Returns -1 if obj is not found.
int lastIndexOf(Object obj)
Returns the index of the last instance of obj in the
invoking list. Returns -1 if obj is not found.
ListIterator<E> listIterator() Returns an iterator to the invoking list.
ListIterator<E> listIterator(int
index) Returns an iterator that begins at position index.

E remove(int index)
Removes the element at position index and returns
the deleted element.
Assigns obj to the location specified by index.
E set(int index, E obj) Returns the element previously stored at that
location.
default void Applies the operator to each element and replaces it
replaceAll(UnaryOperator<E> op) with the result.
default void sort(Comparator<?
super E> comp) Sorts the list using the specified comparator.

List<E> subList(int start, int end)

Returns a list backed by the invoking list from
index start to end − 1.

1. void add(int index, E obj)

 Inserts obj at the specified index.
 Existing elements are shifted to the right.
 Throws:
o IndexOutOfBoundsException
o UnsupportedOperationException

2. boolean addAll(int index, Collection<? extends E> c)

 Inserts all elements of collection c starting at index.
 Returns true if the list changes.
 Throws:
o IndexOutOfBoundsException
o UnsupportedOperationException
 o ClassCastException
o NullPointerException

3. E get(int index)
 Returns the element stored at the specified index.
 Does not modify the list.
 Throws:
o IndexOutOfBoundsException

4. E set(int index, E obj)

 Replaces the element at index with obj.
 Returns the old element.
 Throws:
o IndexOutOfBoundsException
o UnsupportedOperationException
o ClassCastException
o NullPointerException

5. int indexOf(Object obj)

 Returns the index of the first occurrence of obj.
 Returns –1 if not found.

6. int lastIndexOf(Object obj)

 Returns the index of the last occurrence of obj.
 Returns –1 if not found.

7. List subList(int start, int end)

 Returns a portion of the list from start (inclusive) to end (exclusive).
 The returned list is backed by the original list.
 Changes affect both lists.
 Throws:
o IndexOutOfBoundsException
o IllegalArgumentException

8. void replaceAll(UnaryOperator op)

 Replaces each element using the given operator.
 Used to modify every element in the list.
 Throws:
o UnsupportedOperationException

9. void sort(Comparator<? super E> comp)

 Sorts the list using the specified comparator.
 If comp is null, natural ordering is used.
 Throws:
o ClassCastException
 o UnsupportedOperationException

10. ListIterator listIterator()

 Returns a ListIterator starting at the beginning.
 Allows forward and backward traversal.

11. ListIterator listIterator(int index)

 Returns a ListIterator starting at the specified index.
 Throws:
o IndexOutOfBoundsException

Factory Methods (JDK 9 and Later)

[Link]( ) Methods
Beginning with JDK 9, List includes the of() factory method.
 Returns an unmodifiable, value-based list
 Mainly used to create small lists efficiently
 Null elements are not allowed
Examples:
static <E> List<E> of()
static <E> List<E> of(E e1)
static <E> List<E> of(E e1, E e2)
...
static <E> List<E> of(E... elements)

The Set Interface

The Set interface defines a set.
It extends Collection and specifies the behavior of a collection that does not allow duplicate
elements.
 A Set cannot contain duplicate elements.
 Therefore, the add() method returns false if an attempt is made to add a duplicate
element.
 With two exceptions, Set does not specify any additional methods of its own.
 Most of its behavior is inherited from the Collection interface.
Set is a generic interface and has this declaration:
interface Set<E>
Here, E specifies the type of objects that the set will hold.

Important Characteristics of Set

 No duplicate elements allowed
 Order is not guaranteed (unless a specific implementation like LinkedHashSet or
TreeSet is used)
 Equality is usually based on element values, not insertion position
 If duplicates are added, the operation fails silently by returning false
Exceptions Used with Set
Set methods may throw the following exceptions:
 UnsupportedOperationException
Thrown if the set is unmodifiable and a modification is attempted.
 ClassCastException
Thrown if an object is incompatible with the elements of the set.
 NullPointerException
Thrown if a null element is used and nulls are not allowed.
 IllegalArgumentException
Thrown if an invalid argument is used.

Factory Methods in Set (JDK 9 and Later)

Beginning with JDK 9, Set includes the of() factory method.
Purpose of of()
 Provides a convenient and efficient way to create a small Set
 Returns an unmodifiable, value-based collection
 The returned Set cannot be modified
 Null elements are not allowed
 Duplicate elements are not allowed

Overloads of [Link]()
There are 12 overloads of the of() method.

1. Empty Set
static <E> Set<E> of()
 Creates an empty set
 The returned set is unmodifiable

2. Sets with 1 to 10 Elements

static <E> Set<E> of(E obj1)
static <E> Set<E> of(E obj1, E obj2)
static <E> Set<E> of(E obj1, E obj2, E obj3)
...
static <E> Set<E> of(E obj1, E obj2, E obj3, E obj4, E obj5,
E obj6, E obj7, E obj8, E obj9, E obj10)
 Creates a Set containing the specified elements
 Duplicate elements cause an exception
 Null elements are not allowed

3. Varargs Version
static <E> Set<E> of(E... objs)
 Accepts an arbitrary number of elements
 Can also take an array
 Still unmodifiable
 No nulls
 No duplicates
Important Notes About [Link]()
 The implementation is unspecified
 Returned Set is:
o Unmodifiable
o Value-based
 Any attempt to modify the set throws:
o UnsupportedOperationException

copyOf() Method (JDK 10 and Later)

Beginning with JDK 10, Set includes the static copyOf() method.
Declaration
static <E> Set<E> copyOf(Collection<? extends E> from)
Description
 Returns a Set containing the same elements as the collection from
 Null values are not allowed
 The returned Set is:
o Unmodifiable
o Value-based
 If from already represents an unmodifiable Set, it may be returned directly

The SortedSet Interface

The SortedSet interface extends Set and declares the behavior of a set sorted in ascending
order.
 A SortedSet stores elements in sorted (ascending) order
 Sorting is done either:
o By the natural ordering of elements, or
o By a Comparator provided at the time of creation
SortedSet is a generic interface and has this declaration:
interface SortedSet<E>
Here, E specifies the type of objects that the set will hold.

Exceptions Thrown by SortedSet Methods

In addition to the methods provided by Set, the SortedSet interface declares its own methods.
Several methods can throw the following exceptions:
 NoSuchElementException
Thrown when no items are contained in the invoking set (for example, calling first()
or last() on an empty set).
 ClassCastException
Thrown when an object is incompatible with the elements in the set.
 NullPointerException
Thrown if an attempt is made to use a null object and null is not allowed in the set.
  IllegalArgumentException
Thrown if an invalid argument is used.

Purpose of SortedSet Methods

SortedSet defines several methods that make set processing more convenient, especially when
working with ordered data.

Important Methods of SortedSet

Method Description
Returns the comparator or null if natural ordering is
Comparator<? super E> comparator()
used.
E first() Returns the first element.
SortedSet<E> headSet(E end) Returns elements less than end.
E last() Returns the last element.
SortedSet<E> subSet(E start, E
end) Returns elements from start to end−1.
SortedSet<E> tailSet(E start) Returns elements ≥ start.

1. first( )
 Returns the first (lowest) element in the sorted set.
 Throws NoSuchElementException if the set is empty.

2. last( )
 Returns the last (highest) element in the sorted set.
 Throws NoSuchElementException if the set is empty.

3. subSet( )
 Used to obtain a subset of a sorted set.
 You specify the starting element and ending element.
 Returns elements from start to end − 1.
 The returned set is backed by the original set (changes affect both).

4. headSet( )
 Returns a subset that starts with the first element of the set.
 Contains all elements less than the specified element.
 Useful when you need elements before a given value.

5. tailSet( )
 Returns a subset that ends at the last element of the set.
 Contains all elements greater than or equal to the specified element.
 Useful when you need elements after a given value.
Key Characteristics of SortedSet
 Elements are always sorted
 Duplicate elements are not allowed (inherited from Set)
 Order is maintained automatically
 Subsets are views of the original set, not copies

The NavigableSet Interface

The NavigableSet interface extends SortedSet and declares the behavior of a collection that
supports retrieval of elements based on the closest match to a given value or values.
 It allows navigation operations such as finding:
o The closest greater element
o The closest smaller element
o Elements just above or below a given value
NavigableSet is a generic interface and has this declaration:
interface NavigableSet<E>
Here, E specifies the type of objects that the set will hold.

Inheritance Hierarchy
Collection
└── Set
└── SortedSet
└── NavigableSet
 NavigableSet inherits all methods of SortedSet and Set
 Adds navigation-specific methods

Exceptions Thrown by NavigableSet Methods

Several methods of NavigableSet can throw the following exceptions:
 ClassCastException
Thrown when an object is incompatible with the elements in the set.
 NullPointerException
Thrown if an attempt is made to use a null object, and null is not allowed in the set.
 IllegalArgumentException
Thrown if an invalid argument is used.

Methods Added by NavigableSet (Table 20-4)

Method Description
Returns smallest element ≥ obj,
E ceiling(E obj)
or null.
Iterator<E> descendingIterator() Returns a reverse iterator.
Returns a reversed set backed by
NavigableSet<E> descendingSet()
the original.
E floor(E obj) Returns largest element ≤ obj, or
 Method Description
null.
Returns elements less than
NavigableSet<E> headSet(E upperBound, boolean incl)
upperBound.
E higher(E obj) Returns smallest element > obj.
E lower(E obj) Returns largest element < obj.
Removes and returns the first
E pollFirst()
element.
Removes and returns the last
E pollLast()
element.
NavigableSet<E> subSet(E low, boolean lowIncl, E
high, boolean highIncl) Returns a bounded subset.
Returns elements ≥
NavigableSet<E> tailSet(E lowerBound, boolean incl)
lowerBound.

1. ceiling(E obj)
 Searches the set for the smallest element e such that e ≥ obj
 Returns the element if found
 Returns null if no such element exists

2. floor(E obj)
 Searches the set for the largest element e such that e ≤ obj
 Returns the element if found
 Returns null if no such element exists

3. higher(E obj)
 Searches the set for the smallest element e such that e > obj
 Returns the element if found
 Returns null if no such element exists

4. lower(E obj)
 Searches the set for the largest element e such that e < obj
 Returns the element if found
 Returns null if no such element exists

5. descendingIterator( )
 Returns an iterator that moves from the greatest element to the least
 Provides reverse traversal of the set

6. descendingSet( )
 Returns a NavigableSet in reverse order
 The returned set is backed by the invoking set
 Changes in one set affect the other
7. pollFirst( )
 Returns and removes the first (lowest) element
 Returns null if the set is empty

8. pollLast( )
 Returns and removes the last (highest) element
 Returns null if the set is empty

9. headSet(E upperBound, boolean incl)

 Returns a NavigableSet containing elements less than upperBound
 If incl is true, upperBound is included
 The returned set is backed by the original set

10. tailSet(E lowerBound, boolean incl)

 Returns a NavigableSet containing elements greater than lowerBound
 If incl is true, lowerBound is included
 The returned set is backed by the original set

11. subSet(E lowerBound, boolean lowIncl, E upperBound, boolean highIncl)

 Returns a NavigableSet containing elements:
o Greater than lowerBound
o Less than upperBound
 Inclusion depends on:
o lowIncl
o highIncl
 The returned set is backed by the original set

Key Characteristics of NavigableSet

 Maintains sorted order
 Supports nearest-match searches
 Does not allow duplicate elements
 Provides bidirectional traversal
 Subsets are views, not copies

Queue Interface (Simple Explanation)

 A Queue is a collection that usually works on FIFO
(First In, First Out).
 Elements are added at the rear (tail) and removed from the front (head).
 Queue extends the Collection interface.
Declaration
interface Queue<E>
Important points
  Elements are removed only from the head
 Some queues have fixed size
 null elements are usually not allowed
Method Description
E element() Returns head element without removing it. Throws exception if empty.
boolean offer(E obj) Attempts to add an element.
E peek() Returns head element or null.
E poll() Removes and returns head or null.
E remove() Removes and returns head. Throws exception if empty.

Queue Methods (Easy Meaning)

Method What it does
offer(e) Tries to add element to queue, returns false if full
add(e) Adds element, throws exception if queue is full
peek() Returns head element, does not remove, returns null if empty
element() Same as peek, but throws exception if empty
poll() Removes & returns head element, returns null if empty
remove() Removes & returns head element, throws exception if empty
📌 Key difference to remember (important for exams):
 poll() → returns null if empty
 remove() → throws exception if empty
 peek() → returns null if empty
 element() → throws exception if empty

Example
Queue<Integer> q = new LinkedList<>();
[Link](10);
[Link](20);
[Link](30);

[Link](); // removes 10
[Link](); // returns 20

Deque Interface (Double-Ended Queue)

 Deque means Double Ended Queue
 You can add and remove elements from both ends
 Can act as:
o Queue (FIFO)
o Stack (LIFO)

Table 20-6: The Methods Declared by Deque

Insertion & Removal
 Method Description
void addFirst(E obj) Adds element at head.
void addLast(E obj) Adds element at tail.
E removeFirst() Removes and returns first element.
E removeLast() Removes and returns last element.
boolean removeFirstOccurrence(Object obj) Removes first occurrence.
boolean removeLastOccurrence(Object obj) Removes last occurrence.
Access Operations
Method Description
E getFirst() Returns first element without removing.
E getLast() Returns last element without removing.
E peekFirst() Returns first or null.
E peekLast() Returns last or null.
Offer / Poll
Method Description
boolean offerFirst(E obj) Attempts to add at head.
boolean offerLast(E obj) Attempts to add at tail.
E pollFirst() Removes and returns first or null.
E pollLast() Removes and returns last or null.
Stack Operations
Method Description
void push(E obj) Pushes element at head.
E pop() Pops element from head.
Iteration
Method Description
Iterator<E> descendingIterator() Iterates from tail to head.
Declaration
interface Deque<E>

Deque Key Features

 Insert/remove from front and rear
 Supports stack operations using push() and pop()
 Can be capacity-restricted

Deque Methods (Simple Meaning)

Adding elements
Method Meaning
addFirst(e) Adds element at front (exception if full)
addLast(e) Adds element at end
offerFirst(e) Tries to add at front (returns false if full)
offerLast(e) Tries to add at end
 Method Meaning

Viewing elements (no removal)

Method Meaning
getFirst() Returns first element (exception if empty)
getLast() Returns last element
peekFirst() Returns first element, null if empty
peekLast() Returns last element, null if empty
Removing elements
Method Meaning
pollFirst() Removes first element, null if empty
pollLast() Removes last element
pop() Removes first element (stack operation)

Deque as a Stack
Deque<Integer> d = new ArrayDeque<>();
[Link](10);
[Link](20);
[Link](); // removes 20

Reverse Traversal
 descendingIterator()
→ Iterates from last to first

3. Queue vs Deque (Quick Comparison)

Feature Queue Deque
Ends used One end Both ends
FIFO Yes Yes
Stack support No Yes
Flexibility Less More

The Collection Classes

After understanding the collection interfaces, we can examine the standard classes that
implement them.
 Some classes provide full implementations that can be used as-is.
 Others are abstract, providing skeletal implementations used as starting points for
creating concrete collections.
 As a general rule, the collection classes are not synchronized, but synchronized
versions can be obtained (discussed later in the chapter).
Core Collection Classes
The core collection classes are summarized in the table below:
 Class Description
AbstractCollection Implements most of the Collection interface.
Extends AbstractCollection and implements most of the List
AbstractList
interface.
Extends AbstractCollection and implements parts of the Queue
AbstractQueue
interface.
Extends AbstractList for collections that use sequential access rather
AbstractSequentialList
than random access.
LinkedList Implements a linked list by extending AbstractSequentialList.
ArrayList Implements a dynamic array by extending AbstractList.
Implements a dynamic double-ended queue by extending
ArrayDeque
AbstractCollection and implementing the Deque interface.
Extends AbstractCollection and implements most of the Set
AbstractSet
interface.
EnumSet Extends AbstractSet for use with enum elements.
HashSet Extends AbstractSet for use with a hash table.
LinkedHashSet Extends HashSet to allow insertion-order iterations.
PriorityQueue Extends AbstractQueue to support a priority-based queue.
TreeSet Implements a set stored in a tree. Extends AbstractSet.

Notes
 These classes provide the foundation for concrete collection objects.
 They can be used directly, or extended to create custom collections.
 Legacy classes such as Vector, Stack, and Hashtable have been reengineered to
support the Collections Framework. These are discussed later in the chapter.

The ArrayList Class

 The ArrayList class:
o Extends AbstractList
o Implements the List interface
o Declared as a generic class:
 class ArrayList<E>
Here, E specifies the type of objects that the list will hold.

Dynamic Array Support

 Unlike standard Java arrays (which are fixed-length), ArrayList supports dynamic
arrays that can grow or shrink at runtime.
 Why use ArrayList?
o Standard arrays require you to know their size in advance.
 o ArrayList allows for variable-length arrays of object references, growing
automatically when more elements are added, and shrinking when elements are
removed.
 Note: Legacy class Vector also supports dynamic arrays (covered later).

Constructors
1. ArrayList()
o Creates an empty ArrayList.
2. ArrayList(Collection<? extends E> c)
o Creates an ArrayList initialized with the elements of another collection c.
3. ArrayList(int capacity)
o Creates an ArrayList with a specified initial capacity.
o Capacity is the size of the underlying array. It grows automatically as elements
are added.

Example Program
import [Link].*;
class ArrayListDemo {
public static void main(String[] args) {
// Create an array list.
ArrayList<String> al = new ArrayList<String>();
[Link]("Initial size of al: " + [Link]());

// Add elements to the array list.

[Link]("C");
[Link]("A");
[Link]("E");
[Link]("B");
[Link]("D");
[Link]("F");
[Link](1, "A2"); // Inserts at index 1

[Link]("Size of al after additions: " + [Link]());

[Link]("Contents of al: " + al);

// Remove elements
[Link]("F"); // Removes object F
[Link](2); // Removes element at index 2

[Link]("Size of al after deletions: " + [Link]());

[Link]("Contents of al: " + al);
}
}
Output:
Initial size of al: 0
Size of al after additions: 7
Contents of al: [C, A2, A, E, B, D, F]
Size of al after deletions: 5
Contents of al: [C, A2, E, B, D]
Observations:
 The ArrayList starts empty and grows as elements are added.
  Removing elements decreases its size.
 toString() (inherited from AbstractCollection) is used for default display.

Capacity Management
 Automatic resizing:
o ArrayList increases its capacity automatically as elements are added beyond the
current limit.
 Manual resizing:
o ensureCapacity(int cap): Increases the minimum capacity to cap.
o void ensureCapacity(int cap)
 Useful when expecting to store many elements in advance.
 Reduces reallocation overhead, improving performance.
o trimToSize(): Shrinks the underlying array to match the current number of
elements.
 Helps free memory if many elements have been removed.

Key Notes on Behavior

 Adding elements:
o add(E obj) adds to the end.
o add(int index, E obj) inserts at a specific position.
 Removing elements:
o remove(Object obj) removes by value.
o remove(int index) removes by position.
 Accessing elements:
o get(int index) retrieves an element.
o set(int index, E obj) replaces an element at a position.
 Size and emptiness:
o size() returns the current number of elements.
o isEmpty() checks if the list is empty.
 Conversion to arrays:
o toArray() returns an Object array.
o toArray(T[] array) returns a typed array.
 Exceptions:
o IndexOutOfBoundsException: Accessing invalid index.
o NullPointerException: Adding null if not allowed.

Obtaining an Array from an ArrayList

When working with ArrayList, you will sometimes want to obtain an actual array that contains
the contents of the list. This can be done by calling toArray( ), which is defined by the
Collection interface.
There are several reasons why you might want to convert a collection into an array, such as:
  To obtain faster processing times for certain operations
 To pass an array to a method that is not overloaded to accept a collection
 To integrate collection-based code with legacy code that does not understand
collections
Whatever the reason, converting an ArrayList to an array is a trivial matter.

Versions of toArray( )
As explained earlier, there are three versions of toArray( ), shown again here for convenience:
Object[ ] toArray( )
<T> T[ ] toArray(T[ ] array)
default <T> T[ ] toArray(IntFunction<T[ ]> arrayGen)
Explanation of Each Version
1. Object[ ] toArray( )
o Returns an array of type Object
o Requires casting if a specific type is needed
2. T[ ] toArray(T[ ] array)
o Returns an array of elements having the same type as T
o If the given array is large enough, elements are stored in it
o If not, a new array of required size is created
o This form is most convenient and commonly used
3. T[ ] toArray(IntFunction<T[ ]> arrayGen)
o Introduced to allow array creation using a function
o Useful when working with streams and functional programming
In this example, the second form is used because of its convenience.

Program to Convert an ArrayList into an Array

// Convert an ArrayList into an array.
import [Link].*;
class ArrayListToArray {
public static void main(String[] args) {

// Create an array list.

ArrayList<Integer> al = new ArrayList<Integer>();

// Add elements to the array list.

[Link](1);
[Link](2);
[Link](3);
[Link](4);

[Link]("Contents of al: " + al);

// Get the array.

Integer[] ia = new Integer[[Link]()];
ia = [Link](ia);

int sum = 0;

// Sum the array.

for(int i : ia)
 sum += i;

[Link]("Sum is: " + sum);

}
}

Output of the Program

Contents of al: [1, 2, 3, 4]
Sum is: 10

Program Explanation
 An ArrayList of Integer objects is created.
 Integer elements are added to the list using add( ).
 The toArray( ) method converts the ArrayList into an Integer array.
 The contents of the array are processed using a for-each loop.
 All values are summed and displayed.

Important Point: Autoboxing

Collections can store only object references, not primitive values.
However, autoboxing makes it possible to pass primitive values (such as int) directly to
add( ).
 When [Link](1) is written:
o The primitive int value 1 is automatically wrapped into an Integer object.
 This process is called autoboxing.
Autoboxing eliminates the need for manual conversion and significantly improves the ease
with which collections can be used to store primitive values.

The LinkedList Class

The LinkedList class:
 Extends AbstractSequentialList
 Implements the List, Deque, and Queue interfaces
 Provides a linked-list data structure
LinkedList is a generic class and has the following declaration:
class LinkedList<E>
Here, E specifies the type of objects that the list will hold.

Constructors of LinkedList
LinkedList provides two constructors:
LinkedList( )
LinkedList(Collection<? extends E> c)
Explanation
 LinkedList( )
Builds an empty linked list.
  LinkedList(Collection<? extends E> c)
Builds a linked list that is initialized with the elements of collection c.

Deque Support in LinkedList

Because LinkedList implements the Deque interface, it supports double-ended operations.
This means elements can be added, removed, or accessed from both ends of the list.
Adding Elements
 addFirst(E obj) or offerFirst(E obj) → adds element at the start
 addLast(E obj) or offerLast(E obj) → adds element at the end
Accessing Elements
 getFirst() or peekFirst() → gets the first element
 getLast() or peekLast() → gets the last element
Removing Elements
 removeFirst() or pollFirst() → removes the first element
 removeLast() or pollLast() → removes the last element

LinkedList Demonstration Program

// Demonstrate LinkedList.
import [Link].*;
class LinkedListDemo {
public static void main(String[] args) {

// Create a linked list.

LinkedList<String> ll = new LinkedList<String>();

// Add elements to the linked list.

[Link]("F");
[Link]("B");
[Link]("D");
[Link]("E");
[Link]("C");
[Link]("Z");
[Link]("A");
[Link](1, "A2");

[Link]("Original contents of ll: " + ll);

// Remove elements from the linked list.

[Link]("F");
[Link](2);

[Link]("Contents of ll after deletion: "

+ ll);

// Remove first and last elements.

[Link]();
[Link]();

[Link]("ll after deleting first and last: "

+ ll);
 // Get and set a value.
String val = [Link](2);
[Link](2, val + " Changed");

[Link]("ll after change: " + ll);

}
}

Program Output
Original contents of ll: [A, A2, F, B, D, E, C, Z]
Contents of ll after deletion: [A, A2, D, E, C, Z]
ll after deleting first and last: [A2, D, E, C]
ll after change: [A2, D, E Changed, C]

Explanation of Program Behavior

Adding Elements
 add(E) adds elements to the end of the list
 addFirst("A") inserts element at the beginning
 addLast("Z") inserts element at the end
 add(1, "A2") inserts element at index 1

Removing Elements
 remove("F") removes the specified element
 remove(2) removes element at index 2
 removeFirst() removes the first element
 removeLast() removes the last element

Accessing and Modifying Elements

 get(index) retrieves the element stored at the given index
 set(index, value) replaces the element at the given index with a new value
Example:
String val = [Link](2);
[Link](2, val + " Changed");
This changes the third element in the list.

Important Characteristics of LinkedList

 Stores elements as nodes linked together
 Allows duplicate elements
 Maintains insertion order
 Supports queue and deque operations
 Provides efficient insertion and deletion, especially at the ends
 Slower than ArrayList for random access

Exceptions That May Be Thrown

 IndexOutOfBoundsException → invalid index used
 NoSuchElementException → accessing/removing from an empty list
  NullPointerException → null elements not allowed (depending on implementation)
 ClassCastException → incompatible object type

Exam-Important Points
 LinkedList implements List, Queue, and Deque
 Supports addFirst, addLast, removeFirst, removeLast
 Uses sequential access
 Better for frequent insertions/deletions
 Commonly compared with ArrayList

The HashSet Class

The HashSet class:
 Extends AbstractSet
 Implements the Set interface
 Creates a collection that uses a hash table for storage
HashSet is a generic class and has the following declaration:
class HashSet<E>
Here, E specifies the type of objects that the set will hold.

Hashing and Hash Tables

A hash table stores information using a mechanism called hashing.
 In hashing, the informational content of a key is used to compute a hash code
 The hash code determines the index at which the data is stored
 The transformation of a key into its hash code is done automatically
 The hash code is not visible to the programmer
 The programmer cannot directly index into the hash table
Advantages of Hashing
Hashing allows the execution time of the following operations to remain constant (O(1)), even
for large sets:
 add( )
 contains( )
 remove( )
 size( )
This makes HashSet very efficient for storing large amounts of data.

Constructors of HashSet
HashSet provides the following constructors:
HashSet( )
HashSet(Collection<? extends E> c)
HashSet(int capacity)
HashSet(int capacity, float fillRatio)
Explanation of Constructors
1. HashSet( )
o Constructs a default hash set
o Default capacity is 16
 oDefault fill ratio (load factor) is 0.75
2. HashSet(Collection<? extends E> c)
o Constructs a hash set initialized with the elements of collection c
3. HashSet(int capacity)
o Constructs a hash set with the specified initial capacity
o Capacity refers to the number of buckets in the hash table
4. HashSet(int capacity, float fillRatio)
o Constructs a hash set with:
 Specified capacity
 Specified fill ratio (load factor)

Fill Ratio (Load Factor)

 The fill ratio must be between 0.0 and 1.0
 It determines how full the hash set can become before resizing
 When:
number of elements > capacity × fillRatio
the hash set is resized upward
 For constructors that do not specify a fill ratio, 0.75 is used by default

Methods in HashSet
 HashSet does not define any additional methods
 It uses methods inherited from:
o AbstractSet
o Set
o Collection
Important inherited methods include:
 add( )
 remove( )
 contains( )
 isEmpty( )
 size( )
 iterator( )

Ordering in HashSet
 HashSet does not guarantee the order of its elements
 The order depends on the hashing mechanism
 Elements are not stored in sorted order
 The output order may change between executions
If sorted storage is required, use:
 TreeSet instead of HashSet

HashSet Demonstration Program

// Demonstrate HashSet.
import [Link].*;
class HashSetDemo {
public static void main(String[] args) {
 // Create a hash set.
HashSet<String> hs = new HashSet<String>();

// Add elements to the hash set.

[Link]("Beta");
[Link]("Alpha");
[Link]("Eta");
[Link]("Gamma");
[Link]("Epsilon");
[Link]("Omega");

[Link](hs);
}
}

Program Output
[Gamma, Eta, Alpha, Epsilon, Omega, Beta]

Explanation of Output
 The elements are not displayed in sorted order
 The order is determined by the hash codes
 The exact output may vary between program runs

Important Characteristics of HashSet

 Does not allow duplicate elements
 Allows one null element
 Offers fast performance
 Does not maintain insertion order
 Uses hashing internally

Exceptions That May Be Thrown

 NullPointerException → null not allowed in some operations
 ClassCastException → incompatible object type
 IllegalArgumentException → invalid arguments

Exam-Important Points
 HashSet uses a hash table
 Order of elements is not guaranteed
 Duplicate elements are not allowed
 Default capacity = 16
 Default fill ratio = 0.75
 Best for fast searching, insertion, and deletion
LinkedHashSet and TreeSet
1. Position in Java Collections Framework
 Both LinkedHashSet and TreeSet are implementations of the Set interface.
 Set represents a collection that does not allow duplicate elements.
 Hierarchy (simplified):
Object
└── AbstractCollection
└── AbstractSet
├── HashSet
│ └── LinkedHashSet
└── TreeSet
 LinkedHashSet is closely related to HashSet.
 TreeSet is based on sorted-set concepts and implements NavigableSet.

2. LinkedHashSet Class
2.1 Definition
 LinkedHashSet extends HashSet.
 It does not introduce any new methods of its own.
  Generic class declaration:
class LinkedHashSet<E>
 E represents the type of elements stored in the set.

2.2 Internal Data Structure

 Combines two data structures:
1. Hash table (same as HashSet) – for fast insertion, deletion, and lookup.
2. Doubly linked list – to maintain the order of elements.
 Each element is stored in a hash bucket and linked to the previous and next elements in
insertion order.

2.3 Ordering Property (Most Important Feature)

 Maintains insertion order.
 Elements are iterated:
o In the exact order in which they were inserted into the set.
 This order is preserved:
o During iteration using Iterator
o When using enhanced for-each loop
o When calling toString()

2.4 Key Characteristics

 Does not allow duplicate elements.
 Allows at most one null element.
 Iteration order is predictable (insertion order).
 Performance:
o Slightly slower than HashSet due to linked list maintenance.
o Faster than TreeSet.

2.5 Constructors
LinkedHashSet provides the same constructors as HashSet:
LinkedHashSet()
 Creates an empty LinkedHashSet with default capacity and load factor.
LinkedHashSet(int initialCapacity)
 Creates an empty LinkedHashSet with specified initial capacity.
LinkedHashSet(int initialCapacity, float loadFactor)
 Creates an empty LinkedHashSet with specified capacity and load factor.
LinkedHashSet(Collection<? extends E> c)
 Creates a LinkedHashSet containing elements of the given collection in insertion order.

2.6 Example of LinkedHashSet

import [Link].*;

class LinkedHashSetDemo {
public static void main(String[] args) {
LinkedHashSet<String> lhs = new LinkedHashSet<>();

[Link]("Beta");
[Link]("Alpha");
 [Link]("Eta");
[Link]("Gamma");
[Link]("Epsilon");
[Link]("Omega");

[Link](lhs);
}
}
Output
[Beta, Alpha, Eta, Gamma, Epsilon, Omega]
 Output confirms insertion-order preservation.

2.7 Use Cases of LinkedHashSet

 When duplicates must be avoided and insertion order must be preserved.
 When predictable iteration order is required.
 Suitable for caches, ordered logs, and maintaining unique records with order.

3. TreeSet Class
3.1 Definition
 TreeSet extends AbstractSet.
 Implements NavigableSet interface.
 Generic class declaration:
class TreeSet<E>

3.2 Internal Data Structure

 Uses a Red-Black Tree (self-balancing binary search tree).
 Guarantees:
o Sorted order
o Logarithmic time complexity for basic operations

3.3 Ordering Property (Core Feature)

 Stores elements in sorted (ascending) order by default.
 Sorting is based on:
o Natural ordering (Comparable), or
o Custom ordering (Comparator).

3.4 Key Characteristics

 Does not allow duplicate elements.
 Null elements are not allowed (throws NullPointerException).
 Elements must be:
o Comparable, or
o Inserted with a Comparator.
 Slower than HashSet and LinkedHashSet due to tree operations.

3.5 Constructors of TreeSet

TreeSet()
 Creates an empty TreeSet sorted according to natural ordering.
TreeSet(Collection<? extends E> c)
 Creates a TreeSet containing elements of the given collection.
TreeSet(Comparator<? super E> comp)
 Creates an empty TreeSet sorted according to the given comparator.
TreeSet(SortedSet<E> ss)
 Creates a TreeSet containing elements of another sorted set.

3.6 TreeSet Example

import [Link].*;

class TreeSetDemo {
public static void main(String[] args) {
TreeSet<String> ts = new TreeSet<>();

[Link]("C");
[Link]("A");
[Link]("B");
[Link]("E");
[Link]("F");
[Link]("D");

[Link](ts);
}
}
Output
[A, B, C, D, E, F]
 Confirms automatic sorting.

4. NavigableSet Interface (TreeSet Specific)

4.1 Overview
 NavigableSet extends SortedSet.
 Provides navigation methods for locating elements based on ordering.

4.2 Important NavigableSet Methods

subSet(E fromElement, E toElement)
 Returns elements from fromElement (inclusive) to toElement (exclusive).
Example:
[Link]("C", "F");
Output:
[C, D, E]

headSet(E toElement)
 Returns elements strictly less than toElement.
tailSet(E fromElement)
 Returns elements greater than or equal to fromElement.
lower(E e)
 Greatest element strictly less than e.
higher(E e)
 Smallest element strictly greater than e.
floor(E e)
  Greatest element less than or equal to e.
ceiling(E e)
 Smallest element greater than or equal to e.

5. Performance Comparison
Operation HashSet LinkedHashSet TreeSet
Add O(1) O(1) O(log n)
Remove O(1) O(1) O(log n)
Search O(1) O(1) O(log n)
Ordering None Insertion order Sorted order

6. Comparison Summary
Feature HashSet LinkedHashSet TreeSet
Duplicate Elements Not allowed Not allowed Not allowed
Order No Insertion order Sorted order
Null Allowed One One No
Internal Structure Hash table Hash table + Linked list Red-Black Tree
Best Use Case Fast lookup Ordered unique data Sorted data

7. Exam-Oriented Key Point

 LinkedHashSet preserves insertion order using a linked list.
 TreeSet stores elements in sorted order using a Red-Black Tree.
 TreeSet implements NavigableSet, enabling range-based operations.
 TreeSet does not allow null elements.
 LinkedHashSet is a balance between HashSet speed and ordered iteration.

8. One-Line Memory Rules

 HashSet → Fast, unordered
 LinkedHashSet → Ordered by insertion
 TreeSet → Always sorted
PriorityQueue Class
PriorityQueue is a class present in the [Link] package. It extends AbstractQueue and
implements the Queue interface. It represents a special type of queue in which elements are
processed according to priority, not insertion order.
PriorityQueue is a generic class and is declared as:
class PriorityQueue<E>
Here, E represents the type of
elements stored in the queue.
PriorityQueue is dynamic in nature, meaning its capacity automatically increases as elements
are added.

Concept of Priority in PriorityQueue

In a normal queue, elements are processed in FIFO (First In First Out) order.
In a PriorityQueue, elements are processed based on priority.
 The element with the highest priority is placed at the head of the queue.
 By default, smaller elements have higher priority.
 This means PriorityQueue follows ascending order by default.
Internally, PriorityQueue is implemented using a heap data structure (binary heap).
Ordering of Elements
PriorityQueue orders elements using either:
 Natural ordering of elements
(elements must implement Comparable)
 Custom ordering defined by a Comparator
If no comparator is supplied, natural ordering is used.
Example:
 Smallest number → highest priority
 Alphabetically smallest string → highest priority

Constructors of PriorityQueue
PriorityQueue provides multiple constructors:
PriorityQueue()
Creates an empty priority queue with a default initial capacity of 11 and natural ordering.
PriorityQueue(int capacity)
Creates an empty priority queue with the specified initial capacity.
PriorityQueue(Comparator<? super E> comp)
Creates an empty priority queue ordered according to the given comparator.
PriorityQueue(int capacity, Comparator<? super E> comp)
Creates an empty priority queue with specified capacity and comparator.
PriorityQueue(Collection<? extends E> c)
Creates a priority queue initialized with elements from the given collection.
PriorityQueue(PriorityQueue<? extends E> c)
Creates a priority queue from another priority queue.
PriorityQueue(SortedSet<? extends E> c)
Creates a priority queue initialized with elements from a sorted set.
In all cases, the queue grows automatically when required.

comparator() Method
PriorityQueue provides the method:
Comparator<? super E> comparator()
 Returns the comparator used for ordering.
 Returns null if natural ordering is used.

Important Queue Methods Used with PriorityQueue

 offer(E e)
Inserts an element into the queue.
 poll()
Removes and returns the head element (highest priority).
 peek()
Returns the head element without removing it.

Important Note on Iteration (Very Important for Exams)

Although PriorityQueue supports iteration using an iterator:
 Iteration order is undefined
 Iterator does not return elements in priority order
To correctly retrieve elements based on priority, always use:
  poll()
 peek()
This is a common exam trap.

PriorityQueue Example
import [Link].*;

class PriorityQueueDemo {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>();

[Link](40);
[Link](10);
[Link](30);
[Link](20);

while(![Link]()) {
[Link]([Link]() + " ");
}
}
}
Output:
10 20 30 40
This output confirms that elements are removed in ascending order.

Applications of PriorityQueue
 CPU scheduling
 Task scheduling systems
 Event-driven simulations
 Graph algorithms like Dijkstra’s and Prim’s
 Job processing based on priority

ArrayDeque Class
ArrayDeque is a class in the [Link] package.
It extends AbstractCollection and implements the Deque interface.
ArrayDeque represents a double-ended queue, meaning elements can be inserted and removed
from both ends.
It is a generic class declared as:
class ArrayDeque<E>

Internal Structure of ArrayDeque

 Implemented using a resizable circular array
 No fixed capacity restriction
 Capacity grows automatically as elements are added
 Faster than Stack and LinkedList for most operations

Key Characteristics of ArrayDeque

 Allows insertion and removal at both ends
 Does not allow null elements
  Can be used as:
o Stack (LIFO)
o Queue (FIFO)
o Deque (double-ended queue)
 Recommended replacement for the legacy Stack class

Constructors of ArrayDeque
ArrayDeque()
Creates an empty deque with an initial capacity of 16.
ArrayDeque(int size)
Creates a deque with the specified initial capacity.
ArrayDeque(Collection<? extends E> c)
Creates a deque initialized with elements from the given collection.

Using ArrayDeque as a Stack

ArrayDeque supports stack operations using built-in methods.
import [Link].*;

class ArrayDequeDemo {
public static void main(String[] args) {
ArrayDeque<String> adq = new ArrayDeque<>();

[Link]("A");
[Link]("B");
[Link]("D");
[Link]("E");
[Link]("F");

[Link]("Popping the stack: ");

while([Link]() != null) {
[Link]([Link]() + " ");
}
}
}
Output:
Popping the stack: F E D B A
This confirms LIFO behavior.

Commonly Used Deque Methods

 addFirst() and addLast()
 offerFirst() and offerLast()
 removeFirst() and removeLast()
 pollFirst() and pollLast()
 push() and pop()
 peekFirst() and peekLast()

Comparison Between PriorityQueue and ArrayDeque

PriorityQueue:
 Priority-based ordering
 Head element has highest priority
  Internally uses heap
 Best for scheduling and priority-based processing
ArrayDeque:
 No priority ordering
 Fast insertion and removal at both ends
 Internally uses circular array
 Best for stack and deque operations

Exam Memory Points

 PriorityQueue processes elements based on priority, not insertion order
 Default PriorityQueue is a min-heap
 Iteration order in PriorityQueue is undefined
 ArrayDeque is faster than Stack
 ArrayDeque does not allow null elements

Accessing a Collection via an Iterator

In Java, collections often need to be traversed to access or display their elements. One standard
way to do this is by using an iterator. An iterator is an object that provides a uniform method to
access elements of a collection one by one, without exposing the internal structure of the
collection.

Java provides two iterator interfaces: Iterator and ListIterator. Both are generic interfaces,
meaning they work with any object type.

interface Iterator<E>
interface ListIterator<E>

Here, E represents the type of elements being iterated.

Iterator Interface
The Iterator interface enables forward-only traversal of a collection. It allows reading
elements and optionally removing them during iteration.

Iterator can be used with all collection types such as List, Set, and Queue.

Iterator Methods
hasNext()
Returns true if there are more elements in the collection.

next()
Returns the next element in the collection. Throws NoSuchElementException if no element
exists.

remove()
Removes the current element from the collection.
Must be called after next().
Throws UnsupportedOperationException for read-only collections.

forEachRemaining(Consumer<? super E> action)

Performs the specified action on each remaining element.

Operations that modify the collection are optional. If modification is not supported, appropriate
exceptions are thrown.

Using an Iterator
To traverse a collection using an iterator, the collection’s iterator() method is called to obtain
an iterator positioned at the start.

Traversal is performed by repeatedly checking hasNext() and accessing elements using next().

Iterator<String> it = [Link]();
while([Link]()) {
[Link]([Link]());
}

This approach works uniformly across all collection classes.

ListIterator Interface
ListIterator extends Iterator and provides additional capabilities. It is available only for
collections that implement the List interface.

ListIterator supports bidirectional traversal, element modification, and index-based access.

Features of ListIterator
 Allows forward and backward traversal
 Supports element insertion and replacement
 Provides index information
 More powerful than Iterator

ListIterator Methods
hasNext() and next()
Used for forward traversal.

hasPrevious() and previous()

Used for backward traversal.

nextIndex()
Returns the index of the next element.

previousIndex()
Returns the index of the previous element.

add(E obj)
Inserts an element into the list before the next element.

remove()
Removes the current element. Throws IllegalStateException if used incorrectly.

set(E obj)
Replaces the last accessed element with a new value.

EnumSet Overview
EnumSet is a specialized Set implementation designed exclusively for enum types. It is highly
efficient and internally uses bit vectors.
Commonly used factory methods include:

 allOf() to include all enum constants

 noneOf() to create an empty EnumSet
 of() to include specific enum values
 range() to include a range of enum constants
 copyOf() and complementOf() for set operations

EnumSet is faster and more memory-efficient than general-purpose Set implementations when
working with enums.

Important Exam Points

 Iterator provides forward-only traversal
 ListIterator supports bidirectional traversal
 Removal using iterator is optional
 Iterator works with all collections
 ListIterator works only with lists
 EnumSet is designed specifically for enum types

Accessing a Collection via an Iterator

• In Java, collections store multiple elements and often need to be accessed one by one
• An iterator is an object used to traverse through the elements of a collection sequentially
• The iterator hides the internal structure of the collection and provides a standard way to access
elements
• Java provides two main interfaces for this purpose: Iterator and ListIterator

Iterator Interface

• The Iterator interface allows forward-only traversal of a collection

• It is a generic interface where E represents the type of elements being iterated
• Every collection class provides an iterator() method
• The iterator returned always points to the start of the collection
• It supports element access and optional removal operations
• If the collection is read-only, calling remove() throws UnsupportedOperationException

Important Iterator methods

• hasNext() checks whether more elements are available

• next() returns the next element and moves the cursor forward
• remove() removes the last element returned by next()
• Calling next() when no element exists throws NoSuchElementException
• Calling remove() without calling next() first throws IllegalStateException

ListIterator Interface

• ListIterator extends the Iterator interface

• It is available only for collections that implement the List interface
• It allows traversal in both forward and backward directions
• It allows modification of elements while iterating

Additional capabilities of ListIterator

• Adding new elements at the current position

• Replacing existing elements
• Traversing the list in reverse order
• Obtaining index positions during traversal

Important ListIterator methods

• hasNext() checks for next element

• next() returns the next element
• hasPrevious() checks for previous element
• previous() returns the previous element
• add(E obj) inserts an element at the current position
• set(E obj) replaces the current element
• remove() deletes the current element
• nextIndex() returns the index of the next element
• previousIndex() returns the index of the previous element

Steps to Use an Iterator

• Obtain an iterator using the iterator() method of the collection

• Use hasNext() to check for remaining elements
• Use next() to retrieve elements one at a time
• Continue until all elements are processed

Program Using Iterator and ListIterator

// Demonstrate iterators
import [Link].*;

class IteratorDemo {
public static void main(String[] args) {

// Create an ArrayList
ArrayList<String> al = new ArrayList<String>();

// Add elements to the ArrayList

[Link]("C");
[Link]("A");
[Link]("E");
[Link]("B");
[Link]("D");
[Link]("F");

// Use Iterator to display elements

[Link]("Original contents of al: ");
Iterator<String> itr = [Link]();
while ([Link]()) {
String element = [Link]();
[Link](element + " ");
}
[Link]();

// Use ListIterator to modify elements

ListIterator<String> litr = [Link]();
while ([Link]()) {
String element = [Link]();
[Link](element + "+");
}

// Display modified list

[Link]("Modified contents of al: ");
itr = [Link]();
while ([Link]()) {
String element = [Link]();
[Link](element + " ");
}
[Link]();

// Display list in reverse order

[Link]("Modified list backwards: ");
while ([Link]()) {
String element = [Link]();
[Link](element + " ");
}
 [Link]();
}
}

Explanation of the Program

• An ArrayList is created and populated with string elements

• An Iterator is used to display the original contents of the list
• A ListIterator is used to modify each element by appending a plus symbol
• The modified list is displayed again using an Iterator
• The same ListIterator is used to traverse the list in reverse order
• Reverse traversal works because the iterator is positioned at the end after forward traversal

Output of the Program

Original contents of al: C A E B D F
Modified contents of al: C+ A+ E+ B+ D+ F+
Modified list backwards: F+ D+ B+ E+ A+ C+

For-Each Loop as an Alternative to Iterator

• When modification or reverse traversal is not required, the for-each loop is simpler
• All collection classes implement the Iterable interface
• The for-each loop automatically uses an iterator internally
• It improves readability and reduces code complexity

Program Using For-Each Loop

// Use the for-each loop to cycle through a collection
import [Link].*;

class ForEachDemo {
public static void main(String[] args) {

// Create an ArrayList of integers

ArrayList<Integer> vals = new ArrayList<Integer>();

// Add elements
[Link](1);
[Link](2);
[Link](3);
 [Link](4);
[Link](5);

// Display elements
[Link]("Contents of vals: ");
for (int v : vals)
[Link](v + " ");
[Link]();

// Calculate sum
int sum = 0;
for (int v : vals)
sum += v;

[Link]("Sum of values: " + sum);

}
}

Key Points Summary

• Iterator allows forward traversal of collections

• ListIterator supports bidirectional traversal and modification
• Iterator is available for all collections
• ListIterator is available only for lists
• For-each loop is best for simple read-only traversal

IllegalArgumentException Invalid argument

Working with Maps

What is a Map?

 A Map stores key–value pairs.

 Keys must be unique, but values can be duplicated.

 Keys and values are objects.

 Some map implementations allow null keys/values, others do not.

 Map does not implement Collection or Iterable, but we can iterate using:

o entrySet()

o keySet()
 o values()

Map Interfaces
Interface Description
Map Maps unique keys to values
[Link] Represents a key–value pair
SortedMap Keys stored in ascending order
NavigableMap Supports closest-match searches

Important Map Methods

Method Purpose
put(K,V) Inserts key/value
get(K) Returns value of key
remove(K) Deletes entry
containsKey(K) Checks key
containsValue(V) Checks value
keySet() Returns set of keys
values() Returns collection of values
entrySet() Returns set of key-value pairs
isEmpty() Checks map empty
clear() Removes all entries

Simple Map Example Program

import [Link].*;

class MapDemo {
public static void main(String[] args) {

Map<String, Integer> map = new HashMap<>();

[Link]("A", 10);
[Link]("B", 20);
[Link]("C", 30);

// Access value
[Link]("Value of B: " + [Link]("B"));

// Iterate using entrySet

for([Link]<String,Integer> e : [Link]()) {
[Link]([Link]() + " = " + [Link]());
}
}
}
Very Important Exam Points
 Map stores associations, not sequential elements.

 Keys must be unique.

 Iteration is done through collection views (entrySet, keySet, values).

 Common implementations:

o HashMap – fastest

o LinkedHashMap – insertion order maintained

o TreeMap – sorted keys

1. SortedMap Interface
 SortedMap extends Map.
 It stores entries in ascending order of keys.
 Ordering can be:
o Natural ordering (default)
o Comparator-based ordering

interface SortedMap<K,V>

Important Methods
Method Description
Comparator comparator()
Returns comparator used for sorting (null if natural
order).
K firstKey() Returns first (smallest) key.
K lastKey() Returns last (largest) key.
SortedMap headMap(K end) Returns entries with keys less than end.
SortedMap tailMap(K start) Returns entries with keys greater than or equal to
 Method Description
start.
SortedMap subMap(K start, K
end) Returns entries start ≤ key < end.
Important:
Submaps are backed by the original map, so changes affect both.

2. NavigableMap Interface
 NavigableMap extends SortedMap.
 Provides methods to search closest matching keys (greater, smaller, equal).

interface NavigableMap<K,V>
Important Methods
Method Description
ceilingKey(k) Smallest key ≥ k
floorKey(k) Largest key ≤ k
higherKey(k) Smallest key > k
lowerKey(k) Largest key < k
firstEntry() Entry with smallest key
lastEntry() Entry with largest key
descendingMap() Reverse order map
descendingKeySet() Reverse order keys

3. [Link] Interface
 Represents one key-value pair inside a map.

interface [Link]<K,V>

Important Methods
Method Description
K getKey() Returns key
V getValue() Returns value
V setValue(V v) Updates value

Static Methods
  comparingByKey() → comparator based on keys
 comparingByValue() → comparator based on values
 copyOf() → returns unmodifiable copy

Very Important Concept (Exam Favorite)

Hierarchy

Map
↓
SortedMap
↓
NavigableMap
Example Implementations:

 TreeMap → implements NavigableMap

 HashMap → implements Map
 LinkedHashMap → implements Map

One-line Exam Difference (Very Important)

 Map → stores key-value pairs (no ordering)
 SortedMap → keys sorted
 NavigableMap → sorted + nearest-key searching methods

Map Classes in Java

Class Description
AbstractMap Provides partial implementation of Map
HashMap Uses hash table for storage
TreeMap Uses tree structure (sorted keys)
LinkedHashMap Maintains insertion order
WeakHashMap Uses weak keys (can be garbage collected)
EnumMap Used when keys are enum type
IdentityHashMap Uses reference equality (==) instead of equals()
Important:
AbstractMap is the superclass for most map implementations.

HashMap Class
  Extends AbstractMap
 Implements Map
 Stores elements using hash table
 No ordering guarantee
 Allows one null key and multiple null values
 Provides constant-time performance for put() and get()

HashMap Declaration
class HashMap<K,V>

Constructors
Constructor Description
HashMap() Default capacity (16)
HashMap(Map m) Initializes with elements of another map
HashMap(int capacity) Sets initial capacity
HashMap(int capacity, float loadFactor) Sets capacity and load factor
Default load factor = 0.75

Important Points
 Order of elements is not guaranteed
 Iterator order may change
 Very fast retrieval using hashing

Example Program
import [Link].*;

class HashMapDemo {
public static void main(String[] args) {

HashMap<String, Double> hm = new HashMap<>();

[Link]("John Doe", 3434.34);

[Link]("Tom Smith", 123.22);
[Link]("Jane Baker", 1378.00);

Set<[Link]<String, Double>> set = [Link]();

 for([Link]<String, Double> me : set) {
[Link]([Link]()+" : "+[Link]());
}

double balance = [Link]("John Doe");

[Link]("John Doe", balance + 1000);

[Link]("New Balance: "+[Link]("John Doe"));

}
}

Very Important 2-Mark / 5-Mark Points

 HashMap uses hash table
 Order not maintained
 Allows null key
 Average time complexity O(1)

Here is the exam-ready explanation of TreeMap.

TreeMap Class
 TreeMap extends AbstractMap
 Implements NavigableMap
 Stores elements in a tree structure (Red-Black Tree)
 Entries are automatically sorted in ascending order of keys
 Provides fast retrieval and searching operations

class TreeMap<K,V>

Important Characteristics
 Maintains sorted order of keys
 Does not allow null key
 Slower than HashMap (because of tree operations)
 Implements SortedMap + NavigableMap features
 Default sorting = natural ordering
 Custom sorting possible using Comparator

Constructors
 Constructor Description
TreeMap() Empty map with natural ordering
TreeMap(Comparator comp) Sorted using comparator
TreeMap(Map m) Initializes from another map
TreeMap(SortedMap sm) Initializes with same sorting order

Example Program
import [Link].*;

class TreeMapDemo {
public static void main(String[] args) {

TreeMap<String, Double> tm = new TreeMap<>();

[Link]("John Doe", 3434.34);

[Link]("Tom Smith", 123.22);
[Link]("Jane Baker", 1378.00);

for([Link]<String, Double> me : [Link]()) {

[Link]([Link]()+" : "+[Link]());
}

double balance = [Link]("John Doe");

[Link]("John Doe", balance + 1000);

[Link]("New balance: "+[Link]("John Doe"));

}
}

Output Concept
Keys will appear sorted automatically, for example:

Jane Baker : 1378.0

John Doe : 3434.34
Tom Smith : 123.22

LinkedHashMap Class
 LinkedHashMap extends HashMap
 Maintains a linked list of entries
 Elements are returned in insertion order
 Can also maintain access order (order of last access)

class LinkedHashMap<K,V>
Important Characteristics
 Same hashing mechanism as HashMap
 Maintains predictable iteration order
 Slightly slower than HashMap due to linked list maintenance
 Allows one null key and multiple null values

Constructors
Constructor Description
LinkedHashMap() Default map
LinkedHashMap(Map m) Initializes from another map
LinkedHashMap(int capacity) Sets capacity
LinkedHashMap(int capacity, float loadFactor) Sets capacity and load factor
LinkedHashMap(int capacity, float loadFactor, Specifies insertion or access
boolean order) order
 order = false → insertion order (default)
 order = true → access order

Special Method
protected boolean removeEldestEntry([Link]<K,V> e)
 Called automatically when put() or putAll() executes.
 Used to remove the oldest entry (useful for cache implementations).
 Return true → remove oldest entry
 Return false → keep entry

Example Program
import [Link].*;

class LinkedHashMapDemo {
public static void main(String[] args) {

LinkedHashMap<Integer,String> map =
new LinkedHashMap<>();

[Link](3,"C");
[Link](1,"A");
[Link](2,"B");

for(Integer key : [Link]()) {

 [Link](key + " " + [Link](key));
}
}
}
Output (Insertion Order):

3 C
1 A
2 B

Very Important Comparison Shortcut

Feature HashMap LinkedHashMap TreeMap
Ordering No order Insertion / access order Sorted order
Structure Hash table Hash table + linked list Tree
Speed Fastest Slightly slower Slower
Null key Allowed Allowed Not allowed

Legacy Classes and Interfaces in Java

Before the Collections Framework (J2SE 1.2), Java used some older classes for storing objects.
These are called Legacy Classes.

Legacy Classes
 Dictionary
 Hashtable
 Properties
 Stack
 Vector

Legacy Interface
 Enumeration

Important Point

 Legacy classes are synchronized by default

 Modern collection classes (ArrayList, HashMap, etc.) are not synchronized
 Modern classes are generally preferred

Enumeration Interface
  Old interface used to traverse elements one by one
 Replaced by Iterator
 Still used in some legacy classes like Vector and Hashtable

interface Enumeration<E>

Methods of Enumeration
Method Description
boolean hasMoreElements() Returns true if more elements exist
E nextElement() Returns next element
Iterator<E> asIterator() Converts enumeration to iterator (added in JDK 9)

Example
import [Link].*;

class Demo {
public static void main(String[] args) {

Vector<Integer> v = new Vector<>();

[Link](10);
[Link](20);
[Link](30);

Enumeration<Integer> e = [Link]();

while([Link]()) {
[Link]([Link]());
}
}
}

Very Important Exam Points

 Enumeration → legacy traversal interface
 Replaced by Iterator
 Used mainly with Vector, Hashtable, Properties
 Methods: hasMoreElements(), nextElement()

Vector Class
 Vector is a legacy class that implements a dynamic array.
 It extends AbstractList and implements List and Iterable.
 It is synchronized (thread-safe).
 Similar to ArrayList, but slower due to synchronization.
  Supports generics (since JDK 5).

class Vector<E>

Important Features
 Default initial capacity = 10
 Capacity grows automatically when full
 If increment is specified →
New capacity = Old capacity + increment
 If increment not specified →
capacity doubles
 Can be iterated using for-each loop

Constructors
Constructor Description
Vector() Default capacity 10
Vector(int size) Initial capacity specified
Vector(int size, int incr) Capacity + increment
Vector(Collection c) Initializes from collection

Important Legacy Methods

Method Purpose
addElement(e) Add element
elementAt(i) Get element at index
firstElement() First element
lastElement() Last element
removeElement(e) Remove element
removeElementAt(i) Remove at index
capacity() Returns capacity
setSize(n) Changes size
trimToSize() Capacity = size

Vector vs ArrayList (Very Important)

Feature Vector ArrayList
Synchronization Yes No
Performance Slower Faster
 Feature Vector ArrayList
Legacy class Yes No
Recommended Rarely used Preferred

5-Mark Ready Definition

Vector is a synchronized dynamic array class in Java that automatically increases its
capacity when needed and supports both legacy and collection methods.

Java Program using Vector

import [Link].*;

class VectorProgram {
public static void main(String[] args) {

// Creating a Vector
Vector<Integer> v = new Vector<Integer>();

// Adding elements
[Link](10);
[Link](20);
[Link](30);
[Link](40);

// Displaying elements
[Link]("Vector elements: " + v);

// Accessing elements
[Link]("First element: " + [Link]());
[Link]("Last element: " + [Link]());

// Checking element
if([Link](20))
[Link]("Vector contains 20");

// Removing element
[Link](2);
[Link]("After removal: " + v);

// Traversing using Enumeration

Enumeration<Integer> e = [Link]();
[Link]("Using Enumeration:");
while([Link]()) {
[Link]([Link]() + " ");
}
}
}
Sample Output
Vector elements: [10, 20, 30, 40]
First element: 10
Last element: 40
Vector contains 20
After removal: [10, 20, 40]
Using Enumeration:
10 20 40
If you want, I can next give a very small 5-mark exam-ready Vector program (capacity +
increment example) which is frequently asked in VTU exams.

Stack (Java) — Notes with Program

Notes

 Stack is a subclass of Vector that implements LIFO (Last-In First-Out).

 Declared as:
 class Stack<E>
where E is the type of elements stored.

 Stack inherits all Vector methods and adds stack-specific operations.

Important Methods

 push(E element) – adds element to top

 pop() – removes and returns top element
 peek() – returns top element without removing
 empty() – checks whether stack is empty
 search(Object element) – returns position from top
 Calling pop() or peek() on an empty stack throws EmptyStackException.

Stack Program
import [Link].*;

public class StackDemo {

public static void main(String[] args) {

Stack<Integer> st = new Stack<>();

// push elements
[Link](100);
[Link](200);
[Link](300);

[Link]("Stack: " + st);

// peek
 [Link]("Top element: " + [Link]());

// pop
[Link]("Removed element: " + [Link]());
[Link]("Stack after pop: " + st);

// check empty
[Link]("Is stack empty? " + [Link]());

// search element
[Link]("Position of 100 from top: " + [Link](100));
}
}
Output (Example)
Stack: [100, 200, 300]
Top element: 300
Removed element: 300
Stack after pop: [100, 200]
Is stack empty? false
Position of 100 from top: 2

Dictionary — Notes
 Dictionary is an abstract class that stores key/value pairs similar to Map.
 Declared as:
 class Dictionary<K,V>
where
K → key type
V → value type

 It is considered obsolete because it is replaced by the Map interface.

 Important methods:
o put(K key, V value) – insert key/value pair
o get(Object key) – retrieve value using key
o remove(Object key) – delete key/value pair
o keys() – returns enumeration of keys
o elements() – returns enumeration of values
o size() – number of entries
o isEmpty() – checks whether dictionary is empty

Hashtable — Notes
 Hashtable is a concrete subclass of Dictionary and also implements Map.
 Stores data using hash table (key/value pairs).
 Synchronized (thread-safe).
 Null keys and null values are not allowed.
 Declared as:
  class Hashtable<K,V>
 Common methods:
o put(K key, V value)
o get(Object key)
o remove(Object key)
o containsKey(Object key)
o containsValue(Object value)
o size()
o isEmpty()

Hashtable Program
Hashtable Example – Clean Program
import [Link].*;

class HTDemo {
public static void main(String[] args) {

Hashtable<String, Double> balance =

new Hashtable<>();

Enumeration<String> names;
String str;
double bal;

// insert entries
[Link]("John Doe", 3434.34);
[Link]("Tom Smith", 123.22);
[Link]("Jane Baker", 1378.00);
[Link]("Todd Hall", 99.22);
[Link]("Ralph Smith", -19.08);

// show all balances

names = [Link]();
while([Link]()) {
str = [Link]();
[Link](str + ": " + [Link](str));
}

[Link]();

// Deposit 1000 into John Doe account

bal = [Link]("John Doe");
[Link]("John Doe", bal + 1000);

[Link]("John Doe's new balance: "

+ [Link]("John Doe"));
}
}
Sample Output
Todd Hall: 99.22
Ralph Smith: -19.08
John Doe: 3434.34
Jane Baker: 1378.0
Tom Smith: 123.22

John Doe's new balance: 4434.34

Important Exam Notes (Hashtable)

 Stores key–value pairs using hashing.

 Synchronized (thread-safe).

 Null keys and null values are not allowed.

 Implements Map interface and extends Dictionary.

 Keys must properly implement hashCode() and equals().

Properties Class – Short Notes

 Properties is a subclass of Hashtable.

 Used to store String key – String value pairs.

 Commonly used for configuration files and system properties

([Link]()).

 Supports default property values.

 Not generic (keys and values are Strings).

 Can load properties from files and store them to files or XML.

Important Methods

 setProperty(String key, String value) – adds property

 getProperty(String key) – returns value

 getProperty(String key, String default) – returns default if key not found

 load() – reads properties from file/stream

 store() – writes properties to file

  stringPropertyNames() – returns keys set

Properties Example Program

import [Link].*;

class PropDemo {
public static void main(String[] args) {

Properties capitals = new Properties();

[Link]("Illinois", "Springfield");
[Link]("Missouri", "Jefferson City");
[Link]("Washington", "Olympia");
[Link]("California", "Sacramento");
[Link]("Indiana", "Indianapolis");

// display properties
Set<String> states = [Link]();

for(String state : states) {

[Link]("Capital of " + state +
" is " + [Link](state));
}

// default value example

String str = [Link]("Florida", "Not Found");
[Link]("\nCapital of Florida is " + str);
}
}

Output (Example)
Capital of Missouri is Jefferson City
Capital of Illinois is Springfield
Capital of Indiana is Indianapolis
Capital of California is Sacramento
Capital of Washington is Olympia

Capital of Florida is Not Found