Object Oriented Programming
Data Structures in Java
Mayet Gizachew
College of Informatics
Department of Computer Science
May 30, 2025
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 1 / 27
outline
1 List
ArrayList
2 Set
HashSet
3 Map∥DictionaryofJava
HashMap
4 Queue
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 2 / 27
Data Structures in Java
Java provides a comprehensive Collections Framework for efficient data
management. Key categories:
Lists: Ordered, allow duplicates (e.g., ArrayList, LinkedList)
Sets: No duplicates, usually unordered (e.g., HashSet, TreeSet)
Queues/Deques: FIFO and double-ended queues (e.g.,
PriorityQueue, ArrayDeque)
Maps: Key-value pairs, keys unique (e.g., HashMap, TreeMap)
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 3 / 27
Java Collections Framework Hierarchy
Figure: Collections Framework
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 4 / 27
....
Interfaces: Collection is root interface for Lists, Sets, Queues.
Legacy classes: Vector, Stack, Hashtable are synchronized, older
implementations.
Thread Safety: Most classes are not synchronized; use wrappers or
concurrent collections.
Ordering:
ArrayList, LinkedList: insertion order
HashSet, HashMap: no guaranteed order
LinkedHashSet, LinkedHashMap: maintain insertion order
TreeSet, TreeMap: sorted order by natural/comparator
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 5 / 27
List Interface in Java
Package: [Link]
Superinterface: Collection<E>
Characteristics:
Maintains insertion order
Allows duplicate elements
Provides positional access via index
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 6 / 27
Implementing Classes
Common Implementations:
ArrayList
LinkedList
Vector
Stack
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 7 / 27
ArrayList Class
Description:
Resizable array implementation of List
Fast random access
Slower insertions/deletions in the middle
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 8 / 27
ArrayList Example
1 import java . util . ArrayList ;
2 import java . util . List ;
3
4 public class Example {
5 public static void main ( String [] args ) {
6 List < String > fruits = new ArrayList < >() ;
7 fruits . add ( " Apple " ) ;
8 fruits . add ( " Banana " ) ;
9 fruits . add ( " Orange " ) ;
0
1 System . out . println ( fruits . get (1) ) ; // Banana
2 fruits . set (1 , " Mango " ) ;
3 fruits . remove ( " Apple " ) ;
4
5 System . out . println ( fruits . size () ) ;
6
7 for ( String fruit : fruits ) {
8 System . out . println ( fruit ) ;
9 } } }
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 9 / 27
Common List Interface Methods
Method Description
add(E e) Appends element
add(int, E) Inserts at index
get(int) Gets element at index
set(int, E) Replaces element
remove(int) Removes element at index
remove(Object) Removes by value
size() Returns number of elements
isEmpty() Checks if list is empty
contains(Object) Checks presence
indexOf(Object) Returns index of element
clear() Removes all elements
toArray() Converts to array
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 10 / 27
List Implementations Comparison
Class Backed By Thread-safe Best Use Case
ArrayList Array No Fast access, frequent reads
LinkedList Linked list No Frequent inserts/deletes
Vector Array Yes Legacy synchronized code
Stack Array Yes LIFO stack operations
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 11 / 27
Set Interface in Java
Package: [Link]
Superinterface: Collection<E>
Characteristics:
Does not allow duplicate elements
No guaranteed order (unless using SortedSet or LinkedHashSet)
Allows at most one null element (in most implementations)
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 12 / 27
Implementing Classes
Common Implementations:
HashSet
LinkedHashSet
TreeSet
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 13 / 27
HashSet Class
Description:
Backed by a hash table
No guaranteed order of elements
Constant time for add, remove, and contains (on average)
Allows one null element
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 14 / 27
Set Example
1 import java . util . HashSet ;
2 import java . util . Set ;
3
4 public class Example {
5 public static void main ( String [] args ) {
6 Set < String > fruits = new HashSet < >() ;
7 fruits . add ( " Apple " ) ;
8 fruits . add ( " Banana " ) ;
9 fruits . add ( " Orange " ) ;
0 fruits . add ( " Apple " ) ; // Duplicate , ignored
1
2 fruits . remove ( " Banana " ) ;
3
4 System . out . println ( fruits . contains ( " Orange " ) ) ;
// true
5
6 for ( String fruit : fruits ) {
7 System . out . println ( fruit ) ;
8 } } }
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 15 / 27
Common Set Interface Methods
Method Description
add(E e) Adds element if not already present
remove(Object o) Removes specified element
contains(Object o) Checks if element exists
isEmpty() Returns true if set is empty
size() Returns the number of elements
clear() Removes all elements
iterator() Returns iterator over elements
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 16 / 27
Set Implementations Comparison
Class Order Nulls Best Use Case
HashSet Unordered One allowed Fast access, no duplicates
LinkedHashSet Insertion order One allowed Maintain order of insertion
TreeSet Sorted order No nulls Sorted unique elements
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 17 / 27
Map Interface in Java
Package: [Link]
Not a subtype of: Collection
Characteristics:
Stores key-value pairs
Keys must be unique
Values can be duplicated
Accessed via keys, not indices
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 18 / 27
Implementing Classes
Common Implementations:
HashMap
LinkedHashMap
TreeMap
Hashtable (Legacy)
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 19 / 27
HashMap Class
Description:
Backed by a hash table
No guaranteed order of keys
Allows one null key and multiple null values
Average constant time for operations
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 20 / 27
HashMap Example
1 import java . util . HashMap ;
2 import java . util . Map ;
3
4 public class Example {
5 public static void main ( String [] args ) {
6 Map < String , Integer > ageMap = new HashMap < >() ;
7 ageMap . put ( " Alice " , 30) ;
8 ageMap . put ( " Bob " , 25) ;
9 ageMap . put ( " Charlie " , 28) ;
0 ageMap . put ( " Bob " , 26) ; // Updates Bob ’s age
1
2 System . out . println ( ageMap . get ( " Alice " ) ) ; // 30
3
4 ageMap . remove ( " Charlie " ) ;
5
6 for ( String name : ageMap . keySet () ) {
7 System . out . println ( name + " = > " + ageMap .
get ( name ) ) ;
8 } } }
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 21 / 27
Common Map Interface Methods
Method Description
put(K key, V value) Adds or updates entry
get(Object key) Gets value by key
remove(Object key) Removes entry by key
containsKey(Object key) Checks if key exists
containsValue(Object value) Checks if value exists
keySet() Returns set of keys
values() Returns collection of values
entrySet() Returns set of key-value pairs
clear() Removes all entries
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 22 / 27
Map Implementations Comparison
Class Order Null Support Best Use C
HashMap No order 1 null key, many null values General-pur
LinkedHashMap Insertion order Same as HashMap Order-sensit
TreeMap Sorted by keys No null keys Sorted key
Hashtable No order No nulls Legacy sync
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 23 / 27
Queue Interface in Java
Package: [Link]
Extends: Collection<E>
Characteristics:
Represents FIFO (First-In-First-Out) data structure
Common operations: offer(), poll(), peek()
Allows null elements? No (throws NullPointerException on null
insertion)
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 24 / 27
Common Implementations of Queue
Class Description
LinkedList Doubly-linked list, supports Queue and Deque
ArrayDeque Resizable-array implementation, faster than LinkedList
PriorityQueue Elements ordered by natural order or comparator
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 25 / 27
Queue Example in Java
1 import java . util . Queue ;
2 import java . util . LinkedList ;
3
4 public class QueueExample {
5 public static void main ( String [] args ) {
6 Queue < String > queue = new LinkedList < >() ;
7
8 queue . offer ( " Apple " ) ;
9 queue . offer ( " Banana " ) ;
0 queue . offer ( " Orange " ) ;
1
2 System . out . println ( " Head of queue : " + queue .
peek () ) ; // Apple
3
4 while (! queue . isEmpty () ) {
5 System . out . println ( queue . poll () ) ;
6 }
7 }
8 }
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 26 / 27
Thank You!
Mayet Gizachew (College of Informatics DepartmentObject
of Computer
Oriented
Science)
Programming May 30, 2025 27 / 27