Collections Framework

Collections Framework

Abstract Classes and Interfaces

Iterable  - A class implementing this interface can be used for iterating with a for each statement.

Collection  - Common base interface for classes in the collection hierarchy. When you want to write methods that are very general, you can pass the Collection interface.

List  - Base interface for containers that store a sequence of elements. You can access the elements using an index, and retrieve the same element later You can store duplicate elements in a List.

Set, SortedSet, NavigableSet Queue, Deque -  Interfaces for containers that don’t allow duplicate elements. SortedSet maintains the set elements in a sorted order. NavigableSet allows searching the set for the closest matches.

Queue - is a base interface for containers that holds a sequence of elements for processing. For example, the classes implementing Queue can be LIFO or FIFO . In a Deque you can insert or remove elements from both the ends.

Map, SortedMap, NavigableMap - Base class for containers that map keys to values. In SortedMap, the keys are in a sorted order. A NavigableMap allows you to search and return the closest match for given search criteria. Note that Map hierarchy does not extend the Collection interface.

Iterator, ListIterator - You can traverse over the container in the forward direction if a class implements the Iterator interface. You can traverse in both forward and reverse directions if a class implements the ListIterator interface.

The Collection Interface

boolean add(Element elem)  => Adds elem into the underlying container.

void clear()  => Removes all elements from the container.

boolean isEmpty() => Checks whether the container has any elements or not.

Iterator<Element> iterator()  => Returns an Iterator<Element> object for iterating over the container.

boolean remove(Object obj)  => Removes the element if obj is present in the container.

int size()  => Returns the number of elements in the container.

Object[] toArray()  => Returns an array that has all elements in the container.

Concrete Classes

ArrayList  - implemented as a resizable array. Fast to search, but slow to insert or delete. Allows duplicates.

LinkedList - implements a doubly-linked list data structure. Fast to insert or delete elements, but slow for searching elements. 

HashSet - implemented as a hash-table data structure. it does not allow storing duplicate elements. Fast for searching and retrieving elements. It does not maintain any order for stored elements.

TreeSet -  implements a red-black tree data structure. it stores the elements in a sorted order. It uses a

tree data structure to decide where to store or search the elements, and the position is decided

by the sorting order.

HashMap -  implemented as a hash-table data structure. Stores key and value pairs. Uses

hashing for finding a place to search or store a pair. Searching or inserting is very fast. It does

not store the elements in any order.

TreeMap - implemented using a red-black tree data structure.  TreeMap stores the elements in a sorted order. It uses a tree data structure to decide where to store or search for keys, and the position is decided by the sorting order.

PriorityQueue - Internally implemented using heap data structure. A PriorityQueue is for retrieving elements based on priority. Irrespective of the order in which you insert, when you remove the

elements, the highest priority element will be retrieved first.

The Iterator Interface

boolean hasNext()  - Checks if the iterator has more elements to traverse.

E next()  - Moves the iterator to the next element and returns that (next) element.

void remove()  - Removes the last visited element from the underlying container. next() should have been called before calling remove(); otherwise it will throw an IllegalStateException.

List Classes

• ArrayList implements a resizable array, 
• The size of the array is known (fixed) at the time of creation.
• ArrayList is a dynamic array: it can grow in size as required.
• Accessing array elements is very fast in an ArrayList. 
• Add or remove elements, internally the rest of the elements are copied; so addition/deletion of elements is a costly operation.

The ListIterator Interface

The ListIterator interface extends the Iterator interface.

boolean hasPrevious()  - Checks if the iterator has more elements to traverse in reverse direction.

Element previous()  - Moves the iterator to the next element and returns that (next) element in reverse direction.

int nextIndex()  - Returns the index of the next element in the iteration in forward direction.

int previousIndex() - Returns the index of the next element in the iteration in reverse direction.

void set(Element) - Sets the last element visited (using next or previous); it replaces the existing element.

void add(Element) - Adds the element into the list at the current iteration position.

The LinkedList Class

• The LinkedList class internally uses a doubly-linked list. 
• Insertion and deletion is very fast.
• Accessing an element entails traversing the nodes one-by-one, so it is slow.
• When you want to add or remove elements frequently in a list of elements, it is better to use a LinkedList

The Set Interface

Set, contains no duplicates. 

There are two important concrete classes for Set: HashSet and TreeSet. 

A HashSet is for quickly inserting and retrieving elements; it does not maintain any sorting order for the elements it holds. 

A TreeSet stores the elements in a sorted order (and it implements the SortedSet interface).

The Map Interface

A Map stores key and value pairs. The Map interface does not extend the Collection interface.

A HashMap uses a hash table data structure internally. In HashMap, searching (or looking up elements) is a fast operation. However, HashMap neither remembers the order in which you inserted elements nor keeps elements in any sorted order.

A TreeMap uses a red-black tree data structure internally. Unlike HashMap, TreeMap keeps the elements in sorted order (i.e., sorted by its keys). So, searching or inserting is somewhat slower than the HashMap.

Overriding the hashCode() Method

 The hashCode()  method should return the same hash value for two objects if the equals()  method returns true for them.

Comparable and Comparator Interfaces

Comparable and Comparator interfaces are used to compare similar objects, 

The Comparable class has only one method compareTo(), which is declared as follows:

int compareTo(Element that)

Since you are implementing the compareTo() method in a class, you have this reference available. You can compare the current element with the passed Element and return an int value.

return 1 if current object > passed object

return 0 if current object == passed object

return -1 if current object < passed object

Differences between Implementing Comparable and Comparator Interfaces

 Comparable Interface 

• Used when the objects need to be compared in their natural order.
• You do not create a separate class just to implement the Comparable interface.
• For a given class type, you have only that class (and that class alone) implementing the Comparable interface.
• The method in the Comparable interface is declared as int compareTo(ClassType type);.

 Comparator Interface

• Used when the objects need to be compared in custom user-defined order (other than the natural order).
• You create a separate class just to implement the Comparator interface.
• You can have many separate (i.e., independent) classes implementing the Comparator interface, with each class defining different ways to compare objects.
• The method in the Comparator interface is declared as int compare(ClassType type1, ClassType type2);.