Java Collections Framework Notes

Collection Framework in Java

Collections Overview

  • The Collection framework in Java provides an architecture to store and manipulate groups of objects, enabling operations like searching, sorting, insertion, manipulation, and deletion.
  • It includes interfaces (Set, List, Queue, Deque) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet).
  • The framework uses a unified architecture for storing and manipulating groups of objects, consisting of interfaces, classes, and algorithms, all found within the java.util package.

Core Interfaces

  • Collection: Represents a generic collection of elements.
  • Map: Represents a mapping of keys to values.

List Interface

  • A child interface of Collection that stores an ordered collection of objects, allowing duplicate values.
  • Implemented by classes like ArrayList, LinkedList, Vector, and Stack.
  • Instantiation examples:
    • List<data-type> list1 = new ArrayList();
    • List<data-type> list2 = new LinkedList();
    • List<data-type> list3 = new Vector();
    • List<data-type> list4 = new Stack();

ArrayList

  • Implements the List interface using a dynamic array to store duplicate elements of different data types.

  • Maintains insertion order and is non-synchronized.

  • Allows random access of elements and dynamically adjusts its size.

    Example:

    ArrayList<String> al = new ArrayList<String>();
al.add("abc");
al.add(1, "steve");
al.remove("abc");
Collections.sort(al);

LinkedList

  • Implements the Collection interface using a doubly linked list to store elements.

  • Allows duplicate elements, maintains insertion order, and is non-synchronized.

  • Offers fast manipulation due to the lack of shifting.

    Example:

    LinkedList<String> object = new LinkedList<String>();
object.add("A");
object.addLast("C");
object.remove("B");

Vector

  • Implements a growable array of objects and is fully compatible with collections.

  • Similar to ArrayList but is synchronized and includes some legacy methods.

    Example:

    Vector v = new Vector();
ArrayList a = new ArrayList();
v.add(10.4);
v.addAll(a);
Vector v_clone = (Vector) v.clone();

Stack

  • A subclass of Vector that implements the LIFO (Last-In-First-Out) data structure.

  • Includes methods like push(), peek(), and pop().

    Example:

    Stack<Integer> stack = new Stack<Integer>();
stack.push(i);
stack.pop();
stack.peek();

Queue Interface

  • Extends the Collection interface and holds elements to be processed, following FIFO (First-In-First-Out) principle.
  • Common classes are PriorityQueue and LinkedList.

Key Methods of Queue:

  • boolean add(object): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
  • boolean offer(object): Inserts the specified element into this queue, returning true upon success.
  • Object remove(): Retrieves and removes the head of this queue.
  • Object poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
  • Object element(): Retrieves, but does not remove, the head of this queue.
  • Object peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

PriorityQueue

  • Implements the Queue interface, ordering elements based on priority.

  • Does not allow null values.

    Example:

    PriorityQueue<String> queue = new PriorityQueue<String>();
queue.add("Amit Sharma");
queue.remove();
queue.poll();

Deque Interface

  • Extends the Queue interface, allowing element insertion and removal from both ends (double-ended queue).

ArrayDeque

  • Implements the Deque interface.

  • Faster than ArrayList and Stack, with no capacity restrictions.

    Example:

    Deque<String> deque = new ArrayDeque<String>();
deque.add("Gautam");

Set Interface

  • Extends the Collection interface.

  • Represents an unordered collection of unique objects (no duplicates).

  • Implemented by HashSet, LinkedHashSet, or TreeSet.

    Example:

    Set<String> hash_Set = new HashSet<String>();
hash_Set.add("delhi");
hash_Set.addAll(hash_Set1); //union of two sets
hash_Set.retainAll(hash_Set1);//intersection of two sets

HashSet

  • Implements the Set interface.
  • Uses a hash table for storage.
  • Contains unique items.

LinkedHashSet

  • LinkedList implementation of the Set interface which extends the HashSet class and implements Set interface.
  • Like HashSet also contains unique elements but maintains insertion order and permits null elements.

SortedSet

  • Alternate of Set interface that provides a total ordering on its elements.
  • The elements of the SortedSet are arranged in the increasing (ascending) order.
  • The SortedSet provides the additional methods that inhibit the natural ordering of the elements.

TreeSet

  • Implements the Set interface using a tree for storage.
  • Contains unique elements stored in ascending order.

Map Interface

  • A map contains values on the basis of key, i.e. key and value pair.
  • Each key and value pair is known as an entry.
  • A Map contains unique keys.

Useful methods of Map interface

  • V put(Object key, Object value): It is used to insert an entry in the map.
  • void putAll(Map map): It is used to insert the specified map in the map.
  • V putIfAbsent(K key, V value): It inserts the specified value with the specified key in the map only if it is not already specified.
  • V remove(Object key): It is used to delete an entry for the specified key.
  • boolean remove(Object key, Object value): It removes the specified values with the associated specified keys from the map.
  • Set keySet(): It returns the Set view containing all the keys.
  • Set<Map.Entry<K,V>> entrySet(): It returns the Set view containing all the keys and values.
  • void clear(): It is used to reset the map.
  • boolean containsValue(Object value): This method returns true if some value equal to the value exists within the map, else return false.
  • boolean containsKey(Object key): This method returns true if some key equal to the key exists within the map, else return false.
  • boolean equals(Object o): It is used to compare the specified Object with the Map.

HashMap

  • The implementation of Map, but it doesn't maintain any order.

Example:

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
map.put(1,12);

TreeMap

  • TreeMap is the implementation of Map and SortedMap. It maintains ascending order.

Example:

TreeMap<String, String> map1 = new TreeMap<String, String>();
map1.put("1","sabc");

Collections.sort()

  • java.util.Collections.sort() method is present in java.util.Collections class.
  • It is used to sort the elements present in the specified list of Collection in ascending order.
  • Can sort the elements of Array as well as linked list, queue and many more present in it.

Example:

Collections.sort(al);

For descending order:

Collections.sort(al, Collections.reverseOrder());

Comparator Interface

Used for sorting an ArrayList according to user defined criteria.

Example:

Collections.sort(ar, new Sortbyroll());

equals() and hashCode() Methods

  • equals() method is used to compare equality of two Objects.
    • Shallow comparison checks if two Object references refer to the same Object.
    • Deep comparison compares data members of Objects.
  • hashCode() method returns the hashcode value as an Integer and is used in hashing based collections.

Type Wrappers

  • A Wrapper class is a class whose object wraps or contains a primitive data types.

Primitive Data Types and Their Corresponding Wrapper Class:

  • char -> Character
  • byte -> Byte
  • short -> Short
  • long -> Long
  • Integer -> Integer
  • float -> Float
  • double -> Double
  • boolean -> Boolean