Java Collection Framework (Lists)

[Java Tutorial]

Introduction

Collection is defined as several things grouped together.

Java collection framework is made up of various interfaces to work with different groups. Implementation of the interfaces allow us to do our job but this means that data structure can be changed without changing the code.

Java.util package contains an interface called Collection. Collection is an interface which means it defines abstract methods (methods without body). The classes implementing this interface will define the implementation for the abstract methods in the Collection interface.

Subclasses

Following are the list of classes that implement Collection interface:

AbstractCollection, AbstractList, AbstractSet, ArrayList, BeanContextServicesSupport, BeanContextSupport, HashSet, LinkedHashSet, LinkedList, TreeSet, Vector

Each of these class, defines its own implementation of Collection interface. Of course, each abstract method is implemented in these classes.

Subinterfaces

Collection interface has following subinterfaces:
BeanContext, BeanContextServices, List, Set, SortedSet

These interfaces extends Collection.

List Interface

The classes implementing the List interface are:
AbstractList, ArrayList, LinkedList, Vector

List is an ordered collection of object. Ordered means in a sequence. So use can add item to a list at a certain position(index) and can retrieve the item from that very position. Also, duplicates are allowed in a List.

Vector

Vector is a special type of List. It implements List interface where as List interface extends from Collection interface. So all the abstract methods of Collection interface are available in List interface.

For example:

Collection interface provides following 2 methods for adding elements.

boolean add(Object o)
boolean addAll(Collection c)

List interface provides following 4 methods (2 from Collection interface) for adding elements.

void add(int index, Object element)
boolean add(Object o)
boolean addAll(Collection c)
boolean addAll(int index, Collection c)

The two additional methods added in List interface deal with the index. As you know, in a list you can store value at a defined index.

Vector has 4 constructors.

Vector()
Vector(Collection c)
Vector(int initialCapacity)
Vector(int initialCapacity, int capacityIncrement)

If you don’t specify the capacity of the Vector, it will have by default capacity to store 10 objects.

Vector vec = new Vector();
System.out.println(“Capacity: ” + vec.capacity());

Output:

Capacity: 10

Once the vector declared using default constructor is filled to its capacity, its capacity is doubled. This capacity change is an expensive operation because for this, a new array is created in the memory and all the previous data in the vector is shifted there. So it is better to minimize capacity increase operations. Talking about performance, initial capacity and growth factor are very important. One should try to minimize the need for expansion. Its an ideal scenario, that no expansion is required but one should also not declare a vector of initial capacity too large as compared to usage. For instance if you know that a vector will contain from 100 to 200 objects, then declaring a vector of 1000 capacity is not good at all.

Vector vec1 = new Vector(20);
Vector vec2 = new Vector(20,10);

These are another way of declaring Vector. Vector vec1 has initial capacity of 20 objects and its capacity will doubled on reaching the limit. Vector v2 has initial capacity of 20 objects and its capacity will grow by increments of 10 elements per expansion.

Vector can also be created using an existing collection.

ArrayList arrayList = new ArrayList();
arrayList.add("String1");
arrayList.add("String2");
arrayList.add("String3");

Vector vec = new Vector(arrayList);

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

Output:

String1
String2
String3

Vector with generics

Java 5 introduced generics which adds more power to Java. Vectors store objects in them, but that object can be of any type. It can be a String, Integer, Float or even a custom object. With generics, you can specify the type of objects that are allowed to be stored in a Vector. In the following example, I tried to store an integer into a Vector that is bounded by String.

Vector <String> vec = new Vector<String>();

vec.add("String1");
vec.add(1);

Exception:

The method add(int, String) in the type Vector<String> is not applicable 
   for the arguments (int)

Stack

Stack is a special type of Vector as it extends Vector class. Stack works on last-in-first-out (LIFO) principle. Stack class provides 5 operations to treat the vector in a special way.

boolean empty()
Object peek()
Object pop()
Object push(Object item)
int search(Object o)

Lets try push and pop operation on a Stack

Stack newStack = new Stack();
newStack.push("10");
newStack.push("20");
newStack.push("30");
newStack.push("40");
while(!newStack.empty())
{
System.out.println(newStack.pop());
}

Output:

40
30
20
10

ArrayList

ArrayList is a very useful collection. It also implements the List interface. It is almost the same as Vector but the main difference is that it is unsynchronized. Which means that multiple threads cannot use this. It is preferred in single threaded environment. Using Vector in single threaded environment is not a wise decision as it is waste of resources. Java treats Vector specially as it is for threaded environment.

As in Vector, one can add element any where in the ArrayList and it is re sizable. ArrayList also implements Serializable interface which means it can be stored on disk and can be retrieved later.

ArrayList provides following 3 constructors that should be used accordingly to the requirement.

ArrayList()
ArrayList(Collection c)
ArrayList(int initialCapacity)

We can also put a null value into an ArrayList. Following example shows how to create an ArrayList, add elements to it and how to retrieve value from an ArrayList.

ArrayList arrayList = new ArrayList();
arrayList.add("String1");
arrayList.add("String2");
arrayList.add("String3");
arrayList.add(null);
arrayList.add("String4");

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

Output:

String1
String2
String3
null
String4

Sometimes it is useful to get index of an object. This can be done with ArrayList.

System.out.println(arrayList.indexOf("String4"));

ArrayList with generics

Like Vectors, ArrayLists can also be made to deal with only one type of objects. This is useful in many cases.

ArrayList <Integer>arrayList = new ArrayList<Integer>();
arrayList.add(1);
arrayList.add(2);
arrayList.add(3);
arrayList.add(null);

The ArrayList declared above can only store integer objects. This is very useful and provides more control over collection. You are always sure that you will get objects of a specific type from the list.

Writing/Retriving ArrayList to disk

Since ArrayList implements the Serializable interface, therefore ArrayList can be serialized which means it can be persisted on the disk. Following example does exactly that.

ArrayList <String>arrayList = new ArrayList<String>();
arrayList.add("Mars");
arrayList.add("Satrun");
arrayList.add("Pluto");

FileOutputStream f_out = new FileOutputStream("C:\\arraylist.data");

ObjectOutputStream obj_out = new ObjectOutputStream (f_out);

obj_out.writeObject (arrayList);

System.out.println("ArrayList written on the disk.");

FileInputStream f_in = new FileInputStream("C:\\arraylist.data");
ObjectInputStream obj_in = new ObjectInputStream (f_in);
ArrayList <String>arrayList_fetched = 
new ArrayList<String>((ArrayList)obj_in.readObject());

System.out.println("ArrayList fetched from the disk.");

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

Output:

ArrayList written on the disk.
ArrayList fetched from the disk.
Mars
Satrun
Pluto

LinkedList

LinkList is another implementation of Collection interface. Apart from Collection, it also implements Cloneable, List and Serializable interface. Unlike Vector and ArrayList, it doesn’t implement RandomAccess interface. Also LinkedList is not synchronized, so multiple threads cannot access it.

LinkedList has following 2 constructions:

LinkedList()
LinkedList(Collection c)

Developers are confused when to use what. There are few things which should be kept in mind before using any collection. ArrayList and Vector uses arrays internally to store the objects. This means you get fast response when randomly accessing objects, because the array index gets the required elements/object. But drawback is that if you plant o add/remove objects at the start or in the middle of an ArrayList/Vector, it would be slow, because all the later elements have to copied forward or backward. When the initial capacity of ArrayList /Vector is filled up, a new array is created and contents are shifted. This surely is an expensive operation.

LinkedList does not use arrays internally to store objects/elements. This has benefits and drawbacks. LinkedList stores elements/objects in nodes. Each node stores an object and has a pointer to the next node. So its like a chain of nodes. Doubly linked list has two pointers at each node. One points to the next node and the other points to the previous node.



Since LinkedList does not use array for storage, therefore rendam access to objects is slow. If you want to access object no 777, then you have to go forward one by one or go backward one by one until you reach object no 777.

LinkedList has a benefit over ArrayList/Vector when it comes to insert and delete operation. LinkedLists can add and delete any element in the list very efficiently because only the node pointers are to be updated. While talking about the memory consumption, each element/object in a LinkedList takes a bit more memory as compared to ArrayList/Vector because of the pointers involved.

ArrayList, Vector and LinkedList all have their importance. The important thing is to use them in the right situation.

In the example below, we created a LinkedList and added 2 objects to it. We then added a 3rd object at the first index using addFirst() method. This will add the new node to the first place and only few pointers are readjusted. This operation in LinkedList is very efficient as compared to ArrayList/Vector.

LinkedList ll = new LinkedList();
ll.add("Pluto");
ll.add("Neptune");
ll.addFirst("Mercury");

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

Output:

Mercury
Pluto
Neptune

Now lets remove an element from the LinkedList. Here also, pointers of first and 3rd nodes are adjusted and 2nd node is not referred

LinkedList ll = new LinkedList();
ll.add("Pluto");
ll.add("Neptune");
ll.addFirst("Mercury");
ll.remove(1);
for(int i=0;i<ll.size();i++){
System.out.println(ll.get(i));

Output:

Mercury
Neptune

LinkedList also has iterator method which is used to iterate over a LinkedList. Following example shows how to use it:

Iterator it = ll.iterator();
while(it.hasNext()){
	System.out.println(it.next().toString());
}

LinkedList to ArrayList/Vector conversion

If you have a LinkedList and want to convert it into a Vector or into an ArrayList, then you simply have to use constructor which takes collection as a parameter.

ArrayList(Collection c)
Vector(Collection c)

Example:

LinkedList ll = new LinkedList();
ll.add("Str1");
ll.add("Str2");
ll.addFirst("Str3");

ArrayList arrayList = new ArrayList(ll);

Vector vector = new Vector(ll);

System.out.println("Printing elements of ArrayList:");
Iterator it = arrayList.iterator();
while(it.hasNext()){
	System.out.println(it.next().toString());
}

System.out.println("Printing elements of Vector:");
it = vector.iterator();
while(it.hasNext()){
	System.out.println(it.next().toString());
}

Output:

Printing elements of ArrayList:
Str3
Str1
Str2
Printing elements of Vector:
Str3
Str1
Str2

LinkedList with generics

Like Vectors and ArrayLists, LinkedList can also be made to deal with only one type of objects. Lets see how to do that.

LinkedList<String> ll = new LinkedList<String>();
ll.add("Str1");
ll.add("Str2");
ll.addFirst("Str3");

The LinkedList named ll can only store String objects. This is very useful and provides more control over collection. You are always sure that you will get objects of a specific type from the list.

AbstractList

AbstractList implements Collection and List interfaces. ArrayList, Vector and AbstractSequentialList extends from AbstractList. Actually AbstractList contains implementation of List interface for random access.

If you want to create a list that should not be modified, then you should extend this class. But then you have to provide implementations for the get(int index) and size() methods.

public class MyList extends AbstractList {

	@Override
	public Object get(int arg0) {
		return null;
	}

	@Override
	public int size() {	
		return 0;
	}
}

If you want a list to be modifiable, then you must additionally override set(int index, Object element) method.

Performance Issues

Lists (Vector, ArrayList and LinkedList) should be used when your list can contain duplicate elements and you want to insert element at you required position. Ok - it makes sense but what list one should use? It depends on the requirement.

Vector and ArrayList uses arrays internally to store objects. Which means that getting a specific element will be efficient but adding or removing an element from the start or from the middle will be an expensive operation as elements have to be shifted. When size of Vector or ArrayList is reached till capacity, then reallocation is done which also is an expensive operation. The main difference between Vector and ArrayList is that Vector is synchronized and ArrayList is not. So Vectors can be used in multithreaded environment.

LinkedList uses nodes internally to store elements and pointers are used to refer to the next node. Insertion and deletion are efficiently done as only few pointers are updated whereas, searching element at a particular position is an expensive operation.

So conclusion is that, one should understand that which list is for which situation.

[OldManEmu]

thanks for this..its so helpful and just beginning java, this makes things much clearer and easier to understand..again thank your for your time in putting this here

Emu