The Collection classes

There are some standard classes that implements Collection interface. Some of the classes provide full implementations that can be used as it is.Others are abstract classes, which provides skeletal implementations that can be used as a starting point for creating concrete collections.

The standard collection classes are:

ClassDescription
AbstractCollection Implements most of the Collection interface.
AbstractListExtends AbstractCollection and implements most of the List interface.
AbstractQueueExtends AbstractCollection and implements parts of the Queue interface.
AbstractSequentialListExtends AbstractList for use by a collection that uses sequential rather than random access of its elements.
LinkedListImplements a linked list by extending AbstractSequentialList
ArrayListImplements a dynamic array by extending AbstractList
ArrayDequeImplements a dynamic double-ended queue by extending AbstractCollection and implementing the Deque interface(Added by Java SE 6).
AbstractSetExtends AbstractCollection and implements most of the Set interface.
EnumSetExtends AbstractSet for use with enum elements.
HashSetExtends AbstractSet for use with a hash table.
LinkedHashSetExtends HashSet to allow insertion-order iterations.
PriorityQueueExtends AbstractQueue to support a priority-based queue.
TreeSetImplements a set stored in a tree. Extends AbstractSet.

Note:

  1. To use any Collection class in your program, you need to import it in your program. It is contained inside java.util package.
  2. Whenever you print any Collection class, it gets printed inside the square brackets [].

ArrayList class

Simple arrays have fixed size i.e it can store fixed number of elements. But, sometimes you may not know beforehand about the number of elements that you are going to store in your array. In such situations, We can use an ArrayList, which is an array whose size can increase or decrease dynamically.

  1. ArrayList class extends AbstractList class and implements the List interface.
  2. ArrayList supports dynamic array that can grow as needed. ArrayList has three constructors.
    ArrayList()  //It creates an empty ArrayList
    
    ArrayList( Collection C ) //It creates an ArrayList that is initialized with elements of the Collection C
    
    ArrayList( int capacity ) //It creates an ArrayList that has the specified initial capacity
    
  3. ArrayLists are created with an initial size. When this size is exceeded, the size of the ArrayList increases automatically.
  4. It can contain Duplicate elements and it also maintains the insertion order.
  5. Manipulation is slow because a lot of shifting needs to be occurred if any element is removed from the array list.
  6. ArrayLists are not synchronized.
  7. ArrayList allows random access because it works on the index basis.

Example of ArrayList

import java.util.*
class Test
{
 public static void main(String[] args)
 {
  ArrayList< String> al = new ArrayList< String>();
  al.add("ab");
  al.add("bc");
  al.add("cd");
  system.out.println(al);
 }
}

[ab,bc,cd]


Getting Array from an ArrayList

toArray() method is used to get an array containing all the contents of the ArrayList. Following are some reasons for why you can need to obtain an array from your ArrayList:

  • To obtain faster processing for certain operations.
  • To pass an array to methods which do not accept Collection as arguments.
  • To integrate and use collections with legacy code.

Storing User-Defined classes

In the above mentioned example we are storing only string object in ArrayList collection. But You can store any type of object, including object of class that you create in Collection classes.


Example of storing User-Defined object

Contact class

class Contact
{
    String first_name;
    String last_name;
    String phone_no;

    public Contact(String fn,String ln,String pn)
    {
    first_name = fn;
    last_name = ln;
    phone_no = pn;
    }

    public String toString()
    {
        return first_name+" "+last_name+"("+phone_no+")";
    }
}

Storing Contact class

public class PhoneBook
{

   public static void main(String[] args)
   {
       Contact c1 = new Contact("Ricky", "Pointing","999100091");
       Contact c2 = new Contact("David", "Beckham","998392819");
       Contact c3 = new Contact("Virat", "Kohli","998131319");

    ArrayList< Contact> al = new ArrayList< Contact>();
     al.add(c1);
     al.add(c2);
     al.add(c3);
     System.out.println(al);
   }

}

[Ricky Pointing(999100091), David Beckham(998392819), Virat Kohli(998131319)]


LinkedList class

  1. LinkedList class extends AbstractSequentialList and implements List,Deque and Queue inteface.
  2. LinkedList has two constructors.
    
    LinkedList() //It creates an empty LinkedList
    
    LinkedList( Collection C ) //It creates a LinkedList that is initialized with elements of the Collection c
  3. It can be used as List, stack or Queue as it implements all the related interfaces.
  4. They are dynamic in nature i.e it allocates memory when required. Therefore insertion and deletion operations can be easily implemented.
  5. It can contain duplicate elements and it is not synchronized.
  6. Reverse Traversing is difficult in linked list.
  7. In LinkedList, manipulation is fast because no shifting needs to be occurred.

Example of LinkedList class

import java.util.* ;
class Test
{
 public static void main(String[] args)
 {
  LinkedList< String> ll = new LinkedList< String>();
  ll.add("a");
  ll.add("b");
  ll.add("c");
  ll.addLast("z");
  ll.addFirst("A");
  System.out.println(ll);
 }
}

[A, a, b,c, z]


Difference between ArrayList and Linked List

ArrayList and LinkedList are the Collection classes, and both of them implements the List interface. The ArrayList class creates the list which is internally stored in a dynamic array that grows or shrinks in size as the elements are added or deleted from it. LinkedList also creates the list which is internally stored in a DoublyLinked List. Both the classes are used to store the elements in the list, but the major difference between both the classes is that ArrayList allows random access to the elements in the list as it operates on an index-based data structure. On the other hand, the LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.

Some more differences:

  • ArrayList extends AbstarctList class whereas LinkedList extends AbstractSequentialList.
  • AbstractList implements List interface, thus it can behave as a list only whereas LinkedList implements List, Deque and Queue interface, thus it can behave as a Queue and List both.
  • In a list, access to elements is faster in ArrayList as random access is also possible. Access to LinkedList elements is slower as it follows sequential access only.
  • In a list, manipulation of elements is slower in ArrayList whereas it is faster in LinkedList.

HashSet class

  1. HashSet extends AbstractSet class and implements the Set interface.
  2. HashSet has three constructors.
  3. HashSet()  //This creates an empty HashSet
    
    HashSet( Collection C )  //This creates a HashSet that is initialized with the elements of the Collection C
    
    HashSet( int capacity )  //This creates a HashSet that has the specified initial capacity
  4. It creates a collection that uses hash table for storage. A hash table stores information by using a mechanism called hashing.
  5. In hashing, the informational content of a key is used to determine a unique value, called its hash code. The hash code is then used as the index at which the data associated with the key is stored.
  6. HashSet does not maintain any order of elements.
  7. HashSet contains only unique elements.

Example of HashSet class

import java.util.*;
class HashSetDemo
{
 public static void main(String args[])
 {
  HashSet< String> hs = new HashSet< String>();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  System.out.println(hs);
 }
}

[D, E, F, A, B, C]


LinkedHashSet Class

  1. LinkedHashSet class extends HashSet class
  2. LinkedHashSet maintains a linked list of entries in the set.
  3. LinkedHashSet stores elements in the order in which elements are inserted i.e it maintains the insertion order.

Example of LinkedHashSet class

import java.util.*;
class LinkedHashSetDemo
{
 public static void main(String args[])
 {
  LinkedHashSet< String> hs = new LinkedHashSet< String>();
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  System.out.println(hs);
 }
}

[B, A, D, E, C, F]


TreeSet Class

  1. It extends AbstractSet class and implements the NavigableSet interface.
  2. It stores the elements in ascending order.
  3. It uses a Tree structure to store elements.
  4. It contains unique elements only like HashSet.
  5. It's access and retrieval times are quite fast.
  6. It has four Constructors.
  7. TreeSet()  //It creates an empty tree set that will be sorted in an ascending order according to the
    natural order of the tree set
    
    TreeSet( Collection C )  //It creates a new tree set that contains the elements of the Collection C
    
    TreeSet( Comparator comp )  //It creates an empty tree set that will be sorted according to given Comparator
    
    TreeSet( SortedSet ss )  //It creates a TreeSet that contains the elements of given SortedSet
    

Example of TreeSet class

import java.util.*;
class TestCollection11{
 public static void main(String args[]){
   TreeSet<String> al=new TreeSet<String>();
   al.add("Ravi");
   al.add("Vijay");
  al.add("Ravi");
  al.add("Ajay");

  Iterator itr=al.iterator();
  while(itr.hasNext()){
   System.out.println(itr.next());
  }
 }
}

Ajay Ravi Vijay


PriorityQueue Class

  1. It extends the AbstractQueue class.
  2. The PriorityQueue class provides the facility of using queue.
  3. It does not orders the elements in FIFO manner.
  4. PriorityQueue has six constructors. In all cases, the capacity grows automatically as elements are added.
    PriorityQueue( )  //This constructor creates an empty queue. By default, its starting capacity is 11
    
    PriorityQueue(int capacity) //This constructor creates a queue that has the specified initial capacity
    
    PriorityQueue(int capacity, Comparator comp) //This constructor creates a queue with the specified capacity
    and comparator
    
    //The last three constructors create queues that are initialized with elements of Collection passed in c
    PriorityQueue(Collection c)
    
    PriorityQueue(PriorityQueue c)
    
    PriorityQueue(SortedSet c)

Note: If no comparator is specified when a PriorityQueue is constructed, then the default comparator for the type of data stored in the queue is used. The default comparator will order the queue in ascending order. Thus, the head of the queue will be the smallest value. However, by providing a custom comparator, you can specify a different ordering scheme.

Note: Although you can iterate through a PriorityQueue using an iterator, the order of that iteration is undefined. To properly use a PriorityQueue, you must call methods such as offer( ) and poll( ), which are defined by the Queue interface.


Example of PriorityQueue class

import java.util.*;

class StudyTonight
{
public static void main(String args[])
{
  PriorityQueue<String> queue=new PriorityQueue<String>();
  queue.add("WE");
  queue.add("LOVE");
  queue.add("STUDY");
  queue.add("TONIGHT");
  System.out.println("At head of the queue:"+queue.element());
  System.out.println("At head of the queue:"+queue.peek());
  System.out.println("Iterating the queue elements:");
  Iterator itr=queue.iterator();
  while(itr.hasNext()){
    System.out.println(itr.next());
  }
  queue.remove();
  queue.poll();
  System.out.println("After removing two elements:");
  Iterator itr2=queue.iterator();
  while(itr2.hasNext()){
    System.out.println(itr2.next());
  }
}
}

At head of the queue:LOVE At head of the queue:LOVE Iterating the queue elements: LOVE TONIGHT STUDY WE After removing two elements: TONIGHT WE