Collections in java

If we want to represent a group of individual objects as a single entity then we should go for collection. In general collection interface is consider as root interface of collection framework but there is no concrete class which implements collection interface directly.

List(I)

1. The list is child interface if the collection
2. If we want to represent a group of objects as a single entity such that duplicates are allowed and insertion order must be preserved
3. Common methods in a list interface

=>void add(int index,Object o)

=>Object get(int index)

=>Object set(int index, new Object) — replace object present in that index and return old object

=>Object remove(int index)

Array List

1. ArrayList is one of the implementation class of List interface and it is a growable array.
2. Heterogenous object and null insertion are allowed.
3. constructors for array list
4. ArrayList is the best option if our frequent operation is retrieval operation, we should go for ArrayList if our frequent operation is insertion and deletion in the middle

=>ArrayList l=new ArrayList

=>ArrayList l=new ArrayList(int initial capacity) — creates a empty arraylist with specified capacity

=>ArrayList l=new ArrayList(Collection c) — creates ann araylist for given collection

Linked List

1. The underlying data structure is double LinkedList
2. Duplicate and heterogeneous objects are allowed
3. LinkedList is the best choice if our frequent operation is insertion and deletion

Constructors

LinkedList l=new LinkedList();

LinkedList l=new LinkedList(Collection c); — creates a equivalent linked list for passed collection.

LinkedList specific methiods

void addFirst(Object o)

void addLast(Object o)

Object getFirst(Object o)

Object getLast(Object o)

Object removeFirst()

Object removeLast()

Vectors

1. Vectors are very similar to ArrayList but every method present in the vector is synchronized
2. At a time only one thread is allowed to operate on vector and hence it is a thread-safe and relative performance in low.
3. Vector is introduced in 1.0 v it is legacy class.

Constructors

a)Vector v=new Vector() — creates an empty object with default initial capacity 10, once vector reaches its max capacity then a new vector is created with current capacity*2.

b) Vector v=new Vector(int initial capacity)

c)Vector v=new Vector(int initial capacity, int incrementCapacity) — new vector is created when the vector is filled up to its increment capacity

d)Vector v=new Vector(Collection c)

Stack

It is the child class of vector, this class is designed for LIFO order

Constructor: Stack s=new Stack();

specific methods for stack:

Object push(Object o) —insert an object in the stack

Object pop() — remove and return top of the stack

Object peek() — return top of the stack without removal

boolean empty() — return true if stack is empty

Which List implementation class should be used for different operations:

a)Insertion at last index: Both LinkedList and ArrayList has same time complexity O(1) but LinkedList is preferred because in case of ArrayList first it will check if the array is full, if it is full then it will create a new array double size of the present array and copy all value, but LinkedList displace some pointers to do so, Therefore LinkedList is prefered.

b)Insertion value in the given index: Here also both of them has same time complexity O(n), but LinkedList is preferred because of the same reason above in point (a) of this section.

c)Search by value: Here also both have the same time complexity of O(n) but ArrayList‘s data structure is a growable array and array elements are stored in continuous memory location but linkedList’s underlying data structure is double LinkedList as nodes are created in random location Therefore ArrayList is preferred for this because iterating through continuous memory locations efficient than iterating through random memory location.

d)Get element by index: Here ArrayList is preferred because it implements random access interface with O(1) but in case of linkedList we need to iterate all element O(n).

e)Remove by value: For LinkedList and ArrayList we need to iterate through all nodes O(n) but in case of ArrayList we need to displace all elements after it but for LinkedList, we need to displace pointers. Therefore LinkedList is prefered.

d)Remove by index: ArrayList and linked list both can take O(n) but using random access ArrayList can reach to that index and after deletion, we need to displace all elements after that but in case of LinkedList, we just need to iterate and displace some pointers in the destination. so LinkedList is prefered as displacing all elements is not a good option in performance-wise.

The 3 cursours in java

1. Enumeration
2. Iterator
3. List Iterator

Enumeration

Enumeration is used to get object one by one from legacy collection Object

we can create enumeration object by using elements() method of vector class

eg: Vector v=new Vector();

Enumeration e=v.elements();

Methods

public boolean hasMoreElements(); — if more elements are present in vector

public Object nextElements(); —get the next element

limitation of enumeration

a)we can apply this concept only for legacy classes ie: this is not a universal cursor

b)by using enumeration we can get only read access and we can not perform removal operation.

2)Iterator

we can apply iterator concept for any type of collection objects and hence it is universal cursor. By using this we can perform both read and removal operation

we can create iterator object using iterator method of collection interface

Iterator itr=c.iterator() — where cis collection

Methods

1. public boolean hasNext()
2. public Object next()
3. public void remove()

Limitations of iterator

1. By using Iterator we can always move only towards the forward direction and we can’t move in backward direction
2. By using iterator we can perform only read and remove operations and we can’t perform replacement and addition operation

List Iterator

By using list Iterator we can move forward as well as backward direction. We can also perform the replacement and addition of new objects.

we can create list Iterator by using ListIteratir method of list Interface.

eg: ListIterator itr=l.listIterator(); — -where l is list object

Limitation of listIterator

List Iterator can only be used only with list objects only.

SET(I)

Set is a child interface of collection if we want to represent a group of individual objects as a single entity, where duplicates are not allowed and insertion order not preserved.

HashSet

1. This is an implementation class of set interface
2. Duplicate objects are not allowed and insertion order is not preserved
3. null insertion is possible and Heterogenous object is allowed
4. In HashSet duplicates, objects are not allowed, if we are trying to insert duplicate object then add() method return false.
5. Here hashTable data structure in use, therefore, insertion, removal, lookup operations operation takes O(1).

Constructors

HashSet h=new HashSet();

HashSet h=new HashSet(int initial capacity);

HashSet h=new HashSet(Collection c);

HashSet h=new HashSet(int initial capacity,float fillratio);

LinkedHashSet

Its is child class of HashSet, it is exactly same as HashSet including constructor snd method but here insertion order is preserved.

It is a combination of LinkedList and HashTable, therefore insertion, removal, lookup operations operation takes O(1).

Shorted Set(I)

Is the child interface of the set, if we want to represent a group of the individual object according to some shorting order without duplicates then we should go for the shorted set.

As its implementing data structure is

Methods

a) Object first() — return the first element of the shorted set

b) Object last() — return the last element of the shorted set

c)SortedSet headSet(object obj) — return shorted set whose set is less than the object

d)ShortedSet tailSet(Object obj) — return shorted set whose elements are greater than equal to the object.

Comparable interface(I)

This is present in java.lang package and it contains only one method

public int compareTo(Object obj)

obj1.compareTo(obj2) — return negative value if obj1 come before obj2

return positive value if obj1 come after obj2

return 0 if obj1 and obj2 are equal

JVM internally use comparable interface compareTo() method for default shorting.

Comparator(I)

Comparator present in java. util package and it defines two methods

a)compare()

b)equals()

whenever we are implementing comparator interface, compulsory we should provide implementation only for compare method and we are not required to provide the implementation for the equals method because it is already available to our class from obj. class through inheritance.

compare(obj1,obj2) — return a negative value if obj1 come before obj2

— return positive value if obj1 come after obj2

— return 0 if obj1 and obj2 are equal

we can customize which element should come before or after by returning any positive value for obj 1 come before obj2 vice versa.

Comparable vs comparator

1. For predefined comparable class-default natural sorting order already available, if we are not satisfied with that default natural sorting order then we can define our own shorting by using a comparator.
2. For predefined non-comparable class (string buffer) default natural sorting order not available, we can define our own shorting using comparator.

Tree set

Insertion order is not preserved and heterogeneous objects are not allowed. In TreeSet all objects are inserted based on some shorting order natural or customized order. Internally it uses Red-black tree therefore add, remove, next time complexity is O(log n) and to check if an object is present in tree will take O(1).

Queue Interface

1. Boolean offer(Object o) — to add an object into the queue
2. Object peek() — to return head element of the queue, if the queue is empty then this method gives exception
3. Object element() — To remove the head element of the queue, if the queue is empty then this method return null
4. Object poll() — to remove and return the head element of the queue. If the queue is empty then this method return null.
5. Object remove() — to remove and return the head element of the queue. If the queue is empty then this method raise runtime exception.

Priority Queue

1. If we want to represent a group of individual Objects, prior to processing according to some priority then we should go for priority Queue.
2. The Priority can be either default natural sorting order or customized sorting order defined by the comparator.
3. Insertion order is not preserved and it is based on some priority and duplicate objects are not allowed
4. If we are depending on default sorting then compulsory elements should be homogenous and comparable.
5. Null insertion is not allowed.
6. offer() -O(log n),peak()-O(1),poll-O(log n),remove-O(n)

Map(I)

1. Map is not a child interface of collection, If we want to represent a group of objects as key-value pairs then we should go for map.
2. Both keys and values are objects only
3. duplicate keys are not allowed but values can be duplicated
4. Each key-value pair is called entry, hence map is considered as a collection of entry obj.

Method

Object put(Object key, Object value)

void get(Object Key)

boolean containsKey(Object key)

boolean isEmpty()

object remove(Object Key) — remove the entry associated with specified key

Entry(I)

A map is a group of Key value pair and each key-value pair is called an entry, Hence map is considered as a collection of entry objects.

Object getKey()

Object getValue()

HashMap

1. The underlying data Structure is hashTable
2. Insertion order is not preserved and it is based on the hash code of keys
3. Duplicate keys are not allowed but values can be duplicated
4. Heterogenous Object is allowed for key and values
5. Null is allowed for the key (only once) and null is allowed as a value for multiple time.
6. get()-O(1),ContainKey()-O(1) as internally use hash table

Constructor

HashMap m=new HashMap();

HashMap m=new HashMap(int initial capacity);

HashMap m=new HashMap(int initial capacity, float filled ratio);

HashMap m=new HashMap(Map m);

Linked Hashmap

It is child class of hashmap, it is exactly same as hashmap(including methods and constructors) but here insertion order is preserved, and it is based on Linked list and hash table.

get()-O(1),ContainKey()-O(1) as internally use hash table and Linked list

IdentityHashMap

It is exactly same as Hashmap except for the following difference, in the case of normal Hashmap JVM will use .equals method to identify duplicate Keys, which is meant for context comparison, but in case of Identity, HashMap JVM will use == operator to identify duplicate key which is meant for reference comparison.

Time complexity for method: get()-O(1),ContainKey()-O(1)

Sorted Map(I)

It is the child Interface of Map if we want to represent a group of Key-Value pairs according to some sorting order of keys, then we should go for a sorted map.

Methods

1. Object firstKey()
2. Object LastKey()
3. SortedMap headMap(Object Key)
4. SortedMap tailMap(Object Key)

Weak HashMap

In the case of hashMap keys are object and if it doesn't has any references then they are not eligible for garbage collection, but in the case of weak hashmap it is completely opposite.

time complexity for method: get()-O(1),ContainKey()-O(1)

TreeMap

This is the implementation class of a sorted map, the data structure used is a red-black tree. Insertion order is not preserved and it is based on some shorting order of keys and with its corresponding values.

Time complexity for method: get()-O(log n),ContainKey()-O(log n)