Contenu du cours

Java Data Structures

1. Basic Data Structures

Introduction to Data Structures List and ArrayList Challenge: ArrayList CRUD operations LinkedList Implementing our LinkedList Challenge: LinkedList Section 1 Summary

2. Additional Data Structures

Queue Deque Queue Practice Stack Challenge: Deque Practice Section 2 Summary

3. Map

What is Map?HashMap<>HashMap Practice Map with Other Data Structures Section 3 Summary

4. enum & Stream API

enum Challenge: Character Class Stream API Method Reference Stream Practice Section 4 Summary

List and ArrayList

Let's start our introduction to the List data structure. Below is a flowchart illustrating the Hierarchy of Collections and Lists. It may seem like a large and complex diagram, but we'll break it down step by step.

In this section, we'll explore a specific type of collection called lists. We'll take a closer look at different list types, including ArrayList, LinkedList, and Stack.

Since all lists inherit from the List interface, we can create objects using the parent interface. But we'll dive deeper into that later.

For now, let's discuss the first type of list – ArrayList.

Above, you see the syntax for creating an ArrayList<>. There's one part you might not be familiar with – the generic. We'll cover generics and how to create them later.

For now, just remember that when creating an ArrayList, we specify the data type inside angle brackets. Also, keep in mind that lists cannot work with primitive data types. Instead, we use wrapper classes.

Now, let's create a list in code and add a few objects using the add() method.

Main


              1234567891011121314
            
package com.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> numberList = new ArrayList<>();
        numberList.add(10);
        numberList.add(15);
        numberList.add(5);
        System.out.println(numberList);
    }
}

As you can see, the add() method is very straightforward—it simply adds the specified value to the list.

Also, keep in mind that we need to import List and ArrayList from the java.util library. However, if you're using IntelliJ IDEA, it automatically imports these libraries for you, so there's no need to worry about it.

Now, let's look at an example of creating a list with our custom data type:

Main


              1234567891011121314151617181920212223242526272829303132333435
            
package com.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Dog bob = new Dog("Bob", 2);
        Dog ben = new Dog("Ben", 1);
        Dog brian = new Dog("Brian", 5);
        List<Dog> dogList = new ArrayList<>();
        dogList.add(bob);
        dogList.add(ben);
        dogList.add(brian);
        System.out.println(dogList);
    }
}

class Dog {
    String name;
    int age;

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

As you can see, we created our own class Dog and an ArrayList using this data type. When we printed the list, it displayed all the objects stored in it.

What if we have an array and need to convert it into a list? We can do this using the asList() method from the Arrays class.

This method allows us to create a list that contains the same elements as the original array. It's especially useful when we want to apply list methods to an array. The syntax is straightforward:

And we can immediately use it when initializing a new list, for example:

Main


              12345678910111213141516171819202122232425262728293031323334
            
package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Dog bob = new Dog("Bob", 2);
        Dog ben = new Dog("Ben", 1);
        Dog brian = new Dog("Brian", 5);
        Dog[] dogs = {bob, ben, brian};
        List<Dog> dogList = new ArrayList<>(Arrays.asList(dogs));
        System.out.println(dogList);
    }
}

class Dog {
    String name;
    int age;

    public Dog(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

Just as we can convert an array into a list, we can also convert a list into an array using the toArray() method.

ArrayList<> Methods

Let's go over the basic list methods. So far, we could have easily replaced lists with arrays, but here's the key difference—the methods.

The add() method is an overloaded method, meaning it has multiple variations. One of them allows us to add an element at a specific index.

When we insert an element in the middle of a list, all elements to the right shift one position to make space for the new element.

For example, if we add an element at the beginning of the list, all existing elements will shift one position to the right.

Let's take a look at an example:

Main


              123456789101112131415161718
            
package com.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 5; i++) { // Filling `numbers` list with 5 values
            numbers.add(i);
        }
        System.out.println("`numbers` before modifying: " + numbers);
        numbers.add(2, 10); // Adding 10 on the second index
        System.out.println("`numbers` after first modifying: " + numbers);
        numbers.add(0, 5);
        System.out.println("`numbers` after second modifying: " + numbers);
    }
}

The way the values shift when inserting an element can be visualized in the following illustration:

Retrieving Elements

Obviously, if we can add objects to a list at a specific index, we can also retrieve objects by their index using the get(int index) method.

Let's look at an example:

Main


              123456789101112131415
            
package com.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 5; i++) { // Filling `numbers` list with 5 values
            numbers.add(i);
        }
        int element = numbers.get(1);
        System.out.println(element);
    }
}

Removing Elements

We can add, we can retrieve, but can we delete? Of course! We can remove elements using the remove(int index) method.

This method is also overloaded, meaning there's another way to remove an element. We can use the remove(Object obj) method, which deletes the first occurrence of the specified element.

Now, let's imagine we have a large list of all the students in our course. However, one student misbehaved and was expelled. We don't know their exact index, so we need to remove them by name. But there's a catch—the code is a bit broken, and their name might appear multiple times in the list.

Let's write a program to remove all occurrences of this student from the list:

Main


              123456789101112131415161718
            
package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Bob", "Alice", "Charlie", "David", "Eva", "Frank", "Grace", "Hank", "Ivy", "Jack", "Katherine", "Leo", "Mia", "Nathan", "Olivia", "Paul", "Quinn", "Rachel", "Sam", "Tom", "Ursula", "Victor", "Wendy", "Xander", "Yvonne", "Zack", "Bob", "Emily", "Bob", "Jake", "Isabel", "Liam", "Nora", "Bob", "Sophia", "Bob", "Daniel", "Gabrielle", "Mike"};
        // Expelled student: Bob
        List<String> students = new ArrayList<>(Arrays.asList(names));
        System.out.println("Is Bob present in the list? " + students.contains("Bob"));
        while (students.contains("Bob")) {
            students.remove("Bob");
        }
        System.out.println("Is Bob still present in the list after the removal operation? " + students.contains("Bob"));
    }
}

You might have noticed that we used another list method—contains(Object obj). This method checks whether the specified element is present in the list and returns true or false.

By using contains(), we set the condition for the while loop, allowing us to remove all occurrences of a student like "Bob" from the list. Wonderful!

By the way, we can simplify this process significantly using the removeAll(Collection<?> c) method:

Main


              123456789101112131415161718
            
package com.example;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Bob", "Alice", "Charlie", "David", "Eva", "Frank", "Grace", "Hank", "Ivy", "Jack", "Katherine", "Leo", "Mia", "Nathan", "Olivia", "Paul", "Quinn", "Rachel", "Sam", "Tom", "Ursula", "Victor", "Wendy", "Xander", "Yvonne", "Zack", "Bob", "Emily", "Bob", "Jake", "Isabel", "Liam", "Nora", "Bob", "Sophia", "Bob", "Daniel", "Gabrielle", "Mike"};
        // Expelled student: Bob
        List<String> students = new ArrayList<>(Arrays.asList(names));
        System.out.println("Is Bob present in the list? " + students.contains("Bob"));
        List<String> expelledStudents = new ArrayList<>();
        expelledStudents.add("Bob");
        students.removeAll(expelledStudents);
        System.out.println("Is Bob still present in the list after the removal operation? " + students.contains("Bob"));
    }
}

The removeAll() method takes a collection as a parameter, containing values that will be removed from the list on which the method was called.

In this approach, we created a collection of expelled students and added "Bob" to it. This makes our code easily expandable—we can simply add more troublemakers to the expelled students list over time.

Updating a Value by Index

Let's get back to list methods—now it’s time for the update method.

Since the add() method simply shifts all elements to the right when inserting a new value, we need a different way to update an existing value by index.

The set(int index, Object value) method does exactly that:

Main


              12345678910111213141516
            
package com.example;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> example = new ArrayList<>();
        for (int i = 1; i <= 5; i++) {
            example.add(i);
        }
        System.out.println("List before modification: " + example);
        example.set(2, 28);
        System.out.println("List after modification: " + example);
    }
}

It's pretty straightforward—we replaced the element at the second index with the number 28.

Other Methods

We could discuss various list methods for a long time, but that would take quite a while.

Instead, you can find all the methods you need—along with complete documentation and detailed explanations—by opening the ArrayList class in IntelliJ IDEA.

To do this, simply import the ArrayList library, hold down the Command key (Ctrl for Windows), and click on ArrayList. This will show you all the fields and methods available in the class, helping you explore any methods you might have missed.