Results 1 to 2 of 2
  1. #1
    Java Tutorial is offline Member
    Join Date
    Nov 2007
    Posts
    22
    Rep Power
    0

    Default Java Collection Framework (Lists)

    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.

    Java Code:
    Vector vec = new Vector();
    System.out.println(“Capacity: ” + vec.capacity());
    Output:
    Java Code:
    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.

    Java Code:
    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.

    Java Code:
    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:
    Java Code:
    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.

    Java Code:
    Vector <String> vec = new Vector<String>();
    
    vec.add("String1");
    vec.add(1);
    Exception:
    Java Code:
    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

    Java Code:
    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:
    Java Code:
    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.

    Java Code:
    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:
    Java Code:
    String1
    String2
    String3
    null
    String4
    Sometimes it is useful to get index of an object. This can be done with ArrayList.

    Java Code:
    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.

    Java Code:
    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.

    Java Code:
    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:
    Java Code:
    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.

    Java Collection Framework (Lists)-linedlist.png

    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.

    Java Code:
    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:
    Java Code:
    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

    Java Code:
    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:
    Java Code:
    Mercury
    Neptune
    LinkedList also has iterator method which is used to iterate over a LinkedList. Following example shows how to use it:
    Java Code:
    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.

    Java Code:
    ArrayList(Collection c)
    Vector(Collection c)
    Example:
    Java Code:
    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:
    Java Code:
    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.

    Java Code:
    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.

    Java Code:
    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.
    Last edited by JavaBean; 12-05-2007 at 05:18 PM.

  2. #2
    OldManEmu is offline Member
    Join Date
    May 2008
    Posts
    1
    Rep Power
    0

    Default

    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

Similar Threads

  1. 2 dimensional Lists
    By gapper in forum New To Java
    Replies: 4
    Last Post: 01-20-2008, 10:01 AM
  2. Java Collection Framework (Sets)
    By Java Tutorial in forum Java Tutorial
    Replies: 0
    Last Post: 12-07-2007, 08:50 PM
  3. Compare lists
    By JavaNoob in forum New To Java
    Replies: 2
    Last Post: 08-08-2007, 04:11 PM
  4. Tudu Lists 2.0
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 07-11-2007, 04:32 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •