ArrayList speed optimization

Lets see how we can increase the speed while processing the ArrayList. The default size for a Java ArrayList class at the initial stage is 10. When an ArrayList operation reaches its maximum capacity which is 10, it increases its capacity by approximately half. A lot of time gets consumed in this case. Lets see why suppose you are adding elements to the ArrayList and if it reaches to 10 then it creates bigger arraylist with size 15 (approx.) and copies both new and old data to it.
So if we are knowing the size in advance then it is very useful to initialize the arraylist with that size to avoid performance overhead.

Lets see how much difference it makes if specify initial size in advance.

public class ArrayListSpeedTest {
    private static int size = 5000000;
 
    public ArrayListSpeedTest() {
 
        ArrayList dynamicArrayList = new ArrayList();
        ArrayList staticArrayList = new ArrayList(size);
 
        // Lets check how much time it took to load dynamic arraylist size.
        long start = System.currentTimeMillis();
        loadData( dynamicArrayList );
        System.out.println("Dynamic array list took ("+ (System.currentTimeMillis()-start)+ " mS) to load the data.");
 
        // sLets check how much time it took to load static arraylist size.
        start = System.currentTimeMillis();
        loadData( staticArrayList );
        System.out.println("Static Array list took (" +(System.currentTimeMillis()-start) +" mS) to load the data.");
 
        }
 
        private void loadData(ArrayList target) {
            for(int i=0; i< size; i ++ ) {
                target.add(" test ");
            }
        }
 
        public static void main(String[] args){
            new ArrayListSpeedTest();
        }
}

 

Output:

Dynamic array list took (231 mS) to load the data.
Static Array list took (67 mS) to load the data.

Sorting an ArrayList in java

If the data in your ArrayList has a natural sorting order (ie, implements Comparable, as do String, Integer, ...), you can simply call the static Collections.sort() method. This is a stable, guaranteed n log n sort.

Collections.sort(yourArrayList);

If you want to choose a different sort criterion or your data doesn't implement xxxx, you will have to define a Comparator and pass that to the sort() method.

Collections.sort(yourArrayList, yourComparator);

Check out Collections for other useful utility methods.

Iterating over ArrayList in java

To get successive elements from an ArrayList, there are 4 ways:

Use either a for loop with an integer index to get all the elements from an ArrayList, or go over all elements in a ArrayList using an Iterator (forward) or ListIterator (forward / backward).

1. foreach loop. This is fast and works for all kinds of lists, but is not entirely flexible (only sequential forward with no deletions, additions, or multiple references). This should be your first choice in programming. Works efficiently with both ArrayList and LinkedList.
   

   ArrayList<String> a = new ArrayList<String>();
   . . .
   for (String s : a) {
       System.out.println(s);
   }

   
   
   
   
2. for loop with index. This is fast, but should not be used with a LinkedList. It does allow orders other than sequentially forward by one.
   
   

   for (int i = 0; i < a.size(); i++) {
       System.out.println(a.get(i));
   }

   
   
   
   
3. Iterator<E> - Allows simple forward traversal. Can be used for the largest number of other kinds of data structures. This example uses an Iterator to print all elements (Strings) in an ArrayList. It uses hasNext(), which returns true if there are more elements, and next(), which returns the next element. Works with both ArrayList and LinkedList.
   
   

   for (Iterator<String> iter = a.iterator(); iter.hasNext();) 
   {
       System.out.println(iter.next());
   }

   
   
   
   
4. ListIterator<E> - Allows traversal of the ArrayList, but it is more general than a simple Iterator, allowing inserts and deletes (although both are very slow for an ArrayList). It also allows bidirectional traversal. Works efficiently with both ArrayList and LinkedList.

Object only limitation with collections

A possible disadvantage of ArrayList is that it holds only object types and not primitive types (eg, int). To use a primitive type in an ArrayList, put it inside an object or use of the wrapper classes (eg, Integer, Double, Character, ...). The wrapper classes are immutable, so if you use, eg, Integer, you will not be able to change the integer value. In this case it may be more useful to define your own mutable class.

Automatic expansion of ArrayList

Use ArrayList when there will be a large variation in the amount of data that you would put into an array. Arrays should be used only when there is a constant amount of data. For example, storing information about the days of the week should use an array because the number of days in a week is constant. Use an array list for your email contact list because there is no upper bound on the number of contacts.

When to use arrays and when arraylist?

Programmers are frequently faced with the choice of using a simple array or an ArrayList. If the data has a known number of elements or small fixed size upper bound, or where efficiency in using primitive types is important, arrays are often the best choice. However, many data storage problems are not that simple, and ArrayList (or one of the other Collections classes) might be the right choice.

Performance of List interface implementations

LinkedList

- Performance of get and remove methods is linear time [ Big O Notation is O(n) ] - Performance of add and Iterator.remove methods is constant-time [ Big O Notation is O(1) ]

ArrayList

- The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. [ Big O Notation is O(1) ]
- The add operation runs in amortized constant time [ Big O Notation is O(1) ] , but in worst case (since the array must be resized and copied) adding n elements requires linear time [ Big O Notation is O(n) ]
- Performance of remove method is linear time [ Big O Notation is O(n) ]
- All of the other operations run in linear time [ Big O Notation is O(n) ]. The constant factor is low compared to that for the LinkedList implementation.

Difference between ArrayList and LinkedList

java.util.ArrayList and java.util.LinkedList are two Collections classes used for storing lists of object references Here are some differences:

ArrayList	LinkedList
ArrayList uses primitive object array for storing objects.	LinkedList is made up of a chain of nodes. Each node stores an element and the pointer to the next node. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.
ArrayList implements the RandomAccess interface.	LinkedList does not implement RandomAccess interface.
Because of above point its fast to access any element randomly in arraylist. The commonly used ArrayList implementation uses primitive Object array for internal storage. Therefore an ArrayList is much faster than a LinkedList for random access, that is, when accessing arbitrary list elements using the get method.	Note that the get method is implemented for LinkedLists, but it requires a sequential scan from the front or back of the list. This scan is very slow. For a LinkedList, there's no fast way to access the Nth element of the list.
Adding and deleting at the start and middle of the ArrayList is slow, because all the later elements have to be copied forward or backward. (Using System.arrayCopy())	Whereas Linked lists are faster for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers of a node.
Uses memory equivalent to element in it.	Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next and previous pointers.
ArrayList may also have a performance issue when the internal array fills up. The arrayList has to create a new array and copy all the elements there. The ArrayList has a growth algorithm of (n*3)/2+1, meaning that each time the buffer is too small it will create a new one of size (n*3)/2+1 where n is the number of elements of the current buffer. Hence if we can guess the number of elements that we are going to have, then it makes sense to create a arraylist with that capacity during object creation (using construtor new ArrayList(capacity)).	LinkedLists should not have such capacity issues.

Difference between Vector and ArrayList? What is the Vector class OR ArrayList vs Vector

Vector & ArrayList both classes are implemented using dynamically resizable arrays, providing fast random access and fast traversal. ArrayList and Vector class both implement the List interface. Both the classes are member of Java collection framework, therefore from an API perspective, these two classes are very similar. However, there are still some major differences between the two. Below are some key differences :

Vector	ArrayList
Vector is a legacy class which has been retrofitted to implement the List interface since Java 2 platform v1.2	Introduced in java v1.4.2. So its newer API.
Vector is synchronized.	ArrayList is not. Note: Even though Vector class is synchronized, still when you want programs to run in multithreading environment using ArrayList with Collections.synchronizedList() is recommended over Vector.
Vector has default size.	ArrayList has no default size.
The Enumerations returned by Vector's elements method are not fail-fast.	Whereas ArrayList does not have any method returning Enumerations, like other new collections.

Difference between iterator and index access

Index based access allow access of the element directly on the basis of index. The cursor of the datastructure can directly goto the ‘n’ location and get the element. It doesnot traverse through n-1 elements. So this is like random access, as it is in case of arrays.

In Iterator based access, the cursor has to traverse through each element to get the desired element.So to reach the ‘n’th element it need to traverse through n-1 elements. So this is the case of linked list, where we have to go through each element to insert something in list.

Insertion,updation or deletion will be faster for iterator based access if the operations are performed on elements present in between the datastructure.

Insertion,updation or deletion will be faster for index based access if the operations are performed on elements present at last of the datastructure.

Traversal or search in index based datastructure is faster.

ArrayList is index access and LinkedList is iterator access.

How to convert a String array to ArrayList?

Method 1:

String[] words = {"ace", "boom", "crew", "dog", "eon"};
List<String> wordList = Arrays.asList(words);

Method 2:

List<String> list = new ArrayList<String>(words.length);
for (String s : words) {
    list.add(s);
}

Method 3 :

Collections.addAll(myList, myStringArray);

Note: In the method no 1 Arrays.asList() is efficient because it doesn't need to copy the content of the array. This method returns a List that is a "view" onto the array - a wrapper that makes the array look like a list. When you change an element in the list, the element in the original array is also changed. Note that the list is fixed size - if you try to add elements to the list, you'll get an exception.

If you only need read access to the array as if it is a List and you don't want to add or remove elements from the list, then only use method no 1.

Convert ArrayList to Arrays in Java and vice-versa

ArrayList class has a method called toArray() that we are using in our example to convert it into Arrays.
Following is simple code snippet that converts an array list of countries into string array.

List<String> countryList= new ArrayList<String>();
 
countryList.add("India");
countryList.add("Switzerland");
countryList.add("Italy");
countryList.add("France");
 
String [] countries = list.toArray(new String[countryList.size()]);

So to convert ArrayList of any class into array use following code. Convert T into the class whose arrays you want to create.

List<T> list = new ArrayList<T>();
 
T [] countries = list.toArray(new T[list.size()]);

Convert Array to ArrayList

We just saw how to convert ArrayList in Java to Arrays. But how to do the reverse? Well, following is the small code snippet that converts an Array to ArrayList:

import java.util.ArrayList;
import java.util.List;
import java.util.Arrays;
 
...
 
String[] countries = {"India", "Switzerland", "Italy", "France"};
List list = new Arrays(Arrays.asList(countries));
System.out.println("ArrayList of Countries:" + list);

How to Convert an ArrayList to a HashSet?

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ArrayListToHashSet {

  public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    list.add(null);
    list.add("A"); 
    list.add("B");
    Set<String> hashset = new HashSet<String>(list);
    list = new ArrayList<String>(hashset);
    System.out.println(list.toString());
  }
}

The above code example also can be used to remove duplicate items from an ArrayList.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ArrayListToHashSet {

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add(null);
        list.add("A");
        list.add("A");
        list.add("A");
        list.add("A");
        list.add("B");
        list.add("B");
        list.add("B");
        list.add("C");
        Set hashset = new HashSet(list);
        list = new ArrayList(hashset);
        System.out.println(list.toString());
    }

}

Sorting a List

// Create a list
String[] strArray = new String[] {"z", "a", "C"};
List list = Arrays.asList(strArray);

// Sort
Collections.sort(list); // C, a, z

// Case-insensitive sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER); // a, C, z

// Reverse-order sort
Collections.sort(list, Collections.reverseOrder()); // z, a, C

// Case-insensitive reverse-order sort
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
Collections.reverse(list); // z, C, a

Operating on Lists

There are various type of operations that can be performed on lists:

• Collection Operations on Lists -  Simple and Bulk
• Positional Access and Search Operations on List
• Iterating over the List
• Range view operations on lists

ArrayList example 2

// Create the list
List list = new LinkedList(); // Doubly-linked list
list = new ArrayList(); // List implemented as growable array
// Append an element to the list

list.add("a"); 

// Insert an element at the head of the list

list.add(0, "b"); 

// Get the number of elements in the list

int size = list.size(); // 2 

// Retrieving the element at the end of the list

Object element = list.get(list.size()-1); // a

// Retrieving the element at the head of the

list element = list.get(0); // b

// Remove the first occurrence of an element boolean
b = list.remove("b"); // true
b = list.remove("b"); // false // Remove the element at a particular index element = list.remove(0); // a

Alphabetize.java (Arraylist example)

package alphabetizewords;

import java.util.*;

public class Alphabetize {

    public static void main(String[] args) {
        //... Declare variables.
        Scanner           in    = new Scanner(System.in);
        ArrayList words = new ArrayList();

        //... Read input one word at a time.
        System.out.println("Enter words.  End with EOF (CTRL-Z then Enter)");
        System.out.println("      or click Close Input in NetBeans.");

        //... Read input one word at a time, adding it to an array list.
        while (in.hasNext()) {
            words.add(in.next());
        }

        //... Sort the words.
        Collections.sort(words);

        //... Print the sorted list.
        System.out.println("\n\nSorted words\n");
        for (String word : words) {
            System.out.println(word);
        }
    }
}

ArrayList<E> - Some basic methods and constructors

java.util.ArrayList allows for expandable arrays, and is basically the same as the older the Collections Vector class.

ArrayList extends AbstractList and implements List, Cloneable, Serializable.  ArrayList capacity .grows automatically. The ArrayList is not synchronized. It permits all elements including null.
An ArrayList has these characteristics:

• An ArrayList automatically expands as data is added.
  
• Access to any element of an ArrayList is O(1). Insertions and deletions are O(N).
  
• An ArrayList has methods for inserting, deleting, and searching.
  
• An ArrayList can be traversed using a foreach loop, iterators, or indexes.

Implementation. ArrayLists are implemented with an underlying array, and when that array is full and an additional element is added, a new, larger, array is allocated and the elements are copied from the old to the new. Because it takes time to create a bigger array and copy the elements from the old array to the new array, it is a slightly faster to create an ArrayList with a size that it will commonly be when full. Of course, if you knew the final size, you could simply use an array. However, for non-critical sections of code programmers typically don't specify an initial size.

Common ArrayList methods and constructors

Here are some of the most useful ArrayList methods. Assume these declarations. Note that E is the notation for the type of an element in a collection. Sun recommends using single upper case letters for generic types.

int i;
ArrayList<E> a;
E e;
Iterator<E> iter;
ListIterator<E>liter;
E[] earray;
Object[] oarray;

Result	Method	Description
Constructors
a =	new ArrayList()	Creates ArrayList with initial default capacity 10.
a =	new ArrayList(cap)	Creates ArrayList with initial int capacity cap.
a =	new ArrayList(coll)	Creates ArrayList from the Collection coll.
Adding elements
	a.add(e)	adds e to end of ArrayList a
	a.add(i, e)	Inserts e at index i, shifting elements up as necessary.
Replacing an element
	a.set(i,e)	Sets the element at index i to e.
Getting the elements
e =	a.get(i)	Returns the object at index i.
oarray =	a.toArray()	Returns values in array of objects.
earray =	a.toArray(E[])	The array parameter should be of the E class. Returns values in that array (or a larger array is allocated if necessary).
Iterators
iter =	a.iterator()	Returns an Iterator for forward traversal.
liter =	a.listIterator(i)	Returns a ListIterator for forward / backward / modifying traversal, starting at index i. Start from end with a.listIterator(a.size())
liter =	a.listIterator()	Returns a ListIterator for forward / backward / modifying traversal.
Searching
b =	a.contains(e)	Returns true if ArrayList a contains e
i =	a.indexOf(e)	Returns index of first occurrence of e, or -1 if not there.
i =	a.lastIndexOf(e)	Returns index of last occurrence of e, or -1 if not there.
Removing elements
	a.clear()	removes all elements from ArrayList a
	a.remove(i)	Removes the element at position i.
	a.removeRange(i, j)	Removes the elements from positions i thru j.
Other
i =	a.size()	Returns the number of elements in ArrayList a.

 

Adding elements to the end of an ArrayList, getting them by index

ArrayList<E> a = new ArrayList<E>();  // Default size.
E s;          // Declare s to be an object type E.
. . .
a.add(s);     // Adds s to the end of the ArrayList a
. . .
s = a.get(i); // Assigns ith element from a to s.