Chapter 6: Data Structures in
Object-Oriented
Programming
In this chapter, we will explore various essential
data structures that play a crucial role in
organizing and managing data in OOP. Each sub-
lesson focuses on a specific data structure, its
characteristics, and implementation classes.
6.1. The Set
• A set is a collection of distinct elements with no specific order. In OOP,
sets are often used to store unique values and provide efficient
operations for set manipulation.
Key Concepts:
• Uniqueness of elements
• Set operations: union, intersection, difference
import [Link]; // Displaying elements
import [Link]; [Link]("Set elements: " +
set); // Set operations
public class SetExample {
Set anotherSet = new HashSet<>();
public static void main(String[]
[Link]("Banana");
args) {
[Link]("Grapes"); // Union
// Creating a HashSet [Link](anotherSet);
Set<String> set = new HashSet<>(); [Link]("Union: " + set);
// Adding elements to the set // Intersection [Link](anotherSet);
[Link]("Apple"); [Link]("Intersection: " + set);
[Link]("Banana"); // Difference [Link](anotherSet);
[Link]("Difference: " +
[Link]("Orange"); set); } }
6.2. Set Implementation Classes
HashSet:
• Implements a set using a hash table for efficient element retrieval.
• O(1) average time complexity for basic operations.
TreeSet:
• Implements a set using a self-balancing binary search tree.
• Provides ordered iteration of elements.
• O(log n) time complexity for basic operations.
6.3. The List
• A list is an ordered collection of elements, where each element has a position or
index. Lists are fundamental for storing and managing sequential data.
Key Concepts:
• Ordered elements with index access
• Dynamic size
6.4. List Implementation Classes
ArrayList:
• Implements a resizable array.
• Efficient for random access but less so for insertions and deletions.
LinkedList:
• Implements a linked list.
• Efficient for insertions and deletions but slower for random access.
import [Link]; // LinkedList example
import [Link]; List<String> linkedList = new LinkedList<>();
import [Link]; [Link]("Node 1");
public class ListExample { [Link]("Node 2");
public static void main(String[] args) { [Link]("Node 3");
// ArrayList example // Displaying elements
List<String> arrayList = new [Link]("ArrayList: " + arrayList);
ArrayList<>(); [Link]("LinkedList: " + linkedList)
[Link]("Element 1"); }
[Link]("Element 2"); }
[Link]("Element 3");
6.5. The Queue
A queue is a data structure that follows the First-In-First-Out (FIFO) principle, where
the first element added is the first to be removed.
Key Concepts:
• Enqueue and dequeue operations
6.6. Queue Implementation Classes
ArrayQueue:
• Implements a queue using a resizable array.
• Efficient for basic queue operations.
LinkedQueue:
• Implements a queue using a linked list.
• Efficient for dynamic size and frequent enqueue and dequeue operations.
import [Link]; // LinkedList example (implements Queue
interface)
import [Link];
Queue<String> linkedListQueue = new
import [Link]; LinkedList<>();
public class QueueExample { [Link]("Job 1");
public static void main(String[] args) { [Link]("Job 2");
// ArrayDeque example (can be used [Link]("Job 3");
as a queue) // Displaying elements
Queue<String> arrayDequeQueue = [Link]("ArrayDeque Queue: " +
new ArrayDeque<>(); arrayDequeQueue);
[Link]("LinkedList Queue: " +
[Link]("Task 1"); linkedListQueue);
[Link]("Task 2"); }
[Link]("Task 3"); }
6.7. Map/Dictionary
• A map, also known as a dictionary, is a collection of key-value pairs. Each key must be unique, and it
maps to a specific value.
Key Concepts:
• Key-value pairs
• Efficient key-based retrieval
Implementation Classes
HashMap:
• Uses a hash table for efficient key-based operations.
• O(1) average time complexity for basic operations.
TreeMap:
• Implements a map using a self-balancing binary search tree.
• Provides ordered key iteration.
• O(log n) time complexity for basic operations.
import [Link]; // TreeMap example
import [Link]; Map<String, Integer> treeMap = new
import [Link]; TreeMap<>();
public class MapExample { [Link]("Apple", 10);
public static void main(String[] args) { [Link]("Banana", 5);
// HashMap example [Link]("Orange", 8);
Map<String, Integer> hashMap = // Displaying elements
new HashMap<>(); [Link]("HashMap: " +
[Link]("One", 1); hashMap);
[Link]("Two", 2); [Link]("TreeMap: " + treeMap
[Link]("Three", 3); }