Making collections final

Once we write final

ArrayList list = new ArrayList();

We can add, delete objects from this list, but I can not

list = new ArrayList() or list = list1.

So declaring the list final means that you cannot reassign the list variable to another object.

There are two situations in which this can be useful.

1. You want to make sure that no-one reassigns your list variable once it has received its value. This can reduce complexity and helps in understanding the semantics of your class/method. In this case you are usually better off by using good naming conventions and reducing method length (the class/method is already too complex to be easily understood).
2. When using inner classes you need to declare variables as final in an enclosing scope so that you can access them in the inner class. This way, Java can copy your final variable into the inner class object (it will never change its value) and the inner class object does not need to worry what happens to the outer class object while the inner class object is alive and needs to access the value of that variable.

How to convert map to List in java?

Assuming map is your instance of Map :
map.values() will return a Collection containing all of the map's values
map.keys() will return a Set containing all of the map's keys
map.entrySet() will return a Set containing all map key value pairs.

Get list of keys

List<String> list = new ArrayList<String>(map.keySet());

Get list of values

List<String> list = new ArrayList<String>(map.values());

Range-view Operation on list

The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive. This half-open range mirrors the typical for-loop:

for (int i=fromIndex; i<toIndex; i++) {
    ...
}

As the term view implies, the returned List is backed by the List on which subList was called, so changes in the former List are reflected in the latter.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List. For example, the following idiom removes a range of elements from a list:

list.subList(fromIndex, toIndex).clear();

Similar idioms may be constructed to search for an element in a range:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Note that the above idioms return the index of the found element in the subList, not the index in the backing List.

Any polymorphic algorithm that operates on a List (like the replace and shuffle examples, above) works with the List returned by subList.

Here's a polymorphic algorithm whose implementation uses subList to deal a hand from a deck. That is to say, it returns a new List (the "hand") containing the specified number of elements taken from the end of the specified List (the "deck"). The elements returned in the hand are removed from the deck.

public static List dealHand(List deck, int n) {
    int deckSize = deck.size();
    List handView = deck.subList(deckSize-n, deckSize);
    List hand = new ArrayList(handView);
    handView.clear();
    return hand;
}

 

The literal-minded might say that this program deals from the bottom of the deck, but I prefer to think that the computer is holding the deck upside down. At any rate, for many common List implementations, like ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

Here's a program using the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command line arguments: the number of hands to deal and the number of cards in each hand.

 

import java.util.*;

class Deal {
    public static void main(String args[]) {
        int numHands = Integer.parseInt(args[0]);
        int cardsPerHand = Integer.parseInt(args[1]);

       // Make a normal 52-card deck
        String[] suit = new String[] {"spades", "hearts", "diamonds", "clubs"};
        String[] rank = new String[]
            {"ace","2","3","4","5","6","7","8","9","10","jack","queen","king"};
        List deck = new ArrayList();
        for (int i=0; i<suit.length; i++)
            for (int j=0; j<rank.length; j++)
                deck.add(rank[j] + " of " + suit[i]);

        Collections.shuffle(deck);

        for (int i=0; i<numHands; i++)
            System.out.println(dealHand(deck, cardsPerHand));
    }
}

Let's run the program:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades, king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts, queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds, 9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts, ace of hearts]

While the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it's highly recommended that you use the List returned by subList only as a transient object, to perform one or a sequence of range operations on the backing List. The longer you use the subList object, the greater the probability that you'll compromise it by modifying the backing List directly (or through another subList object).

 

Positional Access and Search Operations on Lists

The basic positional access operations (get, set, add and remove) behave just like their longer-named counterparts in Vector (elementAt, setElementAt, insertElementAt and removeElementAt) with one noteworthy exception. The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void). The search operations indexOf and lastIndexOf behave exactly like the identically named operations in Vector.

The addAll operation inserts all of the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection's iterator. This call is the positional access analogue of Collection's addAll operation.

Here's a little function to swap two indexed values in a List.

private static void swap(List a, int i, int j) {
    Object tmp = a.get(i);
    a.set(i, a.get(j));
    a.set(j, tmp);
}

Of course there's one big difference. This is a polymorphic algorithm: it swaps two elements in any List, regardless of its implementation type. "Big deal," you say, "What's it good for?" Funny you should ask. Take a look at this:

public static void shuffle(List list, Random rnd) {
    for (int i=list.size(); i>1; i--)
        swap(list, i-1, rnd.nextInt(i));
}

This algorithm (which is included in the JDK's Collectionsclass) randomly permutes the specified List using the specified source of randomness. It's a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it's fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactly list.size()-1 iterations). The following short program uses this algorithm to print the words in its argument list in random order:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = new ArrayList();
        for (int i=0; i<args.length; i++)
            l.add(args[i]);
        Collections.shuffle(l, new Random());
        System.out.println(l);
    }
}

In fact, we can make this program even shorter and faster. The Arraysclass has a static factory method called asList that allows an array to be viewed as a List. This method does not copy the array; changes in the List write through to the array, and vice-versa. The resulting List is not a general-purpose List implementation, in that it doesn't implement the (optional) add and remove operations: arrays are not resizable. Taking advantage of Arrays.asList and calling an alternate form of shuffle that uses a default source of randomness, you get the following tiny program, whose behavior is identical to the previous program:

import java.util.*;

public class Shuffle {
    public static void main(String args[]) {
        List l = Arrays.asList(args);
        Collections.shuffle(l);
        System.out.println(l);
    }
}

Collection Operations on Lists–Simple and Bulk

Create the lists

List list1 = new ArrayList(); 
List list2 = new ArrayList(); 

Add the elements

// Add elements to the lists ...
list1.add("Hanuman");

Bulk Add
Copy all the elements from list2 to list1 (list1 += list2). list1 becomes the union of list1 and list2

list1.addAll(list2); 

Bulk Remove
Remove all the elements in list1 from list2 (list1 -= list2). list1 becomes the asymmetric difference of list1 and list2

list1.removeAll(list2); 

Intersection of Lists
Get the intersection of list1 and list2. list1 becomes the intersection of list1 and list2

list1.retainAll(list2); 

Remove all elements from a list

list1.clear(); 

Truncate the list

int newSize = 2;
list1.subList(newSize, list1.size()).clear(); 

Lists In Java

A Listis an ordered Collection(sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations for:

• Positional Access: manipulate elements based on their numerical position in the list.
• Search: search for a specified object in the list and return its numerical position.
• List Iteration: extend Iterator semantics to take advantage of the list's sequential nature.
• Range-view: perform arbitrary range operations on the list.

List Interface

List Implementations

• ArrayList
• Vector
•  LinkedList

 

Comparing List to Vector

ListIterator Interface

Operations 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

Generic Lists in Java
Performance of List implementations in java

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.

Common methods of LinkedList in java

Often LinkedLists are selected for use because of the methods in this class. LinkedList has most of the common methods ArrayList has (add(), get(), set(), remove(), size(), etc) plus a number of new methods that can be very convenient:

addFirst(object) & addLast(object): adds the object to the beginning or end of the LinkedList.

peek(): This just returns the first element of the LinkedList. Appreciate this method name: The language architect here seemed to be feeling cutesy, which you don't see often.

poll():This returns and removes the first element of the LinkedList. Also this will return null if the LinkedListis empty.

offer(): Attempts to add object to the end of the LinkedLists, and returns a Boolean based on weather it was added or not.

removeFirst() & removeLast(): Returns and removes the last element.

Operations on Lists in java

Creating a list:

List listA = new ArrayList();

Adding Elements

To add elements to a List you call its add() method. This method is inherited from the Collection interface. Here are a few examples:

listA.add("element 1");
listA.add("element 2");
listA.add("element 3");

Adding element at particular index, like index 0 here:

listA.add(0, "element 0");

Accessing elements:

This is done by get method, which gets the element from particular index:

String element0 = listA.get(0);

Removing elements:

You can remove elements in two ways:

1. remove(Object element)
   
2. remove(int index)

remove(Object element) removes that element in the list, if it is present. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

remove(int index) removes the element at the given index. All subsequent elements in the list are then moved up in the list. Their index thus decreases by 1.

 

Iterating over elements:

This can be done in many ways, like using iterator, foreach style for loop, simple for loop with get method :

//access via Iterator
Iterator iterator = listA.iterator();
while(iterator.hasNext(){
  String element = (String) iterator.next();
}


//access via new for-loop i.e. foreach style
for(Object object : listA) {
    String element = (String) object;
}

//old style for loop
for(int i = 0;i<listA.size();i++) {
    String element = listA.get(i);
}

Generic Lists in java

By default you can put any Object into a List, but from Java 5, Java Generics makes it possible to limit the types of object you can insert into a List. Here is an example:

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

This List can now only have MyObject instances inserted into it. You can then access and iterate its elements without casting them. Here is how it looks:

MyClass myObject = list.get(0);

for(MyClass anObject : list){
   //do someting to anObject...   
}

However, note that this support for custom classes and generics is compile time only. Because if you try to add object of AnyOtherClass to MyClass, it will throw compile time error. At runtime, JVM doesn't make any difference between List of Strings or List of Integer or List of MyClass.

Introduction to Vectors in java

Vectors (the java.util.Vector class) are commonly used instead of arrays, because they expand automatically when new data is added to them. The Java 2 Collections API introduced the similar ArrayList data structure. ArrayLists are unsynchronized and therefore faster than Vectors, but less secure in a multithreaded environment. The Vector class was changed in Java 2 to add the additional methods supported by ArrayList. See below for a reasons to use each. The description below is for the (new) Vector class.
Vectors can hold only Objects and not primitive types (eg, int). If you want to put a primitive type in a Vector, put it inside an object (eg, to save an integer value use the Integer class or define your own class). If you use the Integer wrapper, you will not be able to change the integer value, so it is sometimes useful to define your own class.

Operating on Vectors in java–Common Operations

To Create a Vector

You must import either import java.util.Vector; or import java.util.*;. Vectors are implemented with an array, and when that array is full and an additional element is added, a new array must be allocated. Because it takes time to create a bigger array and copy the elements from the old array to the new array, it is a little faster to create a Vector 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.

• Create a Vector with default initial size
  Vector v = new Vector();
• Create a Vector with an initial size
  Vector v = new Vector(300);

 

 

To Add elements to the end of a Vector

v.add(s); // adds s to the end of the Vector v

Iterating over elements of a Vector API of java

You can use a for loop to get all the elements from a Vector, but another very common way to go over all elements in a Vector is to use a ListIterator. The advantage of an iterator is that it it can be used with other data structures, so that if you later change to using a linked list for example, you won't have to change your code. Here is an example of using an iterator to print all elements (Strings) in a vector. The two most useful methods are hasNext(), which returns true if there are more elements, and next(), which returns the next element.

ListIterator iter = v.listIterator();
while (iter.hasNext()) {
    System.out.println((String)iter.next());
}

Common methods in Vector API of Java

There are many useful methods in the Vector class and its parent classes. Here are some of the most useful. v is a Vector, i is an int index, o is an Object.

Method	Description
v.add(o)	adds Object o to Vector v
v.add(i, o)	Inserts Object o at index i, shifting elements up as necessary.
v.clear()	removes all elements from Vector v
v.contains(o)	Returns true if Vector v contains Object o
v.firstElement(i)	Returns the first element.
v.get(i)	Returns the object at int index i.
v.lastElement(i)	Returns the last element.
v.listIterator()	Returns a ListIterator that can be used to go over the Vector. This is a useful alternative to the for loop.
v.remove(i)	Removes the element at position i, and shifts all following elements down.
v.set(i,o)	Sets the element at index i to o.
v.size()	Returns the number of elements in Vector v.
v.toArray(Object[])	The array parameter can be any Object subclass (eg, String). This returns the vector values in that array (or a larger array if necessary). This is useful when you need the generality of a Vector for input, but need the speed of arrays when processing the data.

Replacements for old methods in Vector API

The following methods have been changed from the old to the new Vector API.

Old Method	New Method
void addElement(Object)	boolean add(Object)
void copyInto(Object[])	Object[] toArray()
Object elementAt(int)	Object get(int)
Enumeration elements()	Iterator iterator() ListIterator listIterator()
void insertElementAt(Object, int)	void add(index, Object)
void removeAllElements()	void clear()
boolean removeElement(Object)	boolean remove(Object)
void removeElementAt(int)	void remove(int)
void setElementAt(int)	Object set(int, Object)

See here for ensuring use of new method API in java.

Ensuring use of the new Vector API methods

When the new Collections API was introduced in Java 2 to provide uniform data structure classes, the Vector class was updated to implement the List interface. Use the List methods because they are common to other data structure. If you later decide to use something other than a Vector (eg, ArrayList, or LinkedList, your other code will not need to change.
Even up thru the first several versions of Java 2 (SDK 1.4), the language had not entirely changed to use the new Collections methods. For example, the DefaultListModel still uses the old methods, so if you are using a JList, you will need to use the old method names. There are hints that they plan to change this, but still and interesting omission.

When you create a Vector, you can assign it to a List (a Collections interface). This will guarantee that only the List methods are called.

Vector v1 = new Vector();  // allows old or new methods.
List   v2 = new Vector();  // allows only the new (List) methods.

See here for replacements of old methods in Vector API.

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.