Chapter 6- Java Collection Framework

Sangeeta Dey (Ph.D.)

Department of Software and Computer Engineering
Ajou University

1
Motivation (Problem with arrays)
• Arrays:
➢ Arrays in Java are fundamental data structures used to store multiple values of the same
data type in a single variable.
➢ But are they flexible enough? (e.g. Can we change size?)

public class ArrayExample {

public static void main(String[] args) {
String[] names = new String[3];
names[0] = "Alice";
names[1] = "Bob";
names[2] = "Charlie";
names[3] = "David"; //ArrayIndexOutOfBoundsException
}
}

2
Motivation (Problem with arrays)
Problem Explanation Example
Once an array is created, its size cannot
int[] nums = new int[3]; → we can’t
Fixed Size be changed. We must know the size in a
add a 4th element.
dvance.
No built-in way to add, remove, or search
elements efficiently. Only a few methods To remove an element, we need to
Lack of Built-in Methods
in Arrays class. Mostly, we must write manually shift elements.
our own logic.
Cannot Store Heterogeneous Arrays can only store one type of data
String[] names can’t store an Integer.
Objects (primitive or object).

If we create a large array but do not use int[] data = new int[1000]; but we
Poor Memory Efficiency
it, the unused elements waste memory. only use 10 elements. (waste)

Resizing means creating a new array and arr = [Link](arr, [Link] *

Difficult to Grow Dynamically
copying elements manually. 2); (tedious and error-prone)

3
Motivation (Problem with arrays)
• Why Collection Framework?

To solve these problems, Java introduced the Collection Framework, a set of ready-made
data structures that are:

• Dynamic — Can grow or shrink as needed.

• Flexible — Can store objects of any type (using Generics).
• Powerful — Come with built-in methods for adding, removing, searching, sorting, etc.
• Unified — Provide a consistent architecture (common interfaces like List, Set, Map).

Formal Definition:
• A collection is an object that represents a group of objects.
• A collections framework is a unified architecture for representing and manipulating
collections, enabling collections to be manipulated independently of implementation details.

4
Motivation (Problem with arrays)
• Primary advantages of using a framework?

✓ Reduces programming effort by providing data structures and algorithms so we don't have
to write them yourself.
✓ Increases performance by providing high-performance implementations of data structures
and algorithms. Because the various implementations of each interface are interchangeable,
programs can be tuned by switching implementations.
✓ Provides interoperability between unrelated APIs by establishing a common language to
pass collections back and forth.
✓ Reduces the effort required to learn APIs by requiring you to learn multiple ad hoc
collection APIs.
✓ Reduces the effort required to design and implement APIs by not requiring you to produce
ad hoc collections APIs.
✓ Fosters software reuse by providing a standard interface for collections and algorithms with
which to manipulate them.

[Link]
[Link]#:~:text=The%20Java%20platform%20includes%20a,with%20which%20to%20manipulate%20them.
5
Motivation (Using ArrayList instead of Array)
import [Link];

public class CollectionExample {

public static void main(String[] args) {
ArrayList<String> names = new ArrayList<>();
[Link]("Alice");
[Link]("Bob");
[Link]("Charlie");
[Link]("David"); // No problem!

[Link]("Names: " + names);

[Link]("Bob");
[Link]("After removal: " + names);
}
}

Output:
Names: [Alice, Bob, Charlie, David]
After removal: [Alice, Charlie, David]
6
Motivation
!! Do not confuse with Arrays (data structure), Arrays Utility Class and ArrayList<> !!

1. Arrays:
An array itself in Java is a low-level fixed-size container —
it’s part of the language, not part of the Collections Framework.

int[] nums = {1, 2, 3};

This array:
• Has fixed length.
• Stores only one type of data (int).
• Does not have any methods for adding, removing, etc.
• We can only access or modify elements by index:

nums[1] = 5;
[Link]([Link]); // ok
// But we can’t do [Link](4);

So, the array itself has very limited functionality.

7
Motivation
!! Do not confuse with Arrays (data structure), Arrays Utility Class and ArrayList<> !!

2. The Arrays Class:

[Link] is a helper class that provides static utility methods to work with arrays.

import [Link];
public class Example {
public static void main(String[] args) {
int[] nums = {3, 1, 2};

[Link](nums); // sort array

[Link]([Link](nums)); // print contents
[Link]([Link](nums, 2)); // search
int[] copy = [Link](nums, 5); // resize (manually)
[Link]([Link](copy));
[Link](3);//Not possible
}
}
So, the Arrays utility class helps but still has some limitations.
8
Motivation
!! Do not confuse with Arrays (data structure), Arrays Utility Class and ArrayList<> !!

3. The ArrayList<>:
[Link] is a helper class that provides static utility methods to work with arrays.
import [Link];
import [Link];
public class Example {
public static void main(String[] args) {

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

[Link](3);
[Link](1);
[Link](2);
[Link](list); // ok
[Link](4); // dynamic
[Link]([Link]());
} Output: [1, 2, 3, 4]
}
So, the ArrayList<> makes arrays dynamic, flexible and the most usable.
9
Motivation
!! Do not confuse with Arrays (data structure), Arrays Utility Class and ArrayList<> !!

Feature Arrays (structure) Arrays class (utility) Collections Framework

Type Built-in language feature Helper class Framework of classes & interfaces
Size Fixed Fixed Dynamic
Static methods like sort(),
Methods Very few (length) Rich set (add, remove, iterator, etc.)
copyOf()
Data Primitive or object Works on arrays Objects only
Flexibility Low Slightly improved Very high

10
Motivation
Food for thought!!

Once again, summarize the difference between int [] and ArrayList<Integer> !

11
Overview of the Java Collection Framework
• Java collection framework is not all just about ArrayList.
• It has more interfaces, implementations, and algorithms.

•Map is not a child of Collection (it’s

a separate hierarchy).
•Iterable is at the top, so anything in
the collection can be iterated (looped)
using a for-each loop.

[Link] 12
Overview of the Java Collection Framework

public interface Iterable<T> T - the type of elements returned by the iterator

public interface Collection<E> extends Iterable<E> E - the type of elements in this list

public interface SequencedCollection<E> extends Collection<E>

public interface List<E> extends SequencedCollection<E>

public class ArrayList<E> extends AbstractList<E>

implements List<E>, RandomAccess, Cloneable, Serializable

Interface Description Common Implementations (Classes)

List Ordered collection (allows duplicates, index-based). ArrayList, LinkedList, Vector
Set Unordered collection (no duplicates). HashSet, LinkedHashSet, TreeSet
FIFO structure, used for holding elements before
Queue PriorityQueue, ArrayDeque
processing.
Map Stores key–value pairs (no duplicate keys). HashMap, TreeMap, LinkedHashMap
13
Java List Interface
• The List interface is part of the Java Collections Framework and represents an ordered collection of elements.
• We can access elements by their index, add duplicates, and maintain the insertion order.
• Since List is an interface, we cannot create a List object directly.
• Instead, we use a class that implements the List interface, such as:
✓ ArrayList - like a resizable array with fast random access
✓ LinkedList - like a train of cars you can easily attach or remove

List<String> myList = new List<>(); //Not possible

List<String> myList = new ArrayList<>(); //Possible

List=Interface Type (Reference)

ArrayList= Concrete class that implements List
Meaning: I want a list-like structure (as per the List interface), but I’ll use ArrayList’s implementation.”

14
Java List Interface
Most commonly used list methods

Method Description
add() Adds an element to the end of the list public interface List<E>
get() extends Collection<E> {
Returns the element at the specified position
boolean add(E e);
set() Replaces the element at the specified position E get(int index);
E remove(int index);
remove() Removes the element at the specified position int size();
size() Returns the number of elements in the list // ... many more
}

✓ All these methods are declared in the List interface as

abstract methods (i.e., methods without implementation).

✓ Any class that implements me must provide its own way to add,
For more details:
remove, and get elements [Link]
4/docs/api/[Link]/java/util/[Link]

15
Java ArrayList<>
• An ArrayList in Java is a resizable (or dynamic) array from the [Link] package that can grow or
shrink automatically as elements are added or removed, unlike regular arrays with a fixed size.

Simplified Hierarchy of ArrayList (Big Picture)

16
Java ArrayList<>
ArrayList Constructors
1. ArrayList()

Creates an empty ArrayList with default initial capacity.

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

2. ArrayList<Integer> arr = new ArrayList<>()

OR Creates an ArrayList initialized with elements from the specified collection.

ArrayList<String> arr = new ArrayList<>(collection);

3. ArrayList(int initialCapacity)

This constructor is used to build an array list with the initial capacity being specified.

ArrayList<Double> arr = new ArrayList<>(20);

17
Java ArrayList<>
import [Link].*;
class Example{

public static void main(String args[]){

// Creating an Array of string type
ArrayList<String> al = new ArrayList<>();

// 1. Adding elements to ArrayList at the end

[Link]("Tim");
[Link]("John");
[Link]("Original List : "+al);

// Adding Elements at the specific index

[Link](1, "Rose");
[Link]("After Adding element at index 1 : "+ al);

// 2. Removing Element using index

[Link](0);
[Link]("Element removed from index 0 : "+ al);

// Removing Element using the value

[Link]("John");
[Link]("Element John removed : "+ al);
18
Java ArrayList<>

// 3. Updating value at index 0

[Link](0, "Jim");

[Link]("List after updation of value : "+al);

}
}

Entire Output:

19
Java ArrayList<> (Memory Allocation)

• Default capacity=10; (unless explicitly

specified)
• When capacity exceeds,
✓ Reassign new array objects
✓ With 50% increased size .

• After reassigning new array objects, old array

objects are marked for garbage collection.

[Link] 20
Questions
1. Which of the following statements about the Java Collection Framework is true?

A. It is a set of classes and interfaces for storing primitive data types.

B. It provides a unified architecture for storing and manipulating groups of objects.
C. It allows only fixed-size data structures.
D. It can store only elements of type String.

2. Which interface is the root of the Collection hierarchy in Java?

A. Iterable
B. Collection
C. List
D. Set

3. Arrays are part of the Java Collection Framework. (True/False)

21
Questions
4. Guess the output:

import [Link].*;
public class Main {
public static void main(String[] args) {
ArrayList<String> names = new ArrayList<>();
[Link]("A");
[Link]("B");
[Link](1, "C");
[Link](names);
}
}

5. What happens if you try to access an element at an invalid index in an ArrayList (e.g., index =
10 when size = 5)?
A. Returns null
B. Returns -1
C. Throws IndexOutOfBoundsException
D. Silently ignores the call
22
Wrapper Class (its use in Collections)
• Motivations :
✓ Java collections framework works on OBJECTS! Not on primitive datatypes.
✓ ArrayList<int> list = new ArrayList<int>();//Invalid
✓ int is a primitive datatype NOT an object.
✓ Similarly, we also need utility methods like parsing and comparisons.
✓ Consistency with object-oriented programming concept.

Therefore, we needed specific class for each primitive data type!

• Definition:
✓ A wrapper class is a class that encloses or ‘wraps’ primitive data type into an object.
✓ Each primitive data type has a wrapper class.
✓ Collections like ArrayList work with the wrapper class object rather than the primitive type.

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

//Valid: Integer is the wrapper class of int
23
Wrapper Class (its use in Collections)
All these wrapper classes are
List of wrapper classes present in the package [Link]

Primitive
Wrapper Class ArrayList<Integer> numbers = new ArrayList<Integer>();
Type
[Link](10);
byte Byte [Link](20);
short Short
Similarly,
int Integer
ArrayList<Double> list = new ArrayList<Double>();
long Long
float Float ArrayList<Float> list = new ArrayList<Float>();
double Double
LinkedList<Double> prices = new LinkedList<>();
char Character [Link](19.99); // double → Double
boolean Boolean [Link](5.75);

…and many more possibilities

24
Wrapper Class (its use in Collections)
• Utility Methods :

✓ Primitive types don’t have any built-in methods

[Link]() or [Link]()// invalid

✓ Wrapper classes provide useful utility methods for:

• Parsing: [Link]("123")
• Comparing: [Link](a, b)
• Converting: [Link](3.14)

✓ So wrapper classes give object-oriented power + built-in utilities.

25
Wrapper Class (its use in Collections)
• Utility Methods :

1. Parsing(Example):

✓ Method→[Link](String s)
✓ Converts a numeric string into an int value.

String numberStr = "123";

int num = [Link](numberStr);
[Link](num + 10); // Output: 133

Usefulness: When we get numbers as user input (String) e.g., from Scanner or GUI
we can convert them to numeric types for calculations.

26
Wrapper Class (its use in Collections)
• Utility Methods :

3. Converting (Example: Primitive to String):

✓ Method→ [Link](double d)etc.

✓ Converts a numeric value into a String

double pi = 3.14;
String s = [Link](pi);
[Link](s + " is Pi");// Output: 3.14 is Pi)

Usefulness: When you need to display or store numbers as text (e.g., file or message)

27
Wrapper Class (its use in Collections)
• Autoboxing and Unboxing :
✓ Java provides automatic conversion between primitive type and their
corresponding wrapper objects.

• Autoboxing (Primitive to Object):

✓ Autoboxing is the automatic conversion of a primitive type
(like int, double, boolean, char) to its corresponding wrapper class
object (like Integer, Double, Boolean, Character).

int x = 5;
Integer y = x; // autoboxing → [Link](x)

28
Wrapper Class (its use in Collections)
• Unboxing (Primitive to Object):
✓ Unboxing is the automatic conversion a wrapper class object to its
corresponding primitive type.
✓ This conversion occurs when a wrapper object is used in a context that expects
a primitive value, such as:
• Assigning a wrapper object to a variable of its corresponding primitive type.

Integer iObject = new Integer(20);

int iPrimitive = iObject;
// Unboxing: Integer object is converted to an int
//(unboxing → [Link]())

29
Wrapper Class (its use in Collections)

Autoboxing

Unboxing

30
Wrapper Class (its use in Collections)
import [Link]; Take input: Scores of 5 mental coding tests
import [Link];

public class ExamScores {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);

// Create an ArrayList of Integer (wrapper class)

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

[Link]("Enter 5 exam scores:");

for (int i = 0; i < 5; i++) {
String input = [Link](); // Read as String
int score = [Link](input); // Parse String → int
using wrapper class
[Link](score); // Auto-box int → Integer
}
31
 Wrapper Class (its use in Collections)
[Link]("\n All Scores for mental coding: " + scores);

// Find the average score

int total = 0;
for (Integer s : scores) { // Auto-unboxing Integer → int
total += s;
}
double average = (double) total / [Link]();
[Link]("Average Score: " + average);

// Compare last two scores using wrapper compare method

if ([Link]() >= 2) {
int result = [Link]([Link]([Link]() - 2),
[Link]([Link]() - 1));
if (result < 0)
[Link]("Last score was higher than the second-last score.");
else if (result > 0)
[Link]("Second-last score was higher that the last score.");
else
[Link]("Two scores were equal.");
} 32
Wrapper Class (its use in Collections)

// Convert average to String for display or storage

String avgStr = [Link](average);
[Link]("Average (as text): " + avgStr);

[Link]();
}
}

33
ArrayList<> of Custom objects
Motivation (Why we need to store objects?)

✓ Real applications deal with entities like students, books, employees.

✓ Example:

ArrayList<String> names = new ArrayList<>();

[Link]("Alice");
[Link]("Bob");

✓ But, what if we want to add both name and student ID/Roll Number?
✓ Then, we need to introduce a custom class Student.

34
ArrayList<> of Custom objects
Step-1: Define a simple class
class Student {
String name;
int roll;

Student(String name, int roll) {

[Link] = name;
[Link] = roll;
}

public String toString() {

return roll + " - " + name;
}
}

35
ArrayList<> of Custom objects
Step-2: Create ArrayList<Student> and add objects
import [Link].*;

public class StudentListDemo {

public static void main(String[] args) {

ArrayList<Student> students = new ArrayList<>();

[Link](new Student("Alice", 101));
[Link](new Student("Bob", 102));
[Link](new Student("Charlie", 103));

for (Student s : students) {

[Link](s);
}
}
}

36
ArrayList<> of Custom objects
We may add more functionalities like search and access object fields

• Add Search Functionality

String searchName = "Bob";

for (Student s : students) {
if ([Link](searchName)) {
[Link]("Found: " + s);
}
}

• Modify Student Data

[Link](1).name = "Bobby";
[Link]("Updated: " + [Link](1));

37
ArrayList<> of Custom objects
What to do if Student attributes are Private?
• Add Getter/Setter Methods: • Access through those methods
class Student { for (Student s : students) {
private String name; [Link]("Name: "
private int roll; + [Link]());
}
public Student(String name, int roll) {
[Link] = name;
[Link] = roll;
}

public String getName() { return name; }

public int getRoll() { return roll; }

public String toString() {

return roll + " - " + name;
}
}
38
ArrayList<> of Custom objects

Why we made custom search functionality when ArrayList already has in-built search method?

ArrayList<String> names = new ArrayList<>();

[Link](”Alice");
[Link](”Kim");

[Link]([Link](”Alice")); // true
[Link]([Link](”Kim")); // 1

39
ArrayList<> of Custom objects
How about with custom objects?
class Student {
String name; • It uses the default implementation from
int id; Object, which compares memory addresses,
Student(String name, int id) { not field values.
[Link] = name; • So two different Student objects with the same
[Link] = id; data are considered not equal.
}
}

ArrayList<Student> students = new ArrayList<>();

[Link](new Student(”Alice", 101));
[Link](new Student(”Kim", 102));

[Link]([Link](new Student(”Alice", 101))); // false

40
Questions
• Which of the following statements about ArrayList is true?
A. It has a fixed size once created.
B. It allows duplicate elements.
C. It cannot store null values.
D. It only stores primitive data types.

• What does autoboxing mean in Java?

A. Automatically converting primitive → wrapper object
B. Automatically converting wrapper → primitive
C. Automatically sorting elements in an ArrayList
D. Automatically importing [Link] package

41
Questions
• What will the following print?
Integer x = [Link]("25");
[Link](x * 2);

• What will the following print?

ArrayList<Double> list = new ArrayList<>();

[Link](3.14);
[Link](2.71);
[Link]([Link]());

42
Java LinkedList<>
• Motivations :
✓ ArrayList is backed by a contiguous array, inserting or removing
elements in the middle requires shifting all subsequent elements.

ArrayList<String> list = new ArrayList<>(); • Works fine!

[Link]("A"); • But, internally, when "C" is
[Link]("B"); added at index 2:
[Link]("D"); o "D" is shifted one
position right.
// Insert element in the middle o Every subsequent
[Link](2, "C"); // Insert at index 2 element after index 2 is
[Link](list); shifted too (if list is
large, this is expensive).

43
Java LinkedList<>
• LinkedList (on the contrary) :
✓ internally maintains nodes connected by references (next and prev).
So, inserting or deleting in the middle just updates a few pointers -- no
shifting required!
LinkedList<String> list = new LinkedList<>(); • Works fine!
[Link]("A"); • internally:
[Link]("B"); o "C" is added by just
[Link]("D"); adjusting node references.
o No element shifting.
// Insert element in the middle
[Link](2, "C"); // Insert at index 2
[Link](list);
Each node in a linked list:
Reference to Data Reference to
previous the next node
node
44
Java LinkedList<>

Insertion in a LinkedList
(Internal Process)

[Link]
Java LinkedList<>

Deletion in a LinkedList
(Internal Process)

[Link]
Java LinkedList<>
List of features

Aspect Description
Implemented as a doubly linked list — each node has references to the
Implementation Type
previous and next nodes.
Found in [Link] package. Implements List, Deque, Queue, Cloneable,
Package & Interfaces
and Serializable interfaces.
Maintains insertion order of elements — elements are stored in the
Ordering
sequence they were added.
Duplicates Allows duplicate elements just like ArrayList.
Null Elements Can store null values.
Automatically grows or shrinks as elements are added or removed
Dynamic Size
(no fixed size).

47
Java LinkedList<>
List of features (Contd.)

Aspect Description
Slower random access (O(n)) since it must traverse nodes sequentially
Access Time
to reach an index.
Faster insertion and deletion (especially in the middle or ends) — no
Insertion/Deletion
shifting of elements like in ArrayList.
Traversal Can be traversed in both directions using an iterator (ListIterator).
Requires more memory than an ArrayList because each element stores
Memory Overhead
two extra references (to previous and next nodes).
Ideal for scenarios where frequent insertion/deletion occurs — e.g., q
Use Cases
ueues, stacks, playlists, undo/redo systems.
Slower random access (O(n)) since it must traverse nodes sequentially
Access Time
to reach an index.

48
Java LinkedList<> (Example of usage)
import [Link];

public class DoublyLinkedListExample { // Removing elements from both ends

public static void main(String[] args) { [Link]();
LinkedList<String> cities = new [Link]();
LinkedList<>();
[Link]("After
[Link]("Seoul"); removing: " + cities);
[Link]("Busan"); }
[Link]("Incheon"); }

[Link]("Cities: " + cities);

Output:
// Adding elements at both ends
[Link]("Daegu");
[Link]("Gwangju");

[Link]("After adding: " +

cities);
Refer to the following link for many more methods of LinkedList:
[Link]
49
Java LinkedList<> (Comparison)

Feature ArrayList LinkedList

Internal Structure Dynamic Array Doubly Linked List
Fast (O(1) time complexity) because Slow (O(n) time complexity) because it
Random Access
elements can be directly accessed using requires traversing the list from the start or
(get/set by index)
their index. end to reach the desired element.
Slow (O(n)) because elements after the
Insertion/Deletion insertion/deletion point need to be shifted Fast (O(1)) because it only involves updating
in middle which can involve creating a new array and the pointers of the neighbouring nodes.
copying elements.
Generally, more memory-efficient as it only Higher memory overhead because each
Memory Usage stores the elements themselves, with some node stores additional pointers (previous
overhead for array resizing. and next).

50
Java LinkedList<> (Comparison)
Choose ArrayList when:

• Frequent random access (getting or setting elements by index) is required.

• Fewer insertions or deletions are performed, especially in the middle of the list.

Choose LinkedList when:

• Frequent insertions or deletions are performed, especially at the beginning, end, or in the middle
of the list.
• Random access by index is not a primary operation.

51
Overview of the Java Collection Framework (Revisit)

[Link] 52
Java Queue Interface
• The Queue interface is part of the Java Collections Framework and belongs to [Link] package.
• We cannot access elements by their index
• We can add duplicates.
• Elements are processed in the order determined by the queue implementation (First In First Out or
FIFO for LinkedList, priority order for PriorityQueue).
• Since Queue is an interface, we cannot create a Queue object directly.
• Instead, we use a class that implements the Queue interface, such as:
✓ LinkedList
✓ PriorityQueue Isn’t
LinkedList a
✓ ArrayDeque
List?

53
Java Queue Interface (Simplified Hierarchy)

• It implements both List

interface and Deque interface.
• Deque interface extends
Queue interface.
• So, LinkedList can behave
like a List, a Queue and a
Dequeue.
• Depends on which reference
type is used to create the
LinkedList.

54
Java Queue Interface
• Working of Queue Data Structure:
✓ Elements are stored and accessed in First In, First Out manner.
✓ That is, elements are added from the behind and removed from the front.

• Working of Dequeue Data Structure:

✓ Unlike a queue, in a deque, we can insert and remove elements from both front
and rear.

Deque 55
Java Queue Interface
Most commonly used Queue methods
Returns special
Method Description Throws Exception?
value (null/false)?
Yes (if capacity is full —
boolean add(E e) Inserts the element into the queue. No
in bounded queues).
Inserts element, returns false if
boolean offer(E e) queue is full (preferred for capacity- No Yes (false if full)
restricted queues).
Removes and returns the head (front)
E remove() Yes (if queue is empty). No
of the queue.
Removes and returns the head of the
E poll() No Yes (null if empty)
queue.
Returns (but does not remove) the
E element() Yes (if queue is empty). No
head of the queue.
Returns (but does not remove) the
E peek() No Yes (null if empty)
head of the queue.

56
Java Deque Interface

Package: [Link] Can act as:

Interface: Deque<E> extends Queue<E> Queue → FIFO (First-In-First-Out)
Implementations: ArrayDeque, LinkedList Stack → LIFO (Last-In-First-Out)

Most commonly used Deque methods

Returns Special
Category Throws Exception Description
Value (null / false)
Add to Front addFirst(E e) offerFirst(E e) Inserts element at the front of the deque
Add to Rear addLast(E e) offerLast(E e) Inserts element at the end of the deque
Remove from Front removeFirst() pollFirst() Removes and returns element from front
Remove from Rear removeLast() pollLast() Removes and returns element from rear
Returns (without removing) element from
Access Front getFirst() peekFirst()
front
Returns (without removing) element from
Access Rear getLast() peekLast()
rear
57
Java Queue Interface (Example: Implemented by LinkedList)
import [Link].*;

public class QueueExample {

public static void main(String[] args) {
Queue<String> q = new LinkedList<>();

// Adding elements Partial Output:

[Link]("A");
[Link]("B");
[Link]("C");

[Link]("Queue: " + q);

// Access head element

[Link]("Head (peek): " + [Link]());// Returns A (does not remove)
[Link]("Head (element): " + [Link]()); // Also A

58
Java Queue Interface (Example: Implemented by LinkedList)
// Remove elements
[Link]("Removed (remove): " + [Link]()); // Removes A
[Link]("Removed (poll): " + [Link]()); // Removes B
[Link]("After removals: " + q);

// Poll on empty queue

[Link](); // removes C
[Link]("Poll empty queue: " + [Link]()); // null
}
}

Complete Output:

59
Java Deque Interface (Example: Implemented by LinkedList)
import [Link];
import [Link];

public class DequeLinkedListExample {

public static void main(String[] args) {

// Deque implementation using LinkedList

Deque<String> dq = new LinkedList<>();

// Add elements at both ends

[Link]("A"); // Front: A
[Link]("B"); // Rear: B
[Link]("C"); // Rear: C
[Link]("Start"); // Front: Start

[Link]("Deque after additions: " + dq);

Partial Output:

60
Java Deque Interface (Example: Implemented by
LinkedList)
// Peek elements
[Link]("Front element (peekFirst): " + [Link]());
[Link]("Rear element (peekLast): " + [Link]());

// Remove elements from both ends

[Link](); // Removes "Start" Complete Output:
[Link](); // Removes "C"

[Link]("Deque after removals: "

+ dq);
// Demonstrating stack-like behavior
[Link]("Top"); // same as addFirst
[Link]("After push: " + dq);

String popped = [Link](); // same as removeFirst

[Link]("Popped element: " + popped);
[Link]("Final Deque: " + dq);
}
} 61
Java Queue Interface
Do not get confused with LinkedList implementing so many difference interfaces: List, Queue, Deque!
Behavior of a LinkedList depends on the Declaration Type (Look for the reference variable)

Declaration Type Behavior Common Methods Usage Example

Sequential data where
List<String> l = add(), get(), set(),
Acts as List insertion/removal is
new LinkedList<>(); remove(int)
frequent
Queue<String> q =
Acts as Queue (FIFO) add(), remove(), peek() Processing tasks in order
new LinkedList<>();
addFirst(), addLast(),
Deque<String> d = Acts as Double-ended When we need stack +
removeFirst(),
new LinkedList<>(); Queue queue behavior
removeLast()

62
Java Queue Interface (Implemented by Class PriorityQueue)
• A PriorityQueue in Java is a queue where elements are ordered based on their priority, rather
than the order of insertion.

• By default, it uses natural ordering (min-heap), but a custom comparator can be used to define
different priorities.

• Elements are processed based on priority rather than insertion order.

• Supports standard queue operations like add(), poll(), and peek().

• Automatically grows as elements are added.

• Uses a heap data structure internally to ensure efficient insertion and removal of the highest-
priority element.

63
Java Queue Interface (Implemented by Class PriorityQueue)
import [Link];

public class Example1 {

public static void main(String[] args) {

PriorityQueue<Integer> pq = new PriorityQueue<>();

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

[Link]("PriorityQueue: " + pq);

[Link]("Peek (smallest): " + [Link]());

[Link]("Poll (remove smallest): " + [Link]());
[Link]("After poll: " + pq);
}
}
Homework: Think how you can reverse the order of the queue
64
Java Queue Interface (Implemented by Class PriorityQueue)
import [Link];

class Task implements Comparable<Task> {

String name;
int priority; // smaller = higher priority

Task(String name, int priority) {

[Link] = name;
[Link] = priority;
}

public int compareTo(Task other) {

return [Link] - [Link];
}

public String toString() {

return name + "(priority=" + priority + ")";
}
}

65
Java Queue Interface (Implemented by Class PriorityQueue)

public class Main {

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

[Link](new Task("Write report", 3));

[Link](new Task("Pay bills", 1));
[Link](new Task("Do homework", 2));

[Link]("Task Queue: " + pq);

[Link]("Next task: " + [Link]()); Do not expect a sorted queue
[Link]("Remaining: " + pq); (min to max OR max to min).
} Heap only makes sure that the
} next element is of most
priority.
Output:

66
Overview of the Java Collection Framework (Revisit)

[Link] 67
Java Set Interface
• The Set interface in Java is part of the Collections Framework and represents a collection of unique
elements.
• Implemented by the following classes:
Implementation Special Feature
HashSet Fastest, no order maintained.
LinkedHashSet Maintains insertion order.
TreeSet Automatically sorted (natural or custom comparator).

• Main Features
Feature Explanation
No duplicates allowed A Set automatically ignores duplicate elements.
Unordered collection Elements do not maintain insertion order (except LinkedHashSet).
Can contain null Most Set implementations allow null (HashSet allows one null).
Fast operations Hash-based sets offer near-constant time for add, remove, contains.

68
Java Set Interface

• Common Methods
Method Description Example
Adds an element if it is not already
boolean add(E e) [Link](10);
present. Returns true if added.
Removes an element if present. Returns
boolean remove(Object o) [Link](10);
true if removed.
boolean contains(Object o) Checks if an element exists in the set. [Link]("A");
Returns the number of elements in the
int size() [Link]();
set.
boolean isEmpty() Checks if the set is empty. [Link]();
void clear() Removes all elements from the set. [Link]();

69
Java Set Interface (Class HashSet)

import [Link];

public class HashSetExample {

public static void main(String[] args) {

// Creating a HashSet of Strings

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

// Adding elements
[Link]("Alice");
[Link]("Bob");
[Link]("Charlie");
[Link]("Alice"); // duplicate → ignored

// Printing the set

[Link]("HashSet elements: " + names);

70
Java Set Interface (Class HashSet)

// Checking if element exists

[Link]("Contains Bob? " + [Link]("Bob"));

// Removing element
[Link]("Charlie");

// Iterating using enhanced for loop

[Link]("After removing Charlie:");
for (String name : names) {
[Link](name);
}
} Output:
}

71
Java Set Interface (Class HashSet)
❖ When to use HashSet?
• When we want to avoid duplicates
• When ordering is not important
• When speed is required (fast lookup)

❖ Why Hashset is so fast in lookup (access an element)?

A hash table stores elements in buckets based on a hash code.
Therefore, the process to lookup is straight forward.

• Process during lookup:

✓ Compute hashCode()
✓ Go to the bucket
✓ Only compare objects using equals() inside that single bucket
✓ Since collisions are usually rare (good hashing), each bucket contains very few elements.
✓ So lookup is almost always constant time — O(1).

72
Questions
1. Which of the following allows duplicate elements?
(a) ArrayList
(b) LinkedList
(c) HashSet
(d) Both (a) and (b)

2. Which of the following maintains insertion order?

(a) HashSet
(b) ArrayList
(c) LinkedList
(d) Both (b) and (c)

3. True or False:
A LinkedList can be used as both a List and a Queue.

73
Questions

4. Which method retrieves but does NOT remove the head of

a Queue?
(a) remove()
(b) poll()
(c) peek()
(d) add()

5. Guess the output:

HashSet<Integer> set = new HashSet<>();

[Link](100);
[Link](200);
[Link](100);
[Link]([Link]());

74