Using the List data structure in Java

The List data structure is one of the most used data structures in any programming language. Therefore, it is important to learn what it is and how to use it.

Table of Contents

• What is a data structure?
• What is a list?
• The List Abstract Data Type
  • We already have arrays, why do we need a List ADT implementation?
• List data structure example
  • Problem 1
  • Problem 2
• Summary

What is a data structure?

In Computer Science, we consider a data structure as a way to organize data to enable us to efficiently access the data. You can read on this link more about it.

Computer programs work with data. We give data as input and expect a certain output as a result. Because of this, it is important how we represent the data we get as input. Using this data representation, we have support to solve problems and to give the output that a user needs or is expecting.

What is a list?

A list is simply a collection or group of objects, where each object has a position.

Let’s examine some examples so you get a better idea:

• Several people standing in line next to each other. In this case, you will be able to see the first person, the second person, a third person and so on. First, second and third is the position. In this case, we have a list of people.
• Several cars standing one behind another in a one-way street. You can see a first car, a second car, etc. Here you can see that all of them have a position. In this case, we have a list of cars.
• The result of the Olympic games. There is a first country, a second country, and so on. In this case, we have a list of countries.
• The rank of the students in your class according to the average marks. Here, you will see a first student (with the highest average marks), a second student (with the second-highest average marks), and so on. In this case, you have a list of students.

Now that you understand what a list is, let’s see the list data structure.

The List Abstract Data Type

“In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behaviour (semantics) from the point of view of a user, of the data, specifically in terms of possible values, possible operations on data of this type, and the behaviour of these operations” Source Wikipedia.

In the case of the data, in Java ADT List you can store any type of object. You will see later the example of how to specify the type of objects you want to store.

See below the basic operations for the ADT List.

Operations:

• Size: returns the number of elements in the list
• isEmpty: returns if the list is empty
• contains(element): returns if the list contains a certain object
• add(element): add an element to the list
• remove(element): removes the given element from the list
• remove(index): removes the element at the given index
• get(index): return the element at the specified position in the list
• set(index, element): sets the given element at the given position
• indexOf(element): returns the position of the given element on the list

Most of the programming languages have an implementation of the ADT List. So, we can just go straight and use the classes provided by the programming language to use different types of lists.

Notice that one of the definitions of a class in Object-Oriented Programming is the following: A class is an ADT equipped with a possible partial implementation.

Therefore, we must look in the programming language we are using, for a class that implements the ADT List. Once we found the name, we can start using it to store lists of objects. The methods can vary slightly depending on the programming language you are using, but most of the basic methods will be available.

We already have arrays, why do we need a List ADT implementation?

Let’s think about the following situation: you must solve a problem, using OOP, in which you must deal with three different collections. A collection of students, a collection of marks and a collection of countries.

If you use arrays to model this situation, you will have to implement a way to add students, a way to add marks and a way to add countries to the three different arrays. As you can see, the three implementations will be the same, except for the type of object you are handling. This will result in repeated code, harder to maintain.

Now, the implementation of the ADT List comes to the rescue. You use the class list to store the objects you want to store, and then use the methods already implemented in that class.

Work in this way has the following benefits:

• You are following one of the main principles in OOP: code reuse. You don’t write the code to add an element to the collection twice. You actually don’t write a code for that at all.
• You don’t have repeated code in your program.
• You use code that is already tested and bug-free. A great advantage for your program.
• You write your code faster, focusing on what matters, to solve a problem. Instead of spending time on writing data structures that are already outside there for a long time.
• The code of your program will be shorter, and easier to understand and maintain.
• Among others.

List data structure example

In this case, we are going to use Java as a programming language, but the implementation should be similar to other programming languages.

Problem 1

Create a console application that stores a collection of integer numbers and print its average.

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

public class Main {

    public static void main(String[] args) {
        List<Integer> listOfintegers = new
                ArrayList();
        int amount = 20;
        for (int i=0; i<amount; i++){
            listOfintegers.add(i);
        }

        int sum = 0;
        for (int i=0; i<amount; i++){
            sum = sum + listOfintegers.get(i);
        }
        System.out.println("The total is " + sum);
        System.out.println("The average is " + (float)sum/amount);
    }
}

A couple of notes, in Java:

• List is an interface, so you cannot create objects from it.
• We can use several List implementations: ArrayList, LinkedList, etc. In the example we used ArrayList. An advantage of using ADTs is that you can change the dynamic type (read about dynamic and static types in this post), and that’s it. You don’t have to change anything, and your code will work.

The first for-loop is just to add values to the list. You can add one by one without using a loop.

The second loop is just the implementation of a basic algorithm for summing. You can find the 5 basic algorithms in this post.

Problem 2

Create a console application that stores a collection of students and prints if a certain student is part of the collection or not. Students have a student number and the country they were born in.

In this case, we must implement a class that represent students. Then, we can implement the console application.

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

class Student{
    private String studentNumber;
    private String country;

    public Student(String studentNumber, String country) {
        this.studentNumber = studentNumber;
        this.country = country;
    }
    public String getStudentNumber() {
        return studentNumber;
    }
    public String getCountry() {
        return country;
    }
}

public class Problem2 {
    static  void PopulateStudentList(List students){
        students.add(new Student("st1","country1"));
        students.add(new Student("st2","country2"));
        students.add(new Student("st3","country3"));
        students.add(new Student("st4","country4"));
    }
    public static void main(String[] args) {
        List<Student> students = new ArrayList();
        PopulateStudentList(students);
        System.out.print("Enter the student number: ");
        Scanner scanner = new Scanner(System.in);
        String sn = scanner.nextLine();
        boolean exists = false;
        for (Student student: students) {
            if (student.getStudentNumber().equals(sn)){
                exists = true;
                break;
            }
        }
        if (exists)
            System.out.println("The student IS in the list");
        else
            System.out.println("The student is NOT in the list");
    }
}

In this case, I created an auxiliary method to populate the list of students. You can also do it as part of the main method in the console application (like the previous example). Always remember that in programming there are several ways to solve the same problem.

After having some data in our list of students, we have to ask the user for a student number. Then we check every element of the list, comparing the student number of each student with the input we got from the user.

If we find the student number, we change the value of the variable that exists, so we can use that value outside of the for-loop to print that we find it. After that, we don’t need to keep searching because we already found the student, so we exit the loop with the instruction “break”.

Summary

The use of data structures is very important in programming.

When we use ADT implementations, we reuse code that is already tested and bug-free. Therefore, our code becomes more robust.

There are many benefits to using lists implementations instead of arrays. We avoid code repetition and create more robust code to solve problems. Also, our code is shorter, clean, and easy to understand.

H@ppy coding!