3. Data Structures in Java

Data Structures in Java

Data structures are essential for storing, organizing, and managing data efficiently. Java provides built-in data structures such as arrays, lists, sets, and maps to handle collections of elements. Understanding these data structures is crucial for developing robust and scalable applications.

Stack vs Heap

In Java, memory is divided into two main areas: the stack and the heap. The stack is used for storing method invocations, local variables, and references to objects in a LIFO (Last-In-First-Out) manner. The heap is used for storing objects and arrays, and it is managed by the garbage collector.

Examples of data structures that are stored on the stack:

• Primitive variables: int, double, boolean, etc.
• References to objects: String, List, Map, etc.

Examples of data structures that are stored on the heap:

• Objects: instances of classes created using the new keyword.
• Arrays: collections of elements of the same type.

a. Arrays

Arrays in Java are objects that store multiple values of the same type. The array reference is stored on the stack, while the array object itself is stored on the heap.

// Different ways to initialize arrays
int[] numbers = new int[5];          // Empty array
int[] numbers = {1, 2, 3, 4, 5};     // Initialize with values
int[] numbers = new int[]{1, 2, 3};  // Anonymous array
 
// Array properties
int length = numbers.length;  // Array length is fixed
 
// Multidimensional arrays
int[][] matrix = new int[3][3];

b. Lists

Lists are dynamic collections of elements that can grow or shrink in size. Java provides several list implementations, such as ArrayList and LinkedList. Lists allow you to add, remove, and access elements based on their index. Lists are useful when you need to store a collection of elements that can change in size. Lists are stored on the heap.

// Create an ArrayList of strings
List<String> names = new ArrayList<>();
 
// Common operations
names.add("Alice");           // Add element
names.remove(0);              // Remove by index
names.remove("Alice");        // Remove by value
int size = names.size();      // Get size
boolean empty = names.isEmpty(); // Check if empty
 
// Iteration
for(String name : names) {   // Enhanced for loop
    System.out.println(name);
}

c. Sets

Sets are collections that do not allow duplicate elements. Java offers HashSet, TreeSet, and LinkedHashSet implementations for sets. Sets are useful for maintaining unique values and performing set operations like union, intersection, and difference. Sets are stored on the heap.

// HashSet: No ordering guarantee, O(1) operations
Set<Integer> hashSet = new HashSet<>();
 
// TreeSet: Sorted order, O(log n) operations
Set<Integer> treeSet = new TreeSet<>();
 
// LinkedHashSet: Insertion order, O(1) operations
Set<Integer> linkedHashSet = new LinkedHashSet<>();

d. Maps

Maps are key-value pairs that allow you to associate keys with values. Java provides HashMap, TreeMap, and LinkedHashMap implementations for maps. Maps are useful for storing and retrieving data based on unique keys. Maps are stored on the heap.

// Create a HashMap of names and ages
Map<String, Integer> ages = new HashMap<>();
 
// Add key-value pairs to the map
ages.put("Alice", 30);
ages.put("Bob", 25);
 
// Retrieve the value associated with a key
int aliceAge = ages.get("Alice");

Queue

A queue is a data structure that follows the FIFO (First-In-First-Out) principle. Java offers Queue and Deque interfaces with implementations like LinkedList and ArrayDeque. Queues are commonly used for task scheduling, job processing, and breadth-first search algorithms. Queues are stored on the heap.

// Create a Queue of integers
Queue<Integer> numbers = new LinkedList<>();
 
// Add elements to the queue
numbers.offer(10);
numbers.offer(20);
 
// Remove and retrieve the first element
int first = numbers.poll();