Beyond Arrays: Structuring Data with Lists and Maps

In the early weeks of learning Java, arrays appear to be the ideal solution for storing data. They are simple, fast, and easy to declare. However, as our applications grow, the limitations of arrays become increasingly apparent. What happens when you don't know the exact size of your data in advance? Or when you need to find a specific record instantly without checking every single element one by one?

This article, the first in our Data Management series, explores the Java Collections Framework. We will move beyond the rigid constraints of static arrays and discover how to build flexible, dynamic applications using Lists and Maps.

The List Abstract Data Type (ADT)

A List is an abstract data type (ADT) representing an ordered sequence of elements that permits duplicates and, unlike static arrays, can dynamically grow and shrink in size. Lists are the direct evolution of arrays, providing a more flexible structure.

The List Interface: Defining the “What”

In the Java Collection Framework, the operations a generic List supports—adding, removing, and accessing elements—are defined abstractly by the List interface. This interface establishes the standard contract and expected behaviour (the "what") for any List implementation.

Crucially, as the figure below illustrates, this contract defines that a generic List must support manipulation at any point in the sequence, making it versatile for sequential data management:

• Front: Insertion or removal of an element at the beginning (index 0).

• Rear: Insertion (appending) or removal of an element at the end.

• Middle: Insertion or removal of an element at any specific, valid index.

The key advantage of the List ADT over low-level arrays is that performing these operations does not require the programmer to manage the underlying memory or element rearrangement; the implementation handles this complexity.

Implementations: Determining the "How"

While the List interface defines what a List does, specific implementation classes determine how those operations are performed internally.

These classes must fulfil the expected List contract, but they use different underlying data structures and logic. The choice of implementation impacts the performance (the "how") of the defined operations, even though the conceptual outcome remains the same for the user. For example, one implementation might excel at middle insertion or removal operations, while another might be optimised for access by index.

The Java Collections Framework provides two primary implementations of the List interface: ArrayList and LinkedList.

ArrayList

It uses a standard, fixed-size array internally. When it gets full, the Java runtime efficiently creates a larger array and copies the data over.

• Pros: It is very fast for retrieving items by index (random access).

• Cons: It is slower when adding or removing elements from the middle of the list, as all subsequent elements must be physically shifted in memory to close the gap or make space.

LinkedList

It uses a linked structure ("chain") where each element (node) points to the next.

• Pros: It is generally faster for frequent insertions and deletions at the beginning or middle of the list because no shifting is required—only the links between nodes need to be updated.

• Cons: It is slower for accessing specific indices because you have to traverse the chain node-by-node from the start to find an element.

Polymorphism and Generics

To use lists effectively, we combine two powerful concepts: Generics and Polymorphism.

First, we use Generics to ensure Type Safety. Collections in Java are strictly typed, meaning we must specify exactly what kind of objects the list will hold. We do this using the <Type> notation (the "diamond operator"). This prevents runtime errors by ensuring, for example, that we cannot accidentally add a Teacher object to a List intended for Student objects.

Second, we apply Polymorphism by declaring our variable using the Interface type (List) rather than the specific implementation (ArrayList or LinkedList).

// Interface (List) on the left, Implementation (ArrayList) on the right
List<Student> students = new ArrayList<>();

This approach promotes flexibility through abstraction. The variable students is defined by the List interface, meaning it can reference any object that implements that interface. If performance requirements change and a LinkedList becomes more suitable, only the instantiation on the right side needs to be updated. The rest of the codebase, which relies solely on the List contract, requires no modification.

List Operations

Unlike arrays, where we use square brackets [] to access elements, lists use methods defined in the List interface. Here is how we can add, remove, and access elements:

// 1. ADD: Add elements to the list (Name, Surname, Year, ID, Fee)
students.add(new Student("Michael", "Johnson", 1998, 54321, 4800));
students.add(new Student("William", "Taylor", 1999, 35791, 6000));
students.add(new Student("Elisabeth", "Smith", 1995, 12345, 5000));

// 2. REMOVE: Remove an element by index (0 is the first element)
students.remove(0); // Removes Michael Johnson

// 3. GET & SIZE: Iterate through the list using a loop
for (int i = 0; i < students.size(); i++) {
    // We use .get(i) instead of [i]
    Student s = students.get(i);
    System.out.println(s.getFee());
}

In this example, we manipulate the list using its built-in methods. We use students.add() to append new Student objects to the end of the list, passing the required details (Name, Surname, Year, ID, Fee) directly into the constructor. We can also insert a student at a specific position, such as index 0, which automatically shifts the existing elements to the right. Finally, the for loop demonstrates how to traverse the list: we use a standard loop that runs from index 0 up to students.size(), accessing each element sequentially with students.get(i) to print the student's fee.

The Need for Speed: Maps

While lists are excellent for maintaining an ordered sequence of items, they become inefficient when you need to search for a specific item.

Consider a scenario where you have a list of thousands of students, and you need to find the one with the Student ID 45678. Since the list doesn't know where that specific ID is located, the computer has no choice but to start at the beginning (index 0) and check every single student object one by one until it finds a match. This process is known as linear search.

In the worst-case scenario—if the student you are looking for is at the very end of the list—you would have to check every single item on the list. If your list contains millions of records, this operation becomes incredibly slow. If you require a fast lookup based on a unique identifier (such as an ID or username), you need a Map.

What is a Map?

A Map represents a collection of Key-Value pairs. Each key is unique and is used to look up a specific value.

Think of real-world examples:

• The Internet (DNS): When you type www.google.com (the Key) into your browser, the Domain Name System maps it to a specific IP Address, like 142.250.187.206 (the Value). You don't scan every IP address on the web to find Google; the lookup is direct.

• File Associations: Your Operating System uses a map to decide which application should be used to open a specific type of file. The File Extension (Key, e.g., .doc, .txt) maps to a specific Application (Value, e.g., Word, Notepad).

Internal Mechanics: HashMap

The most common Map implementation is the HashMap.

• Hashing: The HashMap does not search linearly. It uses a Hash Function on the Key to calculate an index (or "bucket") in its internal array.

• Instant Lookup: This allows the map to jump directly to the memory location where the Value is stored, providing extremely fast retrieval.

• No Order: A HashMap does not guarantee any specific order of elements. If you need the keys to be sorted, you must use a TreeMap.

Map Operations

Just like with Lists, Map is an interface that defines abstract operations, while classes like HashMap provide the implementation. The core operations for interacting with a Map revolve around associating keys with values and retrieving them efficiently:

• Put: Adds a new key-value pair to the map. If the key already exists, the old value is replaced.

• Get: Retrieves the value associated with a specific key. This is a direct lookup operation that does not require scanning the entire collection.

The following code illustrates an example of how we can use a Map to store Students, using their ID as the key and the corresponding object as the value.

// Key is Integer (Wrapper Class), Value is Student (Object)
Map<Integer, Student> students = new HashMap<>();

// 1. PUT: Add data (Key: Student ID, Value: Student Object)
students.put(54321, new Student("Michael", "Johnson", 1998, 54321, 4800));
students.put(35791, new Student("William", "Taylor", 1999, 35791, 6000));
students.put(12345, new Student("Elisabeth", "Smith", 1995, 12345, 5000));

// 2. GET: Retrieve data instantly using the Key
// We ask for the student with ID 54321 and get the Michael object back instantly
Student s = students.get(54321);
System.out.println("Found: " + s.getName()); 

// 3. VALUES: To process all students, we must iterate over the values() collection
for (Student student : students.values()) {
    System.out.println(student.getSurname());
}

In this example, we first create a HashMap and populate it using the put method, which links each unique Student ID (Key) to a specific Student object (Value). When we need to find Michael, we simply call get(54321) with his ID, and the map returns his record immediately without searching through William or Elisabeth.

Finally, the for loop demonstrates how to access every item in the collection if needed; by calling students.values(), we get a collection view of all the Student objects stored in the map, allowing us to iterate through them one by one to print their surnames.

An Object-Only World: Wrapper Classes

In the Map example above, you might have wondered why we declared Map<Integer, Student> instead of Map<int, Student>.

A core principle of the Java Collections Framework is that all collections store only objects (references). In contrast, primitives (int, char, boolean) are basic value types. Unlike objects, they do not inherit from Object and hold raw data rather than references. Since a primitive cannot be put directly into a Collection, Java provides Wrapper Classes—such as Integer for int, Double for double, and Boolean for boolean. These classes "wrap" the primitive value inside an Object, making it compatible with the Collections Framework.

You cannot write Map<int, Student>. You must write:

// Correct: Key is Integer (Wrapper Class), Value is Student (Object)
Map<Integer, Student> students = new HashMap<>();

// Similarly for Lists:
List<Integer> marks = new ArrayList<>();

Thanks to Autoboxing (Java automatically converting int to Integer and back), we can usually treat them as primitives in code, but understanding this underlying object requirement is essential.

Conclusion

We have now moved beyond simple arrays to a world of flexible data structures. By choosing Lists for ordered sequences that grow dynamically and Maps for instantaneous data retrieval, we can build applications that are both functional and efficient.

But organising data is only the first step. Once we have a list of hundreds of students, how do we make sense of it? In the next part of this series, we will tackle the challenge of Sorting—learning how to define custom rules to order our objects exactly the way we want.