Wednesday, 26 August 2015

How to sort an arraylist of custom objects in Java

In ArrayList elements are added in sequential order and while displaying the elements by iterating an arraylist that same default ordering will be used. Sometimes we do have a requirement to sort an arraylist in ascending or descending order. In this post we'll see how to sort an ArrayList of custom objects.

In the post how to sort arrayList of strings we have already seen how to use Collections.sort method to sort such an ArrayList. The point to note here is that "All elements in the list must implement the Comparable interface" in order to use it with sort() method. So, if we have any custom class objects which we are storing in an array list then that custom class should also implement Comparable interface so that that array list can be used with sort method. Not doing so will result in compile time error.

Sorting arraylist containing custom object with Comparable

Let's say we have an Employee class. Objects of this Employee class are stored in an array list and we want to sort it on first name and last name.

public class Employee implements Comparable<Employee> {
    private String lastName;
    private String firstName;
    private String empId;
    private int age;
    public String getLastName() {
        return lastName;
    }
    public void setLastName(String lastName) {
        this.lastName = lastName;
    }
    public String getFirstName() {
        return firstName;
    }
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
    public String getEmpId() {
        return empId;
    }
    public void setEmpId(String empId) {
        this.empId = empId;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    
    @Override
    public String toString() {
        
        return getFirstName() + " " + getLastName() + " " + getAge() + " " + getEmpId();
    }
    @Override
    public int compareTo(Employee o) {
        int firstCmp = this.getFirstName().compareTo(o.getFirstName());
        return firstCmp != 0 ? firstCmp :  this.getLastName().compareTo(o.getLastName());
    }
}
Class where sorting of the list will be done.
public class SortObjectList {
    public static void main(String[] args) {
        List<Employee> empList = new ArrayList<Employee>();
        // Storing elements in the arraylist
        empList.add(getData("E001", "Mishra", "Pyaremohan", 35));
        empList.add(getData("E002", "Smith", "John", 45));
        empList.add(getData("E003", "Sharma", "Ram", 23));
        empList.add(getData("E004", "Mishra", "Pyaremohan", 60));
        empList.add(getData("E005", "Caroll", "Eva", 32));
        empList.add(getData("E003", "Tiwari", "Ram", 23));
        
        System.out.println("Original List");
        for(Employee emp : empList){
            System.out.println("" + emp);
        }
        // Sorting the list
        Collections.sort(empList);
        
        System.out.println("Sorted List");
        for(Employee emp : empList){
            System.out.println("" + emp);
        }    
    }
                
    // Stub method 
    private static Employee getData(String empId, String lastName, String firstName, int age){
        Employee employee = new Employee();
        employee.setEmpId(empId);
        employee.setLastName(lastName);
        employee.setFirstName(firstName);
        employee.setAge(age);
        return employee;
    }    
}

Output

Original List
Pyaremohan Mishra 35 E001
John Smith 45 E002
Ram Sharma 23 E003
Pyaremohan Mishra 60 E004
Eva Caroll 32 E005
Ram Tiwari 23 E003
Sorted List
Eva Caroll 32 E005
John Smith 45 E002
Pyaremohan Mishra 35 E001
Pyaremohan Mishra 60 E004
Ram Sharma 23 E003
Ram Tiwari 23 E003

Sorting arraylist containing custom object using Comparator

Here in Employee class it implements the compareTo() method, where first names take precedence over last names. So this is the natural ordering for sorting the Employee class objects.

Now in case we want to sort in an order where, if names are same, they are sorted on the basis of age in descending order we can't use the already implemented compareTo() method of the Employee class. Other scenario is what if you want to sort some objects that don't implement Comparable?

To do either of these things, you'll need to provide a Comparator - an object that encapsulates an ordering. Comparator interface consists of a single method.

public interface Comparator<T> {
    int compare(T o1, T o2);
}

The compare method compares its two arguments, returning a negative integer, 0, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator, the compare method throws a ClassCastException.

So the case where sorting logic is - if names are same, they are sorted on the basis of age in descending order you have to write a comparator class which will implement Comparator interface and provide implementation for the compare method.

public class SortObjectList {
    public static void main(String[] args) {
        List<Employee> empList = new ArrayList<Employee>();
        // Storing elements in the arraylist
        empList.add(getData("E001", "Mishra", "Pyaremohan", 35));
        empList.add(getData("E002", "Smith", "John", 45));
        empList.add(getData("E003", "Sharma", "Ram", 23));
        empList.add(getData("E004", "Mishra", "Pyaremohan", 60));
        empList.add(getData("E005", "Caroll", "Eva", 32));
        empList.add(getData("E003", "Tiwari", "Ram", 23));
        
        System.out.println("Original List");
        for(Employee emp : empList){
            System.out.println("" + emp);
        }
        // Sorting the list
        Collections.sort(empList, new MyComparator());
                
        System.out.println("Sorted List");
        for(Employee emp : empList){
            System.out.println("" + emp);
        }    
    }
                
    // Stub method 
    private static Employee getData(String empId, String lastName, String firstName, int age){
        Employee employee = new Employee();
        employee.setEmpId(empId);
        employee.setLastName(lastName);
        employee.setFirstName(firstName);
        employee.setAge(age);
        return employee;
    }
    
    
}

class MyComparator implements Comparator<Employee>{
    @Override
    public int compare(Employee o1, Employee o2) {
        int firstCmp = o1.getFirstName().compareTo(o2.getFirstName());
        if(firstCmp == 0){
            int lastCmp = o1.getLastName().compareTo(o2.getLastName());
            if(lastCmp == 0){
                return (o2.getAge() < o1.getAge() ? -1 :
                       (o2.getAge() == o1.getAge() ? 0 : 1));
            }else{
                return lastCmp;
            }
            
        }else{
            return firstCmp;
        }        
    }    
}

Output

Original List
Pyaremohan Mishra 35 E001
John Smith 45 E002
Ram Sharma 23 E003
Pyaremohan Mishra 60 E004
Eva Caroll 32 E005
Ram Tiwari 23 E003
Sorted List
Eva Caroll 32 E005
John Smith 45 E002
Pyaremohan Mishra 60 E004
Pyaremohan Mishra 35 E001
Ram Sharma 23 E003
Ram Tiwari 23 E003

Here it can be seen that the name which is same is sorted by age in descending order. The logic for sorting is in the compare method.

That's all for this topic how to sort an ArrayList of custom objects in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. Difference between Comparable and Comparator
  3. How to join lists in Java
  4. How to sort an ArrayList in descending order
  5. How to remove duplicate elements from an ArrayList in Java
  6. Java Collections interview questions

You may also like -

How LinkedList class works internally in Java Collections

In Java Collections framework there are two general purpose implementations of the list interface -

Out of these two Arraylist internally uses an array of Object which can be dynamically re-sized.

In this post I'll talk about how LinkedList implementation, provided by Java Collections framework, works internally

Note - Code of LinkedList class used here for reference is from Java 8.

LinkedList class in Java implements List and Deque interfaces and LinkedList implements it using doubly linkedlist.

Within the LinkedList implementation there is a private class Node which provides the structure for a node in a doubly linked list. It has item variable for holding the value and two reference to Node class itself for connecting to next and previous nodes.

The Node class from Linked List implementation

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

A graphical representation of Linked list with nodes

Here is a graphical representation of a linked list to help you better visualize how actually a node will look like and how it connects with other nodes through next and prev references.
Since it is storing references for both next and previous nodes that is why it is a doubly linked list implementation.

Though there are many methods with in the LinkedList class but here I'll try to explain the internal working of the LinkedList, how references are created and shuffled using these 3 methods -

  • private void linkFirst(E e)
  • void linkLast(E e)
  • public void add(int index, E element)

linkFirst() method is used to add an element at the beginning of the list and it is implemented as follows

/**
 * Links e as first element.
 */
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

Here one more important thing to mention is first and last reference which always refer to the first and last element of the linked list.

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

With this info it is easy to see that in the linkFirst method, if it is the very first element inserted into the list then first and last both refer to this new node.
In case linked list already contains elements and a new element is inserted at the beginning of the list. Then f will hold the reference to the node which was the first element before this insertion. first will be assigned the reference to the newly created node (first = newNode;). The element which was the first element before this insertion is at second position now so its prev element should store reference of the first node, that's what is happening here f.prev = newNode;

And in the call to the constructor of the node class f is sent as a parameter. If you see in the Node class constructor there is a line this.next = next; that's how the newly created node is storing the reference to the second node.

linkLast() method is used to insert element as the last element of the list. In that case the node which is currently the last node of the linked list will become the second last node now. So the newly created node's prev should store the reference to this second last node and the next of the second last node should store the reference to the node which is the last node now.

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

Here it is first checking if it is the very first element which is inserted in that case both first and last references point to it. If elements are already there in the linked list then the node which is currently the last node of the linked list will become the second last node now.

See the call to the constructor of the Node class (this.prev = prev;). So the newly created node's prev should store the reference to this second last node and the next of the second last node should store the reference to the node which is the last node now (l.next = newNode;).

add(int index, E element) is used to Insert the specified element at the specified position in this list.

public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

Here it calls linkBefore method

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

I am leaving it to you readers to figure out how linkBefore() method is working. It should be easy based on the explanation already provided for linkFirst() and linkLast() method.

That's all for this topic How Linked List class works internally in Java Collections. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How HashMap internally works in Java
  3. How to join lists in Java
  4. Difference between ArrayList and LinkedList in Java
  5. List iterator in Java
  6. Java Collections interview questions

You may also like -

Tuesday, 18 August 2015

How to sort arraylist in Java

In ArrayList elements are added in sequential order and while displaying the elements by iterating an arraylist that same default ordering will be used. Sometimes we do have a requirement to sort an arraylist in ascending or descending order. In this post we'll see how to sort an ArrayList of Strings, Integers or Dates.

Java provides a class called Collections in the package java.util which contains several utilities methods that operate on or return collections. In this class there is a static method sort which can be used for sorting an arraylist.
There are two overloaded versions of sort method and according to Java docs their description is -

  • public static <T extends Comparable<? super T>> void sort(List<T> list) - Sorts the specified list into ascending order, according to the natural ordering of its elements. All elements in the list must implement the Comparable interface. Furthermore, all elements in the list must be mutually comparable (that is, e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the list).

  • public static <T> void sort(List<T> list, Comparator<? super T> c) - Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator (that is, c.compare(e1, e2)must not throw a ClassCastException for any elements e1 and e2 in the list).

Sorting an ArrayList containing strings

To sort an arraylist of strings we can use the first of the two sort methods.
Collections.sort(List<T> list)

Example Code -

public class SortListDemo {

    public static void main(String[] args) {
        // Using diamond operator (Right side no type specified)
        // Available from Java7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        // sorting the list
        Collections.sort(cityList);
        //Displaying the list
        for(String city : cityList){
            System.out.println("Name " + city);
        }
    }
}

Output

Name Bangalore
Name Chennai
Name Delhi
Name Kolkata
Name Mumbai
Name Mumbai

Collections.sort will work in this case because String class implements Comparable interface and provides implementation for the method compareTo(String anotherString). As clearly specified in the Java docs "All elements in the list must implement the Comparable interface". Same way Integer class or Date class also implements Comparable interface so list of integers (or dates) can also be sorted in natural order by using sort method of the Collections class. In fact Java docs give a list of all the classes that implements comparable interface thus can be used with the sort method to sort the elements in the natural order.

Classes Implementing Comparable

Class Natural Ordering
Byte Signed numerical
Character Unsigned numerical
Long Signed numerical
Integer Signed numerical
Short Signed numerical
Double Signed numerical
Float Signed numerical
BigInteger Signed numerical
BigDecimal Signed numerical
Boolean Boolean.FALSE < Boolean.TRUE
File System-dependent lexicographic on path name
String Lexicographic
Date Chronological
CollationKey Locale-specific lexicographic

Sorting an ArrayList containing strings in descending order

According to the JavaDocs description of the compareTo(String anotherString) method provided in Comparable interface is -
Compares two strings lexicographically. The comparison is based on the Unicode value of each character in the strings. The character sequence represented by this String object is compared lexicographically to the character sequence represented by the argument string. The result is a negative integer if this String object lexicographically precedes the argument string. The result is a positive integer if this String object lexicographically follows the argument string. The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object)method would return true.

Which means using Collections.sort() method will always sort in ascending alphabetical order. For sorting an arraylist's elements in descending order we need to use the second sort method which takes two parameters. First is the list that has to be sorted and second a comparator class that can be used to allow precise control over the sort order.
Here again we have two options,

  • Use method reverseOrder() provided by Collections class itself

    General form and description

    public static <T> Comparator<T> reverseOrder()
    
    Returns a comparator that imposes the reverse of the natural ordering on a collection of objects that implement the Comparable interface.
  • Using a custom comparator.

Sorting Using reverseOrder method

public class SortListDemo {

    public static void main(String[] args) {
        // Using diamond operator (Right side no type specified)
        // Available from Java7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        // sorting the list in descending order
        Collections.sort(cityList, Collections.reverseOrder());
        //Displaying the list
        for(String city : cityList){
            System.out.println("Name " + city);
        }
    }
}

Output

Name Mumbai
Name Mumbai
Name Kolkata
Name Delhi
Name Chennai
Name Bangalore

Sorting Using custom Comparator

Internally reverseOrder method calls a Comparator class to do the sorting in reverse order. We can do it ourselves too by writing our own comparator class.

public class SortListDemo {
    public static void main(String[] args) {
        // Using diamond operator (Right side no type specified)
        // Available from Java7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        // sorting the list in descending order
        Collections.sort(cityList, new MyComparator());
        //Displaying the list
        for(String city : cityList){
            System.out.println("Name " + city);
        }
    }
}


//Custom comparator class
class MyComparator implements Comparator<String>{
    @Override
    public int compare(String o1, String o2) {
        return o2.compareTo(o1);
    }    
}

Comparator with Java 8

Since Comparator is a functional interface so we can use lambda expression to provide implementation of its abstract method. That will reduce the custom comparator implementation to a single line. Don't forget to import the comparator interface though.

Example code

public class SortListDemo {
    public static void main(String[] args) {
        // Using diamond operator (Right side no type specified)
        // Available from Java7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        // sorting the list in descending order
        Collections.sort(cityList, (String a, String b)->  b.compareTo(a));
        //Displaying the list
        for(String city : cityList){
            System.out.println("Name " + city);
        }
    }
}

Output

Name Mumbai
Name Mumbai
Name Kolkata
Name Delhi
Name Chennai
Name Bangalore

That's all for this topic how to sort ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How to loop/iterate an arraylist in Java
  3. How to join lists in Java
  4. How to remove elements from an ArrayList in Java
  5. How to remove duplicate elements from an ArrayList in Java
  6. Difference between Comparable and Comparator
  7. How to sort an ArrayList in descending order

You may also like -

Wednesday, 12 August 2015

How to remove duplicate elements from an ArrayList in Java

Arraylist does allow adding duplicate elements but sometimes there may be a need to remove duplicates from a list. In this post we'll talk about the ways to do that.

First thing that will come to mind is create a new list and loop through the already created old list, use contains to see if element is already added to the new list if not add it otherwise discard it.
Example code for this logic

public class RemoveDuplicatesDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        
        List<String> newList = new ArrayList<>();
        for(String name : cityList){
            if(!newList.contains(name)){
                newList.add(name);
            }
        }

        for(String name : newList){
            System.out.println("City Name - " + name);
        }
    }
}

But that much code is really not needed, as collection framework itself provides several options to remove duplicates from an arraylist. We can simply use a HashSet to do the trick of removing the duplicate elements. HashSet only stores unique elements and we'll use that feature of HashSet to remove duplicates. Only problem is it won't retain the order of the list.

Example code using HashSet

public class RemoveDuplicatesDemo {
    public static void main(String[] args) {
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        
        // creating a hashset using the list
        Set<String> citySet = new HashSet<String>(cityList);
        // remove all the elements from the list 
        cityList.clear();
        // add all the elements of the set to create a
        // list with out duplicates
        cityList.addAll(citySet);
        
        // displaying the elements
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

City Name - Delhi
City Name - Chennai
City Name - Kolkata
City Name - Mumbai
City Name - Bangalore

It can be seen that duplicate elements are removed but the original order is not retained. Though in most of the cases when we have such requirement to remove duplicates from the list order doesn't matter but if it does sweat not! LinkedHashSet is there to retain the order. LinkedHashSet differ from HashSet in that it maintains the insertion order.

Example code using LinkedHashSet

public class RemoveDuplicatesDemo {
    public static void main(String[] args) {
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        // creating a linkedhashset using the list
        Set<String> citySet = new LinkedHashSet<String>(cityList);
        // remove all the elements from the list 
        cityList.clear();
        // add all the elements of the set to create a
                // list with out duplicates
        cityList.addAll(citySet);
        
        // displaying the elements
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Chennai
City Name - Kolkata

It can be seen that the order is retained now.

Option with Java 8 Streams

Java 8 streams provide a very simple way to remove duplicate elements from a list. Using the distinct method.

Example code

public class RemoveDuplicatesDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        cityList.add("Mumbai");
        
        cityList = cityList.stream().distinct().collect(Collectors.toList());
        
        
        // displaying the elements
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
    }
}

Output

City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Chennai
City Name - Kolkata

It can be seen that the duplicate element is removed and original order is retained too that too in a single line.

That's all for this topic How to remove duplicate elements from an ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How to iterate an arraylist in Java
  3. How to join lists in Java
  4. How to remove elements from an ArrayList in Java
  5. How HashMap internally works in Java
  6. Java Collections interview questions

You may also like -

Tuesday, 11 August 2015

How to remove elements from an ArrayList

To remove elements from an ArrayList we can use remove method provided by ArrayList or the remove method provided by Iterator. In this post we'll see when to use which method and why.

ArrayList remove method

ArrayList provides two overloaded remove methods -
  • remove(int index) - This method takes int (which specifies the index in the list) as parameter and removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
  • public boolean remove(Object o) - This method takes the object, which has to be removed as parameter and removes the first occurrence of the specified element from this list, if it is present. If the list does not contain the element, it is unchanged.

If you are just removing an element from an ArrayList without looping the list then you can remove an element by giving its index in the list or specifying the object itself.

As example - If there is a list myList and you want to remove the element at index 4 then it can be done this way -

myList.remove(4);

Or by giving object to remove that object

myList.remove(obj);

Note that using ArrayList's remove method with enhanced for loop or iterator may result in ConcurrentModificationException.

ArrayList's remove method can be used with normal for loop but it may give undesired result because of the fact that all the other elements are shifted to the left when an element is removed.
As exp. In the given program code if I want to remove the elements at index 3 & 4 then ideally Hyderabad and Bangalore should be removed from the list. Let's see what happens -

public class RemoveFromListDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<String>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Kolkata");
        cityList.add("Hyderabad");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        
        for(int i = 0; i < cityList.size(); i++){
            if(i == 3 || i == 4){
                cityList.remove(i);
            }
        }
        
        System.out.println("After deletion " );
        for(String city : cityList){
            System.out.println("city " + city);
        }
    }
}

Output

After deletion 
city Delhi
city Mumbai
city Kolkata
city Bangalore

It can be seen that Hyderabad is removed alright but Mumbai is removed instead of Bangalore. This happened because after Hyderabad is removed elements in the list are shifted and Bangalore came in the place of Hyderabad and Mumbai in place of Bangalore. Thus Mumbai was at index 4 hence removed.

In the previous code if we were using city(object) in the if condition then it would have run fine.

public class RemoveFromListDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<String>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Kolkata");
        cityList.add("Hyderabad");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        
        for(int i = 0; i < cityList.size(); i++){
            String city = cityList.get(i);
            if(city.equalsIgnoreCase("Kolkata") || city.equalsIgnoreCase("Bangalore")){
                cityList.remove(i);
            }
        }
        
        System.out.println("After deletion " );
        for(String city : cityList){
            System.out.println("city " + city);
        }
    }
}

Output

After deletion 
city Delhi
city Mumbai
city Hyderabad
city Mumbai

Note here in place of cityList.remove(i); we can also use cityList.remove(city);

RemoveIf

If you are using Java 8 then removeIf method can be used, which takes Predicate functional interface as a parameter. In that case we can write the removal code with in one line as -

for(int i = 0; i < cityList.size(); i++){
    cityList.removeIf(p -> p.equalsIgnoreCase("Hyderabad") || p.equalsIgnoreCase("Bangalore"));
}

Concurrent Modification Exception

If we use the ArrayList remove method while iterating using enhanced for loop or iterator it will throw Concurrent Modification Exception as the iterators returned by ArrayList class's iterator and ListIterator methods are fail-fast. Which means if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.)
public class RemoveFromListDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<String>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Kolkata");
        cityList.add("Hyderabad");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        
                
        //System.out.println("After deletion " );
        for(String city : cityList){
            if(city.equalsIgnoreCase("Kolkata"))
                cityList.remove(city);
            //System.out.println("city " + city);
        }
    }
}

Output

Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
 at java.util.ArrayList$Itr.next(Unknown Source)
 at org.netjs.prog.RemoveFromListDemo.main(RemoveFromListDemo.java:20)

As it can be seen here ConcurrentModificationException is thrown because we are trying to structurally modify the list which it is iterated.

ArrayList remove method and AutoBoxing problem

While removing elements from an ArrayList of Integers we may get problem because of Autoboxing. As alreay mentioned there are two overloaded remove methods -

  • Remove(int index)
  • Remove(Object o)

If we give an int as parameter then it will always be treated as a call to remove method with int parameter.
Let's clear it with an example

public class RemoveFromListDemo {
    public static void main(String[] args) {
        
        List<Integer> numberList = new ArrayList<Integer>();
        // adding to list as int, no need to do
        // new Integer(1)
        numberList.add(1);
        numberList.add(2);
        numberList.add(3);
        numberList.add(4);
        
        // Removing by index 1
        numberList.remove(1);
        // This time removing the integer Object 4
        numberList.remove(4);
    }
}

Output

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 4, Size: 3
 at java.util.ArrayList.rangeCheck(Unknown Source)
 at java.util.ArrayList.remove(Unknown Source)
 at org.netjs.prog.RemoveFromListDemo.main(RemoveFromListDemo.java:20)

So, even if a user thinks while removing the second time that he is giving an object as parameter and hoping autoboxing will take care of all the wrapping to Integer Object chore it won't happen in this case. Second call will also be treated as a call to remove method with int parameter. First remove has already removed one element so now the list size is 3 and trying to access index 4 in such a list will throw IndexOutOfBoundsException.

So in this case user has to explicitly tell the compiler that remove method which takes object as parameter has to be called.

numberList.remove(new Integer(4)); 

Iterator remove method

While looping if we want to remove any element we have to use Iterator's remove method so that we don't get Concurrent Modification Exception.

public class RemoveFromListDemo {

    public static void main(String[] args) {
        List<String> cityList = new ArrayList<String>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Kolkata");
        cityList.add("Hyderabad");
        cityList.add("Bangalore");
        cityList.add("Mumbai");
        
                
        Iterator<String> itr = cityList.iterator();
        int i = 0;
        while(itr.hasNext()){
            System.out.println("city " + itr.next());
            if(i == 3 || i == 4){
                itr.remove();
            }
            i++;
        }
        
        System.out.println("After deletion " );
        for(String city : cityList){
            System.out.println("city " + city);
        }
    }
}

Output

city Delhi
city Mumbai
city Kolkata
city Hyderabad
city Bangalore
city Mumbai
After deletion 
city Delhi
city Mumbai
city Kolkata
city Mumbai

That's all for this topic How to remove elements from an ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How to remove duplicate elements from an ArrayList in Java
  2. How to sort arraylist in Java
  3. How ArrayList works internally in Java
  4. How to join lists in Java
  5. ArrayList in Java
  6. How HashMap internally works in Java
  7. Java Collections interview questions

You may also like -

Thursday, 6 August 2015

How to loop/iterate an ArrayList in Java

There are many ways to loop/iterate an arrayList in Java. We can use the simple for loop, for-each loop (advanced for loop) available from Java 5 onwards, iterator or ListIterator (though not a preferred way if we are just sequentially looping through the elements of a list) and from Java 8 using Java 8 forEach loop that works with stream.

So the options are -
  • for loop
  • for-each loop
  • iterator
  • ListIterator
  • Java 8 forEach loop

Let's see a program that will use all these ways to loop/iterate an array list.

public class LoopListDemo {
    public static void main(String[] args) {
        // Using Diamond operator, so with ArrayList 
        // don't need to provide String, this option is available from 
        // Java 7 onwards
        List<String> cityList = new ArrayList<>();
        cityList.add("Delhi");
        cityList.add("Mumbai");
        cityList.add("Bangalore");
        cityList.add("Chennai");
        cityList.add("Kolkata");
        
        // Using for loop with size
        System.out.println("With simple for loop");
        for(int i = 0; i < cityList.size(); i++){
            System.out.println("City Name - " + cityList.get(i));
        }
        
        // Using for-each loop 
        System.out.println("With for-each loop - Java 5");
        for(String name : cityList){
            System.out.println("City Name - " + name);
        }
        
        // Using Iterator
        System.out.println("With iterator - Java 5");
        Iterator<String> itr = cityList.iterator();
        while(itr.hasNext()){
            System.out.println("City Name - " + itr.next());
        }
        
        // Using List Iterator - though not needed if doing sequential looping
        System.out.println("With List iterator - Java 5");
        ListIterator<String> ltr = cityList.listIterator();
        while(ltr.hasNext()){        
            System.out.println("City Name - " + ltr.next());
        }
        
        //Using Java 8 iterable.forEach loop
        System.out.println("With for-each loop - Java 8");
        
        cityList.forEach((a)->System.out.println("City Name - " + a));
        
        //Using Java 8 iterable.forEach loop with method reference
        cityList.forEach(System.out::println);

    }

}

Output (curtailed)

With simple for loop
City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Chennai
City Name - Kolkata
With for-each loop - Java 5
City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Chennai
City Name - Kolkata
With iterator - Java 5
City Name - Delhi
City Name - Mumbai
City Name - Bangalore
City Name - Chennai
City Name - Kolkata

In my opinion for-each loop is best way to iterate a list if you just need to traverse sequentially through a list.
With Java 8 and multi-core environment you can also use java 8 forEach loop to take advantage of parallel computing. In that case you need to write it like -

cityList.parallelStream().forEach((a)->System.out.println("City Name - " + a));

That's all for this topic how to loop an ArrayList in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How ArrayList works internally in Java
  2. How HashMap internally works in Java
  3. How LinkedList class works internally in Java
  4. How HashSet works internally in Java
  5. How to remove duplicate elements from an ArrayList in Java
  6. How to convert Array to ArrayList in Java
  7. Java Collections interview questions

You may also like -

Wednesday, 5 August 2015

Java OOP interview questions

  1. What is encapsulation?

    Encapsulation means keeping together the implementation (code) and the data it manipulates (variables). In Java a class contains the member variables (instance variables) and the code in methods. In a properly encapsulated Java class method defines how member variables can be used.
    Read more about encapsulation here.


  2. What is abstraction?

    Abstraction means hiding the complexity and only showing the essential features of the object. So in a way, Abstraction means abstracting/hiding the real working and we, as a user, knowing only how to use it.

    Real world example would be a vehicle which we drive with out caring or knowing what all is going underneath.

    Read more about abstraction here.


  3. Difference between abstraction and encapsulation?

    Abstraction is more about hiding the implementation details. In Java abstraction is achieved through abstract classes and interfaces.

    Encapsulation is about wrapping the implementation (code) and the data it manipulates (variables) with in a same class. A Java class, where all instance variables are private and only the methods with in the class can manipulate those variables, is an example of encapsulated class.
    Read more about difference between Encapsulation and Abstraction in Java here.


  4. What is Polymorphism?

    Polymorphism, a Greek word, where poly means many and morph means change, thus it refers to the ability of an object taking many forms. The concept of polymorphism is often expressed as "One interface, multiple methods".
    Where one general class may have the generic method and the derived classes (classes which extend the general class) may add their own specific method with implementation. At the time of execution "One interface" i.e. the general class will take "many forms" i.e. references of the derived classes.
    Read more about polymorphism here.


  5. What is inheritance?

    Inheritance is a mechanism, by which one class acquires, all the properties and behaviors of another class. The class whose members are inherited is called the Super class (or base class), and the class that inherits those members is called the Sub class (or derived class).
    The relationship between the Super and inherited subclasses is known as IS-A relationship.
    Read more about inheritance here.


  6. What Is a Class?

    In object-oriented terms class provides a blue print for the individual objects created from that class. Once a class is defined it can be used to create objects of that type.
    Read more about class here.


  7. What Is an Object?

    In object-oriented terms object is an instance of the class, which gets its state and related behavior from the class. When a new class is created essentially a new data type is created. This type can be used to declare objects of that type.
    An object stores its state in fields and exposes its behavior through methods.
    Read more about object here.


  8. What is method overloading?

    When two or more methods with in the same class or with in the parent-child relationship classes have the same name, but the parameters are different in types or number the methods are said to be overloaded. This process of overloaded methods is known as method overloading.
    Read more about method overloading here.


  9. What is method overriding?

    In a parent-child relation between classes, if a method in subclass has the same signature as the parent class method then the method is said to be overridden by the subclass and this process is called method overriding.
    Read more about method overriding here.


Related Topics

  1. Core Java basics interview questions
  2. Java String interview questions
  3. Java Exception Handling interview questions
  4. Java Collections interview questions
  5. Java Multi-threading interview questions
  6. Java Concurrency interview questions

Tuesday, 4 August 2015

Java Exception Handling interview questions

  1. What is Exception Handling?

    Exception Handling in Java provides a way to handle a situation when an exception is thrown and shows a meaningful message to the user and continue with the flow of the program.

    When an exceptional condition occurs with in a method, the method (where the exception occurred) creates an Exception Object and throws it. The created exception object contains information about the error, its type and the state of the program when the error occurred.

    The method where the exception is thrown may handle that exception itself or pass it on. In case it passes it on, run time system goes through the method hierarchy that had been called to get to the current method to search for a method that can handle the exception.

    Five keywords used to manage Java exception handling

    • try - Any code that might throw an exception is enclosed within a try block.
    • catch - If an exception occurs in try block, catch block can provide exception handlers to handle it in a rational manner.
    • finally - The finally block always executes when the try block exits. So, any code that must execute after a try block is completed should be put in finally block.
    • throw - throw is used to manually thrown an exception.
    • throws - Any exception that is thrown in a method but not handled there must be specified in a throws clause.
    Read more about Exception handling in Java here.

  2. Explain the exception hierarchy in Java?

    Throwable class is the super class of all the exception types. Below Throwable class there are two subclasses which denotes two distinct branches of exceptions -

    • Exception - An Exception indicates that a problem has occurred, but it is not a serious system problem. The user programs you write will throw and catch Exceptions.
    • Error - It defines exceptions that are not expected to be caught by your program. Exceptions of type Error are used by the Java run-time system to indicate errors having to do with the run-time environment, itself.
      Examples of error are StackOverflowError, OutOfMemoryError etc.
    • Below Exception there is a distinct subclass RunTimeExcpetion - RunTimeExcpetion and its descendants denote the exceptional conditions that are external to the application, and the application usually cannot anticipate or recover from them.

    Read more about exception hierarchy in Java here.

  3. What is the difference between Checked Exception and Unchecked Exception?

    Checked Exception is a direct subclass of Exception where as unchecked exception is a subclass of RunTimeException.

    Checked exception should be wrapped in a try-catch block or specified as throws clause where as there is no such requirement for unchecked exception.

    Failure to provide exception handling mechanism for checked exception result in compiler error whereas no compile time error for unchecked exception.

    Checked exceptions are designed to reduce the number of exceptions which are not properly handled and where there is a reasonable chance for recovery. UnCheckedExceptions are mostly programming errors.

    Read more about difference between Checked Exception and Unchecked Exception here.

  4. What is the difference between error and exception?

    Exception - An Exception indicates that a problem has occurred, but it is not a serious system problem. The user programs you write will throw and catch Exceptions.

    Error - It defines exceptions that are not expected to be caught by your program. Exceptions of type Error are used by the Java run-time system to indicate errors having to do with the run-time environment, itself.
    Examples of error are StackOverflowError, OutOfMemoryError etc.


  5. Is it necessary that each try block must be followed by a catch block?

    No it is not mandatory that there should be a catch block after a try block. try block can have only a matching finally block. So there are these valid combnations try-catch-finally, try-catch, try-finally.

    Read more about try-catch block here.

  6. What is finally block?

    When an exception occurs in the code, the flow of the execution may change or even end abruptly. That may cause problem if some resources were opened in the method.
    As exp if a file was opened in a method and it was not closed in the end as some exception occurred then the resources may remain open consuming memory. finally provides that exception-handling mechanism to clean up.

    Code with in the finally block will be executed after a try/catch block has completed. The finally block will be executed whether or not an exception is thrown.

    Read more about finally block here.

  7. Is it possible to have a finally block without catch?

    Yes we can have a try-finally block, catch is optional. We can have these combinations try-catch-finally, try-catch, try-finally.

    Read more about finally block here.

  8. Are you aware of any scenario when finally will not be executed?

    According to Java docs. If the JVM exits (By explicitly using System.exit() or a JVM crash) while the try or catch code is being executed, then the finally block may not execute. Likewise, if the thread executing the try or catch code is interrupted or killed, the finally block may not execute even though the application as a whole continues.

    Read more about finally here.

  9. What is a nested try statement?

    A try-catch-finally block can reside inside another try-catch-finally block that is known as nested try statement.

    public class NestedTryDemo {
        public static void main(String[] args) {
            try{
                System.out.println("In Outer try block");
                try{
                    System.out.println("In Inner try block");
                    int a = 7 / 0;
                }catch (IllegalArgumentException e) {
                    System.out.println("IllegalArgumentException caught");
                }finally{
                    System.out.println("In Inner finally");
                }
            }catch (ArithmeticException e) {
                System.out.println("ArithmeticException caught");
            }finally {
                System.out.println("In Outer finally");
            }
        }
    }
    
    
    Read more about nested try statement here.

  10. What are multiple catch blocks?

    There might be a case when a code enclosed with in a try block throws more than one exception. To handle these types of situations, two or more catch clauses can be specified where each catch clause catches a different type of exception. When an exception is thrown, each of the catch statement is inspected in order, and the first one whose type matches that of the thrown exception is executed.

     int a[] = {0};
     try{
         int b = 7/a[i];
     }catch(ArithmeticException aExp){
         aExp.printStackTrace();
     }catch(ArrayIndexOutOfBoundsException aiExp){
         aiExp.printStackTrace();
     }
    
    Read more about multiple catch blocks here.

  11. What is exception propagation?

    When an exceptional condition occurs within a method, the method (where the exception occurred) creates an Exception Object and throws it. The created exception object contains information about the error, its type and the state of the program when the error occurred.
    The method where the exception is thrown may handle that exception itself or pass it on. In case it passes it on, run time system goes through the method hierarchy that had been called to get to the current method to search for a method that can handle the exception.
    If your program is not able to catch any particular exception, that will ultimately be processed by the default handler. This process of going through the method stack is known as Exception propagation.

    Read more about exception propagation here.

  12. What is throw keyword?

    It is possible for a Java program to throw an exception explicitly that is done using the throw statement.

    The general form of throw is -
    throw throwableObject;

    We can get this throwableObject in 2 ways -
    • By using the Exception parameter of catch block.
    • Create a new one using the new operator.
    try{
       throw new NullPointerException();   
      }catch(NullPointerException nExp){
       System.out.println("Exception caught in catch block of displayValue");
       throw nExp;
      }
     }
    
    Read more about throw keyword here.

  13. What is throws clause?

    If in a method we don't want to handle any exception but want to leave it to the calling method to handle any exception that is thrown by the called method, it is done using throws keyword.

    Using throws a method can just declare the exception it may throw and callers of the method have to provide exception handling for those exceptions (or they can also declare them using throws).

    General form of a method declaration that includes a throws clause

    type method-name(parameter-list) throws exception-list
    {
    // body of method
    }
    
    Here, exception-list is a comma-separated list of the exceptions that a method can throw.
    Read more about throws clause here.

  14. Difference between throw and throws?

    • throw is used to throw an exception.
    • throws is used to declare an exception, in the method signature, that can be thrown from a method.
    Read more about difference between throw and throws here.

  15. final Vs finally Vs finalize

    • final - final keyword is used to restrict in some way. It can be used with variables, methods and classes. When a variable is declared as final, its value can not be changed once it is initialized. Except in case of blank final variable, which must be initialized in the constructor.
      If you make a method final in Java, that method can't be overridden in a sub class.
      If a class is declared as final then it can not be sub classed.
    • finally - finally is part of exception handling mechanism in Java. finally block is used with try-catch block. finally block is always executed whether any exception is thrown or not and raised exception is handled in catch block or not. Since finally block always executes thus it is primarily used to close the opened resources like database connection, file handles etc.
    • finalize() - finalize() method is a protected method of java.lang.Object class. Since it is in Object class thus it is inherited by every class. This method is called by garbage collector thread before removing an object from the memory. This method can be overridden by a class to provide any cleanup operation and gives object final chance to cleanup before getting garbage collected.
      protected void finalize() throws Throwable
      {
          //resource clean up operations
      }
      
    Read more about final Vs finally Vs finalize here.

  16. What are the rules of exception handling with respect to method overriding?

    There are certain restrictions while overriding a method in case of exception handling in Java. Broadly there are two rules -

    • If superclass method has not declared any exception using throws clause then subclass overridden method can't declare any checked exception though it can declare unchecked exception.
    • If superclass method has declared an exception using throws clause then subclass overridden method can do one of the three things.
      • sub-class can declare the same exception as declared in the super-class method.
      • subclass can declare the subtype exception of the exception declared in the superclass method. But subclass method can not declare any exception that is up in the hierarchy than the exception declared in the super class method.
      • subclass method can choose not to declare any exception at all.
    Read more about exception handling and method overriding here.

  17. What is the error in the following code?

    class Parent{
       public void displayMsg() throws IOException{
         System.out.println("In Parent displayMsg()");
        throw new IOException("Problem in method - displayMsg - Parent");
       }
    }
    public class ExceptionOverrideDemo extends Parent{
      public void displayMsg() throws Exception{  
        System.out.println("In ExceptionOverrideDemo displayMsg()"); 
        throw new Exception("Problem in method - displayMsg - ExceptionOverrideDemo");
      }  
    }
     

    Here parent class had declared IOException where as subclass has declared Exception. Exception is the super class of IOException thus it is wrong according to the rules of method overriding and exception handling. Thus the code will give compiler error.

    Read more about exception handling and method overriding here.

  18. What is multi-catch statement in Java 7?

    Before Java 7 multi-catch statement, if two or more exceptions were handled in the same way, we still had to write separate catch blocks for handling them.

      catch(IOException exp){
        logger.error(exp);
        throw exp;
      }catch(SQLException exp){
        logger.error(exp);
        throw exp;
      }
      

    With Java 7 and later it is possible to catch multiple exceptions in one catch block, which eliminates the duplicated code. Each exception type within the multi-catch statement is separated by Pipe symbol (|).

    catch(IOException | SQLException exp){
        logger.error(exp);
        throw exp;
    }
     
    Read more about multi-catch statement in Java 7 here.

  19. What is try-with-resources or ARM in Java 7?

    Java 7 introduced a new form of try known as try-with-resources for Automatic Resource Management (ARM). Here resource is an object that must be closed after the program is finished with it. Example of resources would be an opened file handle or database connection etc.

    Before the introduction of try-with-resources we had to explicitly close the resources once the try block completes normally or abruptly.

    try {
        br = new BufferedReader(new FileReader("C:\\test.txt"));
        System.out.println(br.readLine());
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            if (br != null){
                System.out.println("Closing the file");
                br.close();
            }
                        
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
    

    try-with-resources helps in reducing such boiler plate code. Let's see the same example using try-with-resources.

    try(BufferedReader br = new BufferedReader(new FileReader("C:\\test.txt"))) {            
        System.out.println(br.readLine());
    } catch (IOException e) {
        e.printStackTrace();
    } 
     
    Read more about try-with-resources in Java 7 here.

  20. When is custom exception class needed? How to create a custom exception class?

    According to Java Docs, you should write your own exception classes if you answer yes to any of the following questions; otherwise, you can probably use someone else's.

    • Do you need an exception type that isn't represented by those in the Java platform?
    • Would it help users if they could differentiate your exceptions from those thrown by classes written by other vendors?
    • Does your code throw more than one related exception?
    • If you use someone else's exceptions, will users have access to those exceptions? A similar question is, should your package be independent and self-contained?
    Read more about creating custom exception class here.

Related Topics

  1. Java OOP interview questions
  2. Core Java basics interview questions
  3. Java String interview questions
  4. Java Collections interview questions
  5. Java Multi-threading interview questions
  6. Java Concurrency interview questions

Monday, 3 August 2015

How ArrayList works internally in Java

ArrayList arguably would be the most used collection along with the HashMap. Many of us programmers whip up code everyday which contains atleast one of these data structures to hold objects. I have already discussed how HashMap works internally in Java, in this post I'll try to explain how ArrayList works in Java.

As most of us would already be knowing that ArrayList is a Resizable-array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it. So let's see what is the backing data structure for an ArrayList and how it grows dynamically and ensures that there is always room to add elements. Because of all these side questions it is also a very important Java Collections interview question.

Note - Code of ArrayList used here for reference is from Java 8.

Where does ArrayList store elements

Basic data structure used by ArrayList to store objects is an array of Object class, which is defined like -

transient Object[] elementData;

I am sure many of you would be thinking why transient and how about serializing an ArrayList then?
ArrayList provides its own version of readObject and writeObject so no problem in serializing an ArrayList and that is the reason, I think, of making this Object array as transient.

What happens when ArrayList is created

ArrayList class provides 3 constructors to create an array list.

  • public ArrayList(int initialCapacity) - When this constructor is used we can provide some internal capacity rather than depending on the default capacity as defined in the ArrayList class.
    As example -
    List<String> myList = new ArrayList<String>(7);
    
    Code in the ArrayList class is as -
    public ArrayList(int initialCapacity) {
         if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
         } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
         } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
         }
    }
    

    Where EMPTY_ELEMENTDATA is defined as -

    private static final Object[] EMPTY_ELEMENTDATA = {};
    

    It is easy to see here, that if provided capacity is greater than zero then the elementData array will be created with that capacity, in case provided capacity is zero then elementData array is initialized with an empty Object array. In this case ArrayList will grow when first element is added.

  • public ArrayList() - In case default constructor is used i.e. ArrayList is created like -
     myList = new ArrayList();
    

    Code in the ArrayList class is as -

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    Where DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    

    So you can see initially it will be initialized with an empty array, it will grow only when first element is added to the list.

  • public ArrayList(Collection<? extends E> c) - If we want to construct a list containing the elements of the specified collection we can use this constructor. In this constructor implementation checks for the length of the collection passed as parameter, if length is greater than zero then Arrays.copyOf method is used to copy the collection to the elementData array.
    elementData = Arrays.copyOf(elementData, size, Object[].class);
    

How does ArrayList grow dynamically

When we add an element to an ArrayList it first verifies whether it has that much capacity in the array to store new element or not, in case there is not then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that much capacity (Actually uses Arrays.copyOf which returns the original array increased to the new length).

Code is like this -

public boolean add(E e) {
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

Where DEFAULT_CAPACITY is defined as -

private static final int DEFAULT_CAPACITY = 10;
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
       grow(minCapacity);
}

You can see here it is determined if there is a need to increase the size of the array, if yes then grow method is called.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Note that till Java 6 the new capacity calculation used to be like this -

int newCapacity = (oldCapacity * 3)/2 + 1;

Which is changed from Java 7 to use right shift operator. With right shift operator also it will grow by 50% of old capacity.
Let's see it with the help of a small program

public class Test {
    public static void main(String args[])  {
       int a = 10;
       System.out.println(a>>1);   
    }    
}

Output

5

If the default capacity was 10 then

 
int newCapacity = oldCapacity + (oldCapacity >> 1);
will return 15.

What happens when element is removed

When elements are removed from an ArrayList using either remove(int i) (i.e using index) or remove(Object o), in the underlying array the gap created by the removal of an element has to be filled. That is done by Shifting any subsequent elements to the left (subtracts one from their indices). System.arrayCopy method is used for that.
System.arraycopy(elementData, index+1, elementData, index, numMoved);

Here index+1 is the source position and index is the destination position. Since element at the position index is removed so elements starting from index+1 are copied to destination starting from index.

That's all for this topic how ArrayList internally works in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How HashMap internally works in Java
  2. How Linked List class works internally in Java
  3. How HashSet works internally in Java
  4. How to sort arraylist of custom objects in Java
  5. Java Collections interview questions
  6. CopyOnWriteArrayList in Java

You may also like -