Lecture 4. Collections. Generics

1.

Collections. Generics
www.andersenlab.com

2.

Agenda
• Introduction to Collections
• Core Interfaces and Classes
• Generics
2

3.

Introduction to Collections
What is the Java Collections?
The Java Collections Framework is a set of classes and
interfaces in Java that provides data structures and
algorithms to manipulate them. These collections are part of
the java.util package.
Key Interfaces:
The Java Collections Framework starts with the Iterable
interface. It helps you loop through collections with enhanced
for-loops. Important interfaces include:
Collection: The main interface for all collections (except
maps).
Interfaces: List, Set, Queue, and Deque.
Map: A separate interface for linking keys to values.
3

4.

List Interface
List is an ordered group of elements that allows duplicates.
Implementations:
ArrayList: is a resizable array implementation of the List
interface. Unlike regular arrays, its size can dynamically
grow or shrink as elements are added or removed.
LinkedList: is an implementation of the List and Deque
interfaces, using a doubly linked list as its underlying data
structure.
Vector: is a legacy collection class that implements the
List interface and is similar to ArrayList but thread-safe.
Stack: is a legacy class that extends Vector and
represents a Last-In-First-Out (LIFO) stack of objects.
4

5.

ArrayList and LinkedList
Key Characteristics of ArrayList
Dynamic Sizing: an ArrayList can grow or shrink
automatically based on the number of elements it
contains. When the ArrayList exceeds its capacity, it
creates a new array with a larger size (typically 1.5 times
the current size) and copies the elements to the new array.
Index-Based Access: ArrayList allows fast access to
elements by their index, as elements are stored
contiguously in memory. This makes retrieval operations
very efficient.
Resizable Array Implementation: Internally, ArrayList uses
a standard array. The array's capacity increases
dynamically.
Performance Characteristics of ArrayList
O(1) for getting elements by index, as it directly maps to
the underlying array position.
O(n) when inserting elements at a specific index, as it
requires shifting subsequent elements.
O(1) for removing the last element.
O(n) when removing elements at an arbitrary index, as it
involves shifting subsequent elements to fill the gap.
When the internal array reaches capacity, resizing involves
allocating a new array and copying elements, which incurs
a performance cost.
Key Characteristics of LinkedList
Structure: Each node in the LinkedList contains three
components:
✓ A Node
✓ Pointer to Previous Node
✓ Pointer to Next Node
Dynamic Sizing: The size of a LinkedList can grow or shrink
dynamically without the need for resizing operations.
Efficient Insertions and Deletions: Particularly efficient at the
beginning or end of the list.
Sequential Access: Traversing a LinkedList is slower than an
ArrayList because elements are not stored contiguously in
memory, and traversal requires moving through the nodes
sequentially.
Performance Characteristics of LinkedList
O(n): Accessing elements (requires traversal from head or
tail).
O(1): Adding elements at the head or tail (pointer updates).
O(n): Inserting elements in the middle (traversal required to
locate the insertion point).
O(1): Removing elements from the head or tail.
O(n): Removing elements in the middle (traversal required).
5

6.

Queue Interface and PriorityQueue
What is a Queue?
A Queue is a collection that follows the FIFO (First-In-First-Out) principle,
where elements are added at one end and removed from the other end. It is
a part of the java.util package and extends the Collection interface.
Queue Implementations
1.
2.
3.
PriorityQueue: Orders elements based on their natural ordering or a
custom comparator.
LinkedList: Implements List and Deque interfaces. Uses a doubly
linked list as its underlying data structure.
ArrayDeque: A resizable array-based implementation of the Deque
interface. Can function as a queue or a stack.
PriorityQueue
Key Characteristics
Uses a binary heap data structure to maintain the order of elements.
Ensures the highest-priority element is efficiently accessible.
Does not guarantee the order when iterating through elements.
Prohibits null elements, as null cannot be compared.
Performance
O(log n): Insert an element and reorder the heap to maintain priority.
O(log n): Remove the highest-priority element and reorder the heap.
O(1): Retrieve the highest-priority element without removing it.
6

7.

Set Interface
The Set interface in Java is a part of the Java Collections
Framework. It represents a collection that does not allow
duplicate elements. The Set interface is commonly used
when you need to ensure that no two elements in the
collection are the same.
Implementations:
• HashSet: Uses a hash table for storage. Offers constanttime performance for basic operations like add(), remove().
Does not maintain insertion order.
• LinkedHashSet: Extends HashSet. Maintains insertion
order and slower than HashSet due to additional overhead.
• TreeSet: Implements the NavigableSet interface and uses a
red-black tree. Elements are stored in sorted order.
7

8.

HashSet and TreeSet
Key Characteristics of HashSet
HashSet does not allow duplicate elements.
The order of elements is not guaranteed as it depends on
the hash code of the elements.
Basic operations like add(), remove(), and
contains() are performed in constant time (O(1)),
assuming a good hash function.
Allows one null element.
It uses a HashMap internally to store elements.
When you add an element to a HashSet, it calculates the
hash code of the element using the hashCode()
method.
The element is then stored in a bucket determined by
the hash code.
If multiple elements have the same hash code
(collision), they are stored in a linked list or tree structure
within the same bucket.
Load Factor: Determines when the HashSet will
increase its capacity. If the number of elements exceeds
(capacity * load factor), the HashSet resizes itself.
Key Characteristics of TreeSet
• The elements in a TreeSet are automatically sorted in their
natural order (ascending).
• You can provide a custom comparator for sorting.
• Similar to other Set implementations, it does not allow
duplicate elements.
• TreeSet does not allow null elements since it uses
comparisons for sorting, and null cannot be compared.
• Operations like add(), remove(), and contains() are performed
in O(log n) time because it is backed by a red-black tree.
• Slower than HashSet for basic operations due to the
tree structure.
• Have navigable method like floor(), ceiling()
8

9.

Map Interface
The Map interface in Java is part of the Java Collections Framework,
located in the java.util package. Unlike Set or List, a Map is a collection of
key-value pairs. Each key is unique, and each key maps to exactly one
value.
Key Characteristics of Map
• A Map stores data in the form of keys and values.
• Keys must be unique. If you attempt to insert a duplicate key, the old
value associated with the key will be replaced.
• Map is not a subtype of the Collection interface.
Implementations:
• HashMap: Backed by a hash table. Provides constant-time performance
(O(1)) for basic operations. Does not guarantee the order of keys.
• LinkedHashMap: Extends HashMap. Maintains the insertion order of
keys. Slightly slower than HashMap due to the overhead of maintaining
order.
• TreeMap: Implements the NavigableMap interface. Keys are sorted in
natural order or by a custom comparator. Slower (O(log n) operations)
but useful for ordered data.
9

10.

HashMap
Key Characteristics of HashMap:
• Elements in a HashMap are not stored in a specific order.
• Offers constant-time performance (O(1)) for basic operations like adding, retrieving, and removing elements, provided the
hash function is well-distributed.
• Supports one null key and multiple null values.
How it Works:
• Hashing: When you insert a key-value pair, the key is passed through a hash function to compute its hash code. The hash
code determines the index in the array where the key-value pair will be stored.
• Handling Collisions: Collision happens when two keys produce the same hash code and map to the same bucket. To
resolve collisions:
✓ Before Java 8: HashMap uses a linked list to store multiple entries in a single bucket.
✓ From Java 8: If the number of collisions in a bucket exceeds a threshold , the bucket switches from a linked list to a
binary tree for better performance.
• Retrieval: Compute the hash of the key. Find the bucket using the hash. Traverse the bucket to locate the key-value
pair.
• Load Factor and Resizing: HashMap dynamically resizes when it becomes too full. Load Factor determines how full
the HashMap can get before resizing. Default is 0.75 (75% full).
10

11.

TreeMap
Key Characteristics of TreeMap:
• Maintains ascending order of keys by default.
• Has a time complexity of O(log n) for operations due to the use of a red-black tree internally.
• Does not allow null keys but permits multiple null values.
How it Works:
A TreeMap is implemented using a Red-Black Tree, a type of self-balancing binary search tree.
• Red-Black Tree Properties: Nodes are either red or black. The root is always black. Red nodes cannot have red
children. All paths from a node to its descendant null nodes contain the same number of black nodes (black
height).
These properties ensure the tree remains balanced.
• Key Ordering: TreeMap orders entries by:
▪
Natural Order: Uses the Comparable interface if the key class implements it.
▪
Custom Order: Uses a Comparator provided at the time of TreeMap creation.
• Insertion: The key is compared with existing keys using the comparator or natural ordering. The pair is placed in
the
correct position to maintain the tree’s sorted order. If the tree’s balance is disturbed, rotations and color changes are
performed to restore balance.
• Retrieval: The key is compared with nodes in the tree. The search continues left or right until the key is found or the
search ends.
11

12.

Questions and Answers
12

13.

Introduction to Generics
What is the Generics?
Generics allow you to create classes, methods, and
interfaces that work with different types while still with
type safety at compile time. Instead of using Object and
Typecasting, generics allow you to specify a type
parameter.
Wildcard:
Wildcards provide flexibility when working with generics.
There three types of wildcard:
• Unbounded Wildcard (?)
Accepts any type.
• Upper Bounded Wildcard (? extends T)
Accepts type T or its subclasses.
• Lower Bounded Wildcard (? super T)
Accepts type T or its superclasses.
<?>
13

14.

Key Concepts
Type Erasure
Generics are implemented using type erasure, meaning type
information is removed at runtime for backward
compatibility with pre-Java 5 code.
Raw Types
Using generics without specifying a type is called a raw type.
Try to avoid it.
Generic Restrictions
• You can not create Objects of Generic Type
• You can not use Primitives
• You can not use Static Fields with Type Parameters
The type parameters naming conventions are important to
learn generics thoroughly. The common type parameters are
as follows:
• T – Type
• E – Element
• K – Key
• N – Number
• V – Value
Advantages of Generics
Code Reusability: You can write a method, class, or
interface once and use it with any type.
Type Safety: Generics ensure that errors are
detected at compile time rather than runtime,
promoting safer code.
No Need for Type Casting: The compiler
automatically handles casting, removing the need for
explicit type casting when retrieving data.
Disadvantages of Generics
Performance Overhead: Type erasure causes some
overhead as generic types are converted
to Object during runtime.
No Support for Primitive Types: Generics only work
with reference types, requiring the use of wrapper
classes like Integer or Double for primitives.
Limited Reflection: Type erasure limits how much
you can use reflection with generics since type
information is not available at runtime.
14

15.

Questions and Answers
15

16.

Homework
• Use Collections and Generics in your project

17.

THANK YOU
www.andersenlab.com