Collections - Java

Introduction to Collections

A collection sometimes called a container is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers). If you have used the Java programming language or just about any other programming language you are already familiar with collections.

What Is a Collections Framework?

A collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:
    Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.
    Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.
    Algorithms: These are the methods that perform useful computations, such as searching and sorting, on objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.

Benefits of the Java Collections Framework

The Java Collections Framework provides the following benefits:

Reduces programming effort: By providing useful data structures and algorithms, the Collections Framework frees you to concentrate on the important parts of your program rather than on the low-level "plumbing" required to make it work. By facilitating interoperability among unrelated APIs, the Java Collections Framework frees you from writing adapter objects or conversion code to connect APIs.
Increases program speed and quality: This Collections Framework provides high-performance, high-quality implementations of useful data structures and algorithms. The various implementations of each interface are interchangeable, so programs can be easily tuned by switching collection implementations. Because you're freed from the drudgery of writing your own data structures, you'll have more time to devote to improving programs' quality and performance.
Allows interoperability among unrelated APIs: The collection interfaces are the vernacular by which APIs pass collections back and forth. If my network administration API furnishes a collection of node names and if your GUI toolkit expects a collection of column headings, our APIs will interoperate seamlessly, even though they were written independently.
Reduces effort to learn and to use new APIs: Many APIs naturally take collections on input and furnish them as output. In the past, each such API had a small sub-API devoted to manipulating its collections. There was little consistency among these ad hoc collections sub-APIs, so you had to learn each one from scratch, and it was easy to make mistakes when using them. With the advent of standard collection interfaces, the problem went away.
Reduces effort to design new APIs: This is the flip side of the previous advantage. Designers and implementers don't have to reinvent the wheel each time they create an API that relies on collections; instead, they can use standard collection interfaces.
Fosters software reuse: New data structures that conform to the standard collection interfaces are by nature reusable. The same goes for new algorithms that operate on objects that implement these interfaces.

The core collection interfaces encapsulate different types of collections, which are shown in the figure below. These interfaces allow collections to be manipulated independently of the details of their representation. Core collection interfaces are the foundation of the Java Collections Framework. As you can see in the following figure, the core collection interfaces form a hierarchy.

The Collection interface provides support for the implementation of a mathematical bag - an unordered collection of objects that may contain duplicates.
HashTable : Whenever a program wants to store a key value pair, one can use Hashtable.
Set : The Set interface provides methods for accessing the elements of a finite mathematical set. Sets do not allow duplicate elements.

Implements Collection Interface
Does not allow duplicate
EnumSet (classes)
HashSet (classes) : HashSet uses map to store. It stores element as KEY and "PRESENT" object as VALUE.
Sortedset (Interface)

Ascending order
Does not allow duplicate
TreeSet (classes)
LinkedHashSet (classes)

List : The List interface provides support for ordered collections of objects.

Implement collection Interface
Can contain duplicate and it’s ordered
Stack class implements list interface
Linked List class implements list interface
Vector (classes) - Syncronized : The Vector class provides the capability to implement a growable array of objects.Yes a Vector can contain heterogenous objects. Because a Vector stores everything in terms of Object.
ArrayList (classes) - nonsynchronized . Yes a ArrayList can contain heterogenous objects. Because a ArrayList stores everything in terms of Object.
The basic difference between a Vector and an ArrayList is that, vector is synchronized while ArrayList is not. Thus whenever there is a possibility of multiple threads accessing the same instance, one should use Vector. While if not multiple threads are going to access the same instance then use ArrayList. Non synchronized data structure will give better performance than the synchronized one.
How to sort list in reverse order?How to sort list in reverse order?

This question is just like above to test your knowledge of Collections utility class. Use it reverse() method to reverse the list.
List reversedList = Collections.reverse(list);

Queue
De-queue:
Map: Map interface is a special type of collection which is used to store key-value pairs. It does not extend Collection interface for this reason.Main classes implementing Map interface are:

HashMap,
Hashtable,
EnumMap,
IdentityHashMap,
LinkedHashMap,
Properties.

When to use HashMap or TreeMap?

TreeMap is special form of HashMap. It maintains the ordering of keys which is missing in HashMap class. This ordering is by default “natural ordering”. The default ordering can be override by providing an instance of Comparator class, whose compare method will be used to maintain ordering of keys.

SortedMap :

To remember :
Legacy collection frame works are Synchronized:

Vector
stack
dictionary
hashTable
Properties

New collection framework are not synchronized:

LinkedList
ArrayList
HashSet
TreeSet
HashMap
TreeMap

-----------------------------------------------------------------------------------------------------------------------------------------------------------

Some famous repeated interview questions :

Difference between Set and List?

The most noticeable differences are :

Set is unordered collection where List is ordered collection based on zero based index.
List allow duplicate elements but Set does not allow duplicates.
List does not prevent inserting null elements (as many you like), but Set will allow only one null element.

Difference between List and Map?
Perhaps most easy question. List is collection of elements where as map is collection of key-value pairs. There is actually lots of differences which originate from first statement. They have separate top level interface, separate set of generic methods, different supported methods and different views of collection.
I will take much time hear as answer to this question is enough as first difference only.
Difference between HashMap and HashTable?
There are several differences between HashMap and Hashtable in Java:

Hashtable is synchronized, whereas HashMap is not.
Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.
The third significant difference between HashMap vs Hashtable is that Iterator in the HashMap is a fail-fast iterator while the enumerator for the Hashtable is not.

Difference between Vector and ArrayList?
Lets note down the differences:

All the methods of Vector is synchronized. But, the methods of ArrayList is not synchronized.
Vector is a Legacy class added in first release of JDK. ArrayList was part of JDK 1.2, when collection framework was introduced in java.
By default, Vector doubles the size of its array when it is re-sized internally. But, ArrayList increases by half of its size when it is re-sized.

Difference between Iterator and Enumeration?
Iterators differ from enumerations in three ways:

Iterators allow the caller to remove elements from the underlying collection during the iteration with its remove() method. You can not add/remove elements from a collection when using enumerator.
Enumeration is available in legacy classes i.e Vector/Stack etc. whereas Iterator is available in all modern collection classes.
Another minor difference is that Iterator has improved method names e.g. Enumeration.hasMoreElement() has become Iterator.hasNext(), Enumeration.nextElement() has become Iterator.next() etc.

Difference between HashMap and HashSet?
HashMap is collection of key-value pairs whereas HashSet is un-ordered collection of unique elements. That’s it. No need to describe further.
Difference between Iterator and ListIterator?
There are three Differences are there:

We can use Iterator to traverse Set and List and also Map type of Objects. But List Iterator can be used to traverse for List type Objects, but not for Set type of Objects.
By using Iterator we can retrieve the elements from Collection Object in forward direction only whereas List Iterator, which allows you to traverse in either directions using hasPrevious() and previous() methods.
ListIterator allows you modify the list using add() remove() methods. Using Iterator you can not add, only remove the elements.

Difference between TreeSet and SortedSet?
SortedSet is an interface which TreeSet implements. That’ it !!
Difference between ArrayList and LinkedList?

LinkedList store elements within a doubly-linked list data structure. ArrayList store elements within a dynamically resizing array.
LinkedList allows for constant-time insertions or removals, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list. ArrayLists, on the other hand, allow random 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.
LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.

Reference : [1] [2]