Java Technology - 2018 - Java Collection
Collection:
ArrayList is implemented as a resizable array. As more elements are added to ArrayList, its size is increased dynamically. It's elements can be accessed directly by using the get and set methods, since ArrayList is essentially an array.
LinkedList is implemented as a double linked list. Its performance on add and remove is better than Arraylist, but worse on get and set methods.
Vector is similar with ArrayList, but it is synchronized.
Collections in java is a framework that provides an architecture to store and manipulate the group of objects.
All the operations that you perform on a data such as searching, sorting, insertion, manipulation, deletion etc. can be performed by Java Collections.
Java Collection simply means a single unit of objects. Java Collection framework provides many interfaces (Set, List, Queue, Deque etc.) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet etc).
What is Collection in java
Collection represents a single unit of objects i.e. a group.
What is framework in java
- provides readymade architecture.
- represents set of classes and interface.
- is optional.
What is Collection framework
Collection framework represents a unified architecture for storing and manipulating group of objects. It has:
- Interfaces and its implementations i.e. classes
- Algorithm
Hierarchy of Collection Framework
Let us see the hierarchy of collection framework.The java.util package contains all the classes and interfaces for Collection framework.
Iterator interface
Iterator interface provides the facility of iterating the elements in forward direction only.
Methods of Iterator interface
There are only three methods in the Iterator interface. They are:
No. Method Description
1 public boolean hasNext() It returns true if iterator has more elements.
2 public Object next() It returns the element and moves the cursor pointer to the next element.
3 public void remove() It removes the last elements returned by the iterator. It is rarely used.
ArrayList
Java ArrayList class uses a dynamic array for storing the elements. It inherits AbstractList class and implements List interface.
The important points about Java ArrayList class are:
- Java ArrayList class can contain duplicate elements.
- Java ArrayList class maintains insertion order.
- Java ArrayList class is non synchronized.
- Java ArrayList allows random access because array works at the index basis.
- In Java ArrayList class, manipulation is slow because a lot of shifting needs to be occurred if any element is removed from the array list.
Hierarchy of ArrayList class
Methods of Java ArrayList
Method Description
void add(int index, Object element) It is used to insert the specified element at the specified position index in a list.
boolean addAll(Collection c) It is used to append all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
void clear() It is used to remove all of the elements from this list.
int lastIndexOf(Object o) It is used to return the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
Object[] toArray() It is used to return an array containing all of the elements in this list in the correct order.
Object[] toArray(Object[] a) It is used to return an array containing all of the elements in this list in the correct order.
boolean add(Object o) It is used to append the specified element to the end of a list.
boolean addAll(int index, Collection c) It is used to insert all of the elements in the specified collection into this list, starting at the specified position.
Object clone() It is used to return a shallow copy of an ArrayList.
int indexOf(Object o) It is used to return the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.
void trimToSize() It is used to trim the capacity of this ArrayList instance to be the list's current size.
ArrayList<String> al=new ArrayList<String>();//creating new generic arraylist
In generic collection, we specify the type in angular braces. Now ArrayList is forced to have only specified type of objects in it. If you try to add another type of object, it gives compile time error.
package com.practice.arraylistpractice;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class ArrayListPractice1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Ram");
list.add("Shyam");
list.add("David");
for (String ii : list) {
System.out.println(ii);
}
ArrayList<String> list1 = new ArrayList<String>();
list1.add("James");
list1.add("Walker");
list.addAll(list1);
for (String ii : list) {
System.out.println(ii);
}
System.out.println(list.contains("Ram"));
list.remove("Ram");
System.out.println(list.contains("Ram"));
Iterator itrlist = list.iterator();
while (itrlist.hasNext()) {
System.out.println(itrlist.next());
}
System.out.println("=---------------------");
Iterator itrlist1 = list1.iterator();
while (itrlist1.hasNext()) {
System.out.println(itrlist1.next());
}
System.out.println("______________________");
System.out.println("Convert ArrayList to Arrays");
String[] str = list1.toArray(new String[list1.size()]);
for (String ii : str) {
System.out.println(ii);
}
System.out.println("______________________");
for (int i = 0; i < str.length; i++) {
System.out.println(str[i]);
}
System.out.println("______________________");
System.out.println("Convert Array to ArrayList");
List<String> list2 = new ArrayList<String>(Arrays.asList(str));
for (String ii : list2) {
System.out.println(ii);
}
}
}
-----------------------------------
package com.practice.arraylistpractice;
public class ArrayListClass {
private String firstName;
private String lastName;
private int id;
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public ArrayListClass() {
}
public ArrayListClass(String firstName, String lastName, int id) {
this.firstName = firstName;
this.lastName = lastName;
this.id = id;
}
@Override
public String toString() {
return "ArrayListClass [firstName=" + firstName + ", lastName="
+ lastName + ", id=" + id + "]";
}
}
package com.practice.arraylistpractice;
import java.util.ArrayList;
public class ArrayListClassImpl {
public static void main(String[] args) {
ArrayList<ArrayListClass> list = new ArrayList<ArrayListClass>();
ArrayListClass obj1 = new ArrayListClass(); // default constructor
// use setter method
obj1.setFirstName("Mandip");
obj1.setLastName("Shrestha");
obj1.setId(1);
// use parameterized constructor
ArrayListClass obj2 = new ArrayListClass("Ram", "Kumar", 5);
list.add(obj1);
list.add(obj2);
System.out.println(list);
// [ArrayListClass [firstName=Mandip, lastName=Shrestha, id=1],
// ArrayListClass [firstName=Ram, lastName=Kumar, id=5]]
for (ArrayListClass ii : list) {
System.out.println(ii.getFirstName() + " " + ii.getLastName() + " "
+ ii.getId());
}
// Mandip Shrestha 1
// Ram Kumar 5
System.out.println(obj1);
// ArrayListClass [firstName=Mandip, lastName=Shrestha, id=1]
}
}
---------------------------------------
Difference between arraylist and linkedList
When should i use arrayList and when should I go for LinkedList?
Arraylist maintain indices like arrays. So if want more frequent get operations than put then arraylist is best to go.
LinkedList maintain pointers to elements. you can't to a specific index like in arraylist. But the advantage here in linkedlist is that they don't need to shift back and forth like in arraylist to maintain continues indices. So get operations in linkedlist are costly as you would have to go through pointers to reach your elements. But put operations are good as compared to arraylist. you just need to connect to pointers and that's it.
When should I use TreeSet, LinkedHashSet and HashSet?
the difference is only in ordering. treeset elements need to maintain a specific orders defined by your member objects.
--------
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.
As with standard linked list and array operations, the various methods will have different algorithmic runtimes.
For LinkedList<E>
get(int index) is O(n/4) average
add(E element) is O(1)
add(int index, E element) is O(n/4) average
but O(1) when index = 0 <--- main benefit of LinkedList<E>
remove(int index) is O(n/4) average
Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>
Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)
For ArrayList<E>
get(int index) is O(1) <--- main benefit of ArrayList<E>
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n/2) average
remove(int index) is O(n/2) average
Iterator.remove() is O(n/2) average
ListIterator.add(E element) is O(n/2) average
Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)
LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n/4) on average, though O(1) for index = 0.
ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)
The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n/2) for worst case, whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).
Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.
Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.
The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.
-----------
Linked lists are preferable over arrays when:
a) you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
b) you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
c) you don't need random access to any elements
d) you want to be able to insert items in the middle of the list (such as a priority queue)
Arrays are preferable when:
a) you need indexed/random access to elements
b) you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array
c) you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
d) memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list.
Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re-shuffling elements around. Performance-wise, arraylists are slower than raw arrays.
---------------------
Example of ListIterator Interface
import java.util.*;
public class TestCollection8{
public static void main(String args[]){
ArrayList<String> al=new ArrayList<String>();
al.add("Amit");
al.add("Vijay");
al.add("Kumar");
al.add(1,"Sachin");
System.out.println("element at 2nd position: "+al.get(2));
ListIterator<String> itr=al.listIterator();
System.out.println("traversing elements in forward direction...");
while(itr.hasNext()){
System.out.println(itr.next());
}
System.out.println("traversing elements in backward direction...");
while(itr.hasPrevious()){
System.out.println(itr.previous());
}
}
}
------------
package com.practice.hashsetpractice;
import java.util.HashSet;
import java.util.LinkedHashSet;
public class HashSetPractice1 {
public static void main(String[] args) {
HashSet<String> set = new HashSet<String>();
set.add("A");
set.add("E");
set.add("C");
set.add("B");
set.add("a");
set.add("B");
for (String ii : set) {
System.out.println(ii);
}
System.out.println(set); //[A, a, B, C, E]
System.out.println("__________________");
LinkedHashSet<String> set1 = new LinkedHashSet<String>();
set1.add("A");
set1.add("E");
set1.add("C");
set1.add("B");
set1.add("a");
set1.add("B");
for (String ii : set1) {
System.out.println(ii);
}
System.out.println(set1); //[A, E, C, B, a]
}
}
---------------
HashSet vs TreeSet
HashSet is faster than TreeSet which means if you need performance use HashSet but HashSet doesn't provide any kind of ordering so if you need ordering then you need to switch to TreeSet which provides sorting of keys.
1)Both HashSet and TreeSet implements java.util.Set interface which means they follow contract of Set interface and doesn't allow any duplicates.
Second difference between HashSet and TreeSet is that HashSet allows null object but TreeSet doesn't allow null Object and throw NullPointerException, Why, because TreeSet uses compareTo() method to compare keys and compareTo() will throw java.lang.NullPointerException
Another significant difference between HashSet and TreeSet is that HashSet is backed by HashMap while TreeSet is backed by TreeMap in Java.
Another significant difference between HashSet and TreeSet is that HashSet is backed by HashMap while TreeSet is backed by TreeMap in Java.
Now the most important difference between HashSet and TreeSet is ordering. HashSet doesn't guarantee any order while TreeSet maintains objects in the Sorted order defined by either Comparable or Comparator method in Java.
HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.
HashSet
- class offers constant time performance for the basic operations (add, remove, contains and size).
- it does not guarantee that the order of elements will remain constant over time
- iteration performance depends on the initial capacity and the load factor of the HashSet.
- It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.
TreeSet
- guarantees log(n) time cost for the basic operations (add, remove and contains)
- guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements
SortedSet) - doesn't offer any tuning parameters for iteration performance
- offers a few handy methods to deal with the ordered set like
first(),last(),headSet(), andtailSet()etc
Important points:
- Both guarantee duplicate-free collection of elements
- It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
- None of these implementation are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
- LinkedHashSet is in some sense intermediate between
HashSetandTreeSet. Implemented as a hash table with a linked list running through it, however it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.
So choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.
- e.g.
SortedSet<String> s = new TreeSet<String>(hashSet);
2. HashSet vs. TreeSet vs. LinkedHashSet
HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, and contains methods has constant time complexity O(1). TreeSet is implemented using a tree structure(red-black tree in algorithm book). The elements in a set are sorted, but the add, remove, and contains methods has time complexity of O(log (n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet(), etc. LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1).
ArrayList vs. LinkedList vs. Vector
From the hierarchy diagram, they all implement List interface. They are very similar to use. Their main difference is their implementation which causes different performance for different operations.
ArrayList is a better choice if your program is thread-safe. Vector and ArrayList require more space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time. LinkedList, however, also implements Queue interface which adds more methods than ArrayList and Vector, such as offer(), peek(), poll(), etc.
Note: The default initial capacity of an ArrayList is pretty small. It is a good habit to construct the ArrayList with a higher initial capacity. This can avoid the resizing cost.
HashMap:
Java HashMap class implements the map interface by using a hashtable. It inherits AbstractMap class and implements Map interface.
The important points about Java HashMap class are:
- A HashMap contains values based on the key.
- It contains only unique elements.
- It may have one null key and multiple null values.
- It maintains no order.
package com.practice.hashandtreepracticecopy;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
public class HashMapPractice {
// no ordering of keys and value
public static void main(String[] args) {
HashMap<String, Integer> myMap = new HashMap<String, Integer>();
myMap.put("apple", 15);
myMap.put("apple", 22);
myMap.put("cat", 3);
myMap.put("zebra", 100);
myMap.put("cat", 32);
myMap.put("dog", 42);
for (String str : myMap.keySet()) {
System.out.println(str);
}
for (Integer val : myMap.values()) {
System.out.println(val);
}
Set<String> mySet = myMap.keySet();
Iterator<String> itr = mySet.iterator();
while (itr.hasNext()) {
String myKeys = (String) itr.next();
System.out.println(myKeys + " " + myMap.get(myKeys));
}
}
}
zebra
apple
cat
dog
100
22
32
42
zebra 100
apple 22
cat 32
dog 42
---------------------------------------------
package com.practice.hashandtreepracticecopy;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;
public class LinkedHashMapPractice {
// Preserve the insertion order
public static void main(String[] args) {
LinkedHashMap<String, Integer> myMap = new LinkedHashMap<String, Integer>();
myMap.put("apple", 15);
myMap.put("apple", 22);
myMap.put("cat", 300);
myMap.put("zebra", 100);
myMap.put("cat", 32);
myMap.put("dog", 42);
for (String str : myMap.keySet()) {
System.out.println(str);
}
for (Integer val : myMap.values()) {
System.out.println(val);
}
Set<String> mySet = myMap.keySet();
Iterator itr = mySet.iterator();
while (itr.hasNext()) {
String myKeys = (String) itr.next();
System.out.println(myKeys + " " + myMap.get(myKeys));
}
}
}
apple
cat
zebra
dog
22
32
100
42
apple 22
cat 32
zebra 100
dog 42
----------------------------------------------
Java TreeMap
Java TreeMap class implements the Map interface by using a tree. It provides an efficient means of storing key/value pairs in sorted order.
The important points about Java TreeMap class are:
- A TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
- It contains only unique elements.
- It cannot have null key but can have multiple null values.
- It is same as HashMap instead maintains ascending order.
import java.util.*;
class TestCollection15{
public static void main(String args[]){
TreeMap<Integer,String> hm=new TreeMap<Integer,String>();
hm.put(100,"Amit");
hm.put(102,"Ravi");
hm.put(101,"Vijay");
hm.put(103,"Rahul");
for(Map.Entry m:hm.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
}
}
Output:100 Amit
101 Vijay
102 Ravi
103 Rahul
What is difference between HashMap and TreeMap? HashMap TreeMap 1) HashMap can contain one null key. TreeMap can not contain any null key. 2) HashMap maintains no order. TreeMap maintains ascending order.
----------------------------
package com.practice.hashandtreepracticecopy;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class TreeMapPractice {
// TreeMap ordered by Keys
public static void main(String[] args) {
TreeMap<String, Integer> myMap = new TreeMap<String, Integer>();
myMap.put("apple", 15);
myMap.put("apple", 22);
myMap.put("cat", 3);
myMap.put("zebra", 100);
myMap.put("elephant", 32);
myMap.put("dog", 42);
for (String str : myMap.keySet()) {
System.out.println(str);
}
for (Integer val : myMap.values()) {
System.out.println(val);
}
Set<String> mySet = myMap.keySet();
Iterator itr = mySet.iterator();
while (itr.hasNext()) {
String myKeys = (String) itr.next();
System.out.println(myKeys + " " + myMap.get(myKeys));
}
}
}
apple
cat
dog
elephant
zebra
22
3
42
32
100
apple 22
cat 3
dog 42
elephant 32
zebra 100
-------------------------------
Java Collections
Java collection class is used exclusively with static methods that operate on or return collections.
import java.util.*;
public class CollectionsExample {
public static void main(String a[]){
List<String> list = new ArrayList<String>();
list.add("C");
list.add("Core Java");
list.add("Advance Java");
System.out.println("Initial collection value:"+list);
Collections.addAll(list, "Servlet","JSP");
System.out.println("After adding elements collection value:"+list);
String[] strArr = {"C#", ".Net"};
Collections.addAll(list, strArr);
System.out.println("After adding array collection value:"+list);
}
}
Output:
Initial collection value:[C, Core Java, Advance Java]
After adding elements collection value:[C, Core Java, Advance Java, Servlet, JSP]
After adding array collection value:[C, Core Java, Advance Java, Servlet, JSP, C#, .Net]
Java Collections Example: max()
import java.util.*;
public class CollectionsExample {
public static void main(String a[]){
List<Integer> list = new ArrayList<Integer>();
list.add(46);
list.add(67);
list.add(24);
list.add(16);
list.add(8);
list.add(12);
System.out.println("Value of maximum element from the collection: "+Collections.max(list));
}
}
Output:
Value of maximum element from the collection: 67
import java.util.*;
public class CollectionsExample {
public static void main(String a[]){
List<Integer> list = new ArrayList<Integer>();
list.add(46);
list.add(67);
list.add(24);
list.add(16);
list.add(8);
list.add(12);
System.out.println("Value of maximum element from the collection: "+Collections.max(list));
}
}
Output:
Value of maximum element from the collection: 67
Comments
Post a Comment