2D Array List in Java


An Array List is a dynamic version of array. It is similar to Dynamic Array class where we do not need to predefine the size. The size of array list grows automatically as we keep on adding elements. In this article, we will focus on 2D array list in Java.

In short, it is defined as:

ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
// There are other methods which we covered 
// further in this article at OpenGenus

By default, when it is filled completely, its size increases to only 1.5 times its original capacity. So, it helps in reducing the space complexity immensely.

The elements of an ArrayList are stored in a chunk of contiguous memory. When that memory becomes full, a larger chunk of contiguous memory is allocated (1.5 times the size) and the existing elements are copied into this new chunk. This chunk is called the capacity of the ArrayList object.

There are mainly two common variations of ArrayLists, namely:

  • 1-D Array Lists (or commonly called Array Lists)
  • Multidimensional Array Lists

Multidimensional Array List

It is a collection of group of objects where each group can have any number of objects stored dynamically. Hence, here we can store any number of elements in a group whenever we want.

In Java we have Collection framework which provides functionality to store multidimensional Array List which is commonly called Multidimensional Collections (or Nested Collections)

The most common and the simplest form of Multidimensional Array Lists used is 2-D Array Lists. In this article, we'll dive deeper into it, studying about its implementation, advantages and disadvantages.

2-D Array List

A two dimensional array list can be seen as an array list of an array list. Here also, we do not need to predefine the size of rows and columns. When it is filled completely, the size increases automatically to store the next element.

Implementation

It is a generic class already defined in java. We just need to import it using -

import java.util.ArrayList;

Syntax

The following are diiferent ways to initialize a 2D ArrayList:

import java.util.ArrayList;

public class TwoDimensionalArrayLists{
    public static void main(String args[]) {
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
    }
}

where 1. arrLL is name of the arraylist created
2. Object is the data type of arraylist

or

import java.util.ArrayList;

public class TwoDimensionalArrayLists{
    public static void main(String args[]) {
        Twodimensional ArrayList: [[3,4],[2,4,5]]
    }
}

Here, a 2D arraylist is created.

Methods

Java 2D ArrayLists has various methods such as

  1. <ArrayList_name>.add(Object element) : It helps in adding a new row in our existing 2D arraylist where element is the element to be added of datatype of which ArrayList created.
  2. <ArrayList_name>.add(int index, Object element) : It helps in adding the element at a particular index.
  3. <ArrayList_name>.get(int index) : It helps in getting the index of the ArrayList where the required element is to be added.
  4. <ArrayList_name>.get(int index).indexOf(Object element): It helps in finding the index of particular element in our ArrayList in a particular row.
  5. <ArrayList_name>.remove(int row) : It helps in removing a particular row from our ArrayList.
  6. <ArrayList_name>.get(int row).remove(int index) : It helps in deleting an element present at a particular index of ArrayList in a given row.
  7. <ArrayList_name>.contains (Object element) : It helps in checking whether a particular element is present in a particular row.
  8. <ArrayList_name>.get(int index).lastIndexOf(Object element) : It helps in finding the last index whether the given element is present in our ArrayList.

Complexity

The complexity of various ArrayList methods on a subset of element where n is size of the ArrayList is as follows:

  1. add(int i, E element)

This method adds element of data type E at index i.

  • Worst case time complexity: Θ(n-i)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;

public class TwoDimensionalArrayLists{
    
    public static void main(String args[]) {
    
        // Creating 2D ArrayList
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
    
        // Allocating space to 0th row with the help of 'new' keyword
        // At 0th row, 0 gets stored in memory by default
        arrLL.add(new ArrayList<Integer>());
        // At 0th row, modifing the default value to 13
        arrLL.get(0).add(0, 13);
        
        System.out.println("2D ArrayList :");
        // Printing 2D ArrayList
        System.out.println(arrLL);
    }
 }

OUTPUT

2D ArrayList :
[[13]]
  1. remove(int i)

This method will delete the element at index i.

  • Worst case time complexity: Θ(n - i )
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;
public class TwoDimensionalArrayLists{
    public static void main(String args[]) {
    
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
        arrLL.add(new ArrayList<Integer>());
        arrLL.get(0).add(0, 13);
        
        // 0th row gets deleted from the arrayList created
        arrLL.remove(0);
        // Modified arrayList is
        System.out.println(arrLL);
        
    }
}

OUTPUT

[]
  1. remove(Object o)

This method will remove object o from the array list.

  • Worst case time complexity: Θ(n)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;
public class TwoDimensionalArrayLists{
    public static void main(String args[]) {
    
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
        arrLL.add(new ArrayList<Integer>());
        arrLL.get(0).add(0, 13);
        
        // Element at index 0 gets removed from 0th row
        arrLL.get(0).remove(0);
        // Modified arrayList is 
        System.out.println(arrLL);
        
    }
}

OUTPUT

[[]]
  1. contains(Object o)

This method checks if the array list have the object o.

  • Worst case time complexity: Θ(n)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;
public class TwoDimensionalArrayLists{
    public static void main(String args[]) {
    
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
        arrLL.add(new ArrayList<Integer>());
        arrLL.get(0).add(0, 13);
        
        // To check whether 13 present at a particular row in our ArrayList
        System.out.println(x.get(0).contains(13));
        System.out.println(x.get(0).contains(1));       
    }
}

OUTPUT

true
false
  1. indexOf(Object o)

This method will return the first index in which the object o appears in the array list.

  • Worst case time complexity: Θ(n)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;
public class TwoDimensionalArrayLists{
    
    public static void main(String args[]) {
    
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
        arrLL.add(new ArrayList<Integer>());
        arrLL.get(0).add(0, 13);
        
        // Determining the index of element - 13
        int ans = arrLL.get(0).indexOf(13);
        System.out.println(" Index of element 13 is "+ ans); 
     }
  }

OUTPUT

Index of element 13 is 0
  1. lastIndexOf(Object o)

This method returns the last index in which the object o appears in the array list.

  • Worst case time complexity: Θ(n)
  • Average case time complexity: Θ(1)
  • Best case time complexity: Θ(1)
  • Space complexity: Θ(1)
import java.util.ArrayList;
public class TwoDimensionalArrayLists{
    
    public static void main(String args[]) {
    
        ArrayList<ArrayList<Integer> > arrLL = new ArrayList<ArrayList<Integer> >();
        arrLL.add(new ArrayList<Integer>());
        arrLL.get(0).add(0, 13);
        
        // Determining the last index of element - 13
        int ans = arrLL.get(0).lastIndexOf(13);
        System.out.println(" Last Index of element 13 is "+ ans); 
     }
  }

OUTPUT

Last Index of element 13 is 0

Advantages

Array Lists have many advantages like,

  1. We don't have to specify size at the time of creation. 2D arraylist is a dynamic version of 2D arrays.
  2. It helps in reducing Space Complexity which is very important for competitive programmers.
  3. It is available in Java Collections Framework (STL library). So, it helps in reducing number of lines of code.

Applications

  1. It can be used to implement a graph where edges of the graph can be represented by 2D ArrayLists and can be stored in ArrayList of ArrayLists.
  2. It is used by competitive coders to solve various types of problems.

Questions

Q1. How to check whether the element that is to be added, already exists in our 2D ArrayList or not !?

Answer:

ArrayList<ArrayList<String> > movies_info = new ArrayList<ArrayList<Integer> >();
movies_info.add(new ArrayList<String>());
movies_info.get(i).add(title);
boolean found = false;
for (int i = 0; i < movies_info.size(); i++) {
    if(movies_info.get(i).contains(title)) {
    found = true;
}
if (!found) {
    movies_info.add(new ArrayList<String>());
    movies_info.get(i).add(title);
}

With this article at OpenGenus, you must have a complete idea of 2D array list in Java. Enjoy.