Lesson

ArrayList in Java
Pre-Requisites
• Basics of Java
• Arrays in Java

List of Concepts Involved

• Collections in Java
• The Collection Interface
• The List Interface
• ArrayList Class
• Methods of ArrayList
• Problems based on ArrayList

Topic - Collections in Java

• Until now, we have understood the concept of one dimensional arrays and multi- dimensional arrays and
solved some problems based on these concepts. We have also understood the concept of object creation
for the non-primitive data types.

• If we know the count of objects to be created. Then, in that case, an array of such objects is created and all
the objects are stored in that array. Now, if there is a situation where we do not have information about the
count of objects to be stored and in which format, then we have to use the feature of java called “Collections”.

• A group of individual objects which are represented as a single unit is known as the collection of the objects.
• In other words, Java Collection is a single unit of objects.
• This collections framework provides a set of interfaces and classes to implement various data structures and
algorithms.

What is the interface ?(Will be explained in oops lectures)

• An interface in Java is a blueprint of a class.

• It has static constants and abstract() methods(The abstract keyword is a non-access modifier, used for
classes and methods. Class: An abstract class is a restricted class that cannot be used to create objects
(to access it, it must be inherited from another class). Method: An abstract method can only be used in an
abstract class, and it does not have a body.,).
• It is used to describe a behavior that classes must implement, similar to protocols.
• We can't create object of interfaces.

What is Framework ?

• A framework in programming is a structure of ready-made components or solutions that are customized in

order to speed up development.

• Using frameworks saves time and reduces the risk of errors. You don't need to write everything from scratch.

Cracking the Coding Interview in Java - Foundation

Topic - Collection Interface
• It is the root interface of the Java collections framework.
• It is a member of the Java collections framework.
• It is a part of java.util package.
• This interface cannot be implemented directly, it is implemented through its subinterfaces like List, Queue and Set.
• ArrayList class implements the List interface which is a subinterface of the Collection Interface.

e-> extends & i-> implements

Here, we have not shown the hierarchy of Queue and Set Interface as it will be discussed in coming lectures.

Topic-The List Interface

• It is an ordered collection that allows us to add and remove elements like an array.
• In Java, we must import java.util.List package in order to use List

Java classes which implements List Interface are-

• ArrayList
• LinkedList
• Vector
• Stack
Here, we will focus on ArrayList class only

Cracking the Coding Interview in java - Foundation

Topic - ArrayList Class
• Before going towards the ArrayList class, let us recap about Arrays. The Array is a fixed number of groups of
Similar kinds of objects placed at a continuous memory location. Similarly, ArrayList is a class which holds the
object of the same kind in the order of insertion without any limit to the number of objects to store, i.e. we can
say that Array is of fixed size and List is of dynamic sizing.

• ArrayList class extends AbstractList class and implements List interface.

• Syntax to create ArrayList

List<AnyClass> list = new ArrayList<AnyClass>();

• It uses a dynamic array data structure to store objects and elements.

• It allows duplicate objects and elements.

• It maintains the insertion order.

• It is non-synchronized.

• Its elements/objects can be accessed randomly.

Methods of ArrayList

Method Description
This is used to insert the specified element at the
void add(int
ht ps:/ www.javatpoint.com/java-ar aylist-ad -method index, E element) specified position in a list.

It is used to append the specified element at the end

add(E
ht ps:/ www.javatpoint.com/java-ar aylist-ad -method e)
of a list.

It is used to append all of the elements in the specified

addAll(Collection<?
https:/ www.javatpoint.com/java-ar aylist-addall-method extends E> c) collection to the end of this list, in the order that they
are returned by the specified collection's iterator.

addAll(int index, Collection<? extends E> c)

https://www.javatpoint.com/java-arraylist-addall-method
It is used to append all the elements in the specified
collection, starting at the specified position of the list.

clear() It is used to remove all of the elements from this list.

htps:/w w.jav tpoint.com/jav -ar ylist-clear-method

It is used to remove the element present at the

E remove(int index) specified position in the list

It is used to remove the first occurrence of the

ht ps:/ w w.javatpoint.com/java- r aylist-remove-method
boolean remove(Object o) specified element

Cracking the Coding Interview in Java - Foundation

 Description
Increases the capacity of this ArrayList instance,
ensureCapacity?(int Method
https://www.geeksforgeeks.org/arraylist-ensurecapacity-method-i n-java-with-examples/
minCapacity)
if necessary, to ensure that it can hold at least the
number of elements specified by the minimum
capacity argument

boolean isEmpty()
It returns true if the list is empty, otherwise false.

listIterator() Returns a list iterator over the elements in this list

int lastIndexOf(Object o) It is used to return the index in this list of the last
occurrence of the specified element, or -1 if the list
does not contain this element.

Object[] toArray() It is used to return an array containing all of the

elements in this list in the correct order.

It is used to return an array containing all of the

<T> T[] toArray(T[] a) elements in this list in the correct order.

boolean contains(Object o) It returns true if the list contains the specified element.

It is used to return the index in this list of the first

int indexOf(Object o)
occurrence of the specified element, or -1 if the List
does not contain this element.

boolean removeAll(Collection<?> c) It is used to remove all the elements from the list.

It is used to remove all the elements from the list that

boolean removeIf(Predicate<? super E> filter) satisfies the given predicate.
ht ps:/ www.javatpoint.com/java-ar aylist-removeal -method

protected void removeRange(int fromIndex, IIt is used to remove all the elements lies within the
int toIndex) given range.

void replaceAll(UnaryOperator<E> operator) It is used to replace all the elements from the list with
https:/ www.javatpoint.com/java-ar aylist-removerange-method the specified element.

Cracking the Coding Interview in java - Foundation

 Method Description
It is used to retain all the elements in the list that are
void hretainAll(Collection<?>
t ps:/ w w.javatpoint.com/java-ar aylist-retainal-method c)
present in the specified collection.

It is used to replace the specified element in the list,

E set(int index, E element)
present at the specified position

void sort(Comparator<? super E> c) It is used to sort the elements of the list on the basis
of the specified comparator.

It is used to create a spliterator over the elements

Spliterator<E> spliterator()
in a list.

It is used to fetch all the elements that lies within the

List<E> subList(int fromIndex, int toIndex) given range.

int size() It is used to return the number of elements present

in the list.

void trimToSize() It is used to trim the capacity of this ArrayList instance

to be the list's current size.

Cracking the Coding Interview in Java - Foundation

Examples of ArrayList:

import java.util.ArrayList;
import java.io.*;
import java.util.*;
public class ExampleArray{

public static void main(String args[]) {

ArrayList arrayList = new ArrayList();
System.out.println("initially the size of arrayList : " + arrayList.size());

// add elements to the array list

arrayList.add("P");
arrayList.add("Q");
arrayList.add("R");
arrayList.add(1, "P2");
System.out.println("Size of arraylist after inserting elements: " + arrayList.size());

// display the array list

System.out.println("Elements of arraylist are " + arrayList);
arrayList.add("10");
arrayList.add("@");
System.out.println("Elements of arraylist after inserting 2 elements are " + arrayList);
// Remove elements from the array list
arrayList.remove("10");
arrayList.remove(3);
System.out.println("Size of arrayList after deletions of 2 elements: " + arrayList.size());
System.out.println("Elements of arraylist are " + arrayList);

}
}

Cracking the Coding Interview in Java - Foundation

Topic - Problems based on ArrayList
Problem – Write a program to Reverse the given ArrayList.
Input – [0, 10,3,5,22,10]
Output – [10,22,5,3,10,0]

Approach 1 – We can use the custom function. Here we will reverse the ArrayList by considering it as a simple
array and traversing it in reverse order.
Steps –
1) Iterate the ArrayList from 0 to n/2 index
2) Swap the first and last element in each iteration
3) Once the loop ends, it return the reversed ArrayList

import java.util.ArrayList;
import java.io.*;
import java.util.*;

public class ExampleArray{

public static void main(String[] args)
{
ArrayList<Integer> list = new ArrayList<Integer>();

list.add(new Integer(0));
list.add(new Integer(10));
list.add(new Integer(3));
list.add(new Integer(5));
list.add(new Integer(22));
list.add(new Integer(10));
System.out.println("Before reverse: ");
print(list);
System.out.println("");
for (int i = 0; i < list.size() / 2; i++) {
Integer t = list.get(i);
list.set(i, list.get(list.size() - i - 1));
list.set(list.size() - i - 1, t);
}
System.out.println("After reverse: ");

print(list);
}

public static void print(ArrayList<Integer> list)

{
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}
}

Cracking the Coding Interview in Java - Foundation

Time Complexity –
If there are N numbers in the given ArrayList arr, then complexity will be O(N/2)

Space Complexity –
If there are N numbers in arraylist array arr, then complexity will be O(1).

Approach 2 – We can use the inbuilt Collections function. Collections is a class in Java which contains different
in-built functions for sorting, reversing, etc. We will use the Collections.reverse() function to reverse the ArrayList.

import java.io.*;
import java.util.*;

public class ExampleArray{

public static void main(String[] args)
{
ArrayList<Integer> list = new ArrayList<Integer>();

list.add(new Integer(0));
list.add(new Integer(10));
list.add(new Integer(3));
list.add(new Integer(5));
list.add(new Integer(22));
list.add(new Integer(10));
System.out.print("Before reverse: ");
print(list);
System.out.println("");

Collections.reverse(list);
System.out.print("After reverse: ");
print(list);
}

Cracking the Coding Interview in Java - Foundation

public static void print(ArrayList<Integer> list)
{
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}
}

Problem 2 :Write a program to sort an ArrayList of Strings in descending order.

Solution
import java.io.*;
import java.util.*;

public class ExampleArray{

public static void main(String args[]) {

ArrayList<String> arraylist = new ArrayList<String>();

arraylist.add("Akash");
arraylist.add("Rahul");
arraylist.add("Pankaj");
arraylist.add("Manoj");

/*Unsorted List: ArrayList content before sorting*/

System.out.println("ArrayList Before Sorting:");
for(String str: arraylist){
System.out.println(str);
}

/* Sorting in decreasing (descending) order*/

Collections.sort(arraylist, Collections.reverseOrder());

/* Sorted List in reverse order*/

System.out.println("ArrayList in descending order:");
for(String str: arraylist){
System.out.println(str);
}
}
}

Cracking the Coding Interview in Java - Foundation

Upcoming Class Teasers
Complexity theory
Space and time Complexity
Calculating Time and Space Complexity

Cracking the Coding Interview in Java - Foundation