Java Data Structures

Introduction to Data Structures in Java

A data structure is a specialized format for organizing, processing, retrieving, and storing data. It's a way of arranging data on a computer so that it can be accessed and updated efficiently.

Choosing the right data structure is a crucial part of designing an efficient algorithm and is a fundamental concept in computer science and software engineering.

Why are Data Structures Important?

Imagine you have a library with thousands of books. If the books were just thrown into a giant pile, finding a specific one would be nearly impossible. But if they are organized—say, alphabetically by author or by genre using the Dewey Decimal System—you can find any book quickly.

Data structures do the same thing for data in our programs. They provide a way to manage data for efficient access and modification.

• Efficiency: The right data structure can make the difference between a program that runs in seconds and one that takes hours.
• Reusability: Common data structures can be reused across many different applications.
• Abstraction: They hide the complex inner workings of data manipulation behind a simple interface.

Types of Data Structures

Data structures are broadly classified into two categories:

1. Linear Data Structures

In linear data structures, the elements are arranged in a sequential order. Each element is connected to its previous and next element.

• Array: A collection of items stored at contiguous memory locations. Java's built-in arrays are of a fixed size.
• List: An ordered sequence of elements. Unlike arrays, lists can typically grow and shrink dynamically. Examples in Java include ArrayList and LinkedList.
• Stack: A LIFO (Last-In, First-Out) structure. Think of a stack of plates.
• Queue: A FIFO (First-In, First-Out) structure. Think of a checkout line.

2. Non-Linear Data Structures

In non-linear data structures, elements are not arranged in a sequence. They are arranged in a hierarchical or networked manner.

• Tree: A hierarchical structure with a root node and child nodes. A file system directory is a good example.
• Graph: A collection of nodes (or vertices) connected by edges. Social networks or road maps can be represented as graphs.
• Map (or Hash Table): A collection of key-value pairs. Used for fast lookups based on a key.
• Set: A collection of unique, unordered elements.

Java's Built-in Data Structures

Java provides a rich, built-in library for working with common data structures, known as the Java Collections Framework (JCF). This framework provides interfaces and classes for most of the data structures mentioned above, like ArrayList, LinkedList, HashSet, HashMap, and more.

Using these pre-built, highly-optimized classes is almost always better than trying to implement your own from scratch.

In the following chapters, we will dive deep into the Java Collections Framework and learn how to use these powerful tools effectively.

Advanced: Big O Notation and Time Complexity

When choosing a data structure, seasoned developers evaluate Time Complexity and Space Complexity, often expressed using Big O Notation. It describes how the execution time or memory requirements grow as the amount of data increases.

• O(1) - Constant Time: The operation takes the same amount of time regardless of data size (e.g., retrieving an element from a HashMap by key, or an array by index).
• O(log n) - Logarithmic Time: The execution time grows very slowly as data increases (e.g., finding an element in a sorted TreeSet).
• O(n) - Linear Time: The execution time grows directly in proportion to the data size (e.g., searching for a specific value in an unsorted ArrayList).

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
  public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < 100000; i++) {
      list.add(i);
      set.add(i);
    }
    // O(n) operation - has to scan through the elements one by one
    boolean listHasIt = list.contains(99999); 
    // O(1) operation - jumps directly to the element using a hash
    boolean setHasIt = set.contains(99999); 
  }
}

Advanced: Concurrent Data Structures

The standard Java Collections (like ArrayList and HashMap) are not thread-safe. If multiple threads try to modify them at the exact same time, the program might crash or data might be corrupted.

For multithreaded applications, Java provides the java.util.concurrent package, which includes thread-safe, highly concurrent data structures.

import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;

public class Main {
  public static void main(String[] args) {
    // A Thread-safe map for concurrent environments
    Map<String, Integer> safeMap = new ConcurrentHashMap<>();
    safeMap.put("Alice", 100);
    safeMap.put("Bob", 200);
    // Multiple threads can safely read and write to safeMap simultaneously
    System.out.println("Alice's Score: " + safeMap.get("Alice"));
  }
}