Mastering Java Collections: From Interfaces to Iterators

1 Overview of the Collection Framework Diagram

We will briefly interpret the diagram above:

All collection classes are located in the java.util package.

Iterator is the tool for traversing collections; Collection depends on Iterator because its implementations must provide an iterator() method that returns an Iterator . ListIterator is used specifically for List .

Java collection classes are derived from two root interfaces: Collection and Map .

Collection interfaces include LinkIterator , List , Set , Queue , SortedMap , and SortedSet —six interfaces representing different collection types.

Abstract classes such as AbstractCollection , AbstractList , AbstractSet , AbstractMap , and AbstractSequentialList provide partial implementations of those interfaces.

Concrete implementation classes (e.g., LinkedHashMap , TreeMap , etc.) provide the actual functionality.

The Collection interface allows duplicate objects.

The Set interface extends Collection but forbids duplicate elements; implementations include HashSet and TreeSet . HashSet relies on HashMap , while TreeSet relies on TreeMap .

The List interface extends Collection , allows duplicates, and maintains insertion order; implementations include ArrayList , LinkedList , Vector , and Stack .

The Map interface represents key‑value pairs; it does not extend Collection . Implementations include HashMap , TreeMap , WeakHashMap , and Hashtable .

Set, List, and Map are the three major collection categories.

Arrays and Collections are utility classes for operating on arrays and collections.

After the overall introduction, we will analyze each category in detail.

2 Collection Interface

The Collection interface is the root for handling object collections; it defines many methods for element operations. It has two main sub‑interfaces, List and Set . Note that Map is not a sub‑interface of Collection .

Common methods include add() , addAll() , contains() , toArray() , etc.

Collection also provides iterator() , which returns an Iterator . ListIterator is specific to List .

The Collection interface has two commonly used sub‑interfaces, described below.

2.1 List Interface

List represents an ordered collection where each element has an index. It allows duplicate elements and supports random access via index, similar to an array.

List extends Collection and defines an ordered collection. Implementations include ArrayList , LinkedList , Vector , and Stack .

2.1.1 ArrayList

ArrayList is a dynamic array and the most commonly used collection. It allows any element (including null ). It has an initial capacity (default 10) that grows as elements are added. Adding n elements takes O(n) time overall due to amortized resizing.

Methods such as size , isEmpty , get , set , iterator , and listIterator run in constant time. add runs in amortized constant time.

ArrayList excels at random access and is not synchronized.

2.1.2 LinkedList

LinkedList implements List using a doubly linked list. It provides get , remove , and insert operations at the head or tail. Random access is not supported; operations traverse from the nearer end.

Insertion and deletion are cheaper than in ArrayList . Like ArrayList , LinkedList is not synchronized; external synchronization is required for concurrent access.

2.1.3 Vector

Vector is similar to ArrayList but synchronized, making it thread‑safe. Its operations are almost identical to those of ArrayList .

2.1.4 Stack

Stack extends Vector to provide a LIFO stack with push , pop , peek , empty , and search methods. (Stack is initially empty.)

2.2 Set Interface

Set is a Collection that does not allow duplicate elements. Implementations include HashSet , LinkedHashSet , and TreeSet .

HashSet is backed by a HashMap , does not guarantee order, allows a single null , and is not synchronized.

LinkedHashSet maintains insertion order using a linked hash map and is also not synchronized.

TreeSet is an ordered set backed by a TreeMap , does not allow null keys, and is not synchronized.

Example code demonstrating Set behavior:

<code>private static void setWork() {
    Set<String> set = new HashSet<>();
    set.add("Brand1");
    set.add("Brand2");
    set.add("Brand1");
    System.out.println("Set Size:" + set.size());
    System.out.println("Set Elements:" + set.toString());

    // Add a new String object "Brand2"
    boolean result = set.add(new String("Brand2"));
    System.out.println(result);
    System.out.println(set);
}</code>

The output shows that duplicate elements are ignored because equals and hashCode consider them equal.

2.2.1 HashSet

HashSet has no guaranteed order, allows one null , is not synchronized, and provides fast lookup via hashing.

Allows a single null value.

Element positions are determined by hashCode .

Mutable objects used as elements must be handled carefully to avoid inconsistent behavior.

2.2.2 LinkedHashSet

LinkedHashSet extends HashSet , maintains insertion order using a linked list, and is not synchronized.

2.2.3 TreeSet

TreeSet is an ordered set based on a red‑black tree, non‑thread‑safe, and supports natural or custom ordering. Equality is determined by compareTo() returning 0 .

3 Map Interface

Map is a collection of key‑value pairs; it does not extend Collection . It guarantees a one‑to‑one relationship between keys and values.

3.1 HashMap

HashMap uses a hash table; keys are placed in buckets based on their hashCode . Collisions are resolved with linked lists or, since Java 8, balanced trees.

3.2 LinkedHashMap

LinkedHashMap extends HashMap and preserves insertion order (or access order if configured). It is not synchronized and is slightly slower than HashMap for iteration.

3.3 TreeMap

TreeMap is an ordered map based on a red‑black tree, non‑synchronized, and sorts keys either naturally or via a custom comparator.

4 Iterator and ListIterator Details

4.1 Iterator

Iterator is an interface that provides hasNext() , next() , and remove() methods for traversing collections.

<code>public interface Iterator<E> {}</code>

remove() is the only safe way to modify a collection during iteration.

4.2 ListIterator

ListIterator extends Iterator and adds bidirectional traversal, index access, and element modification methods.

boolean hasNext() ()

E next() ()

boolean hasPrevious() ()

E previous() ()

int nextIndex() ()

int previousIndex() ()

void remove() ()

void set(E e) ()

void add(E e) ()

<code>public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}</code>

Example code demonstrates using ListIterator to traverse, add, and modify elements.

<code>public static void listIteratorWork() {
    List<String> list = new ArrayList<>();
    list.add("Element A");
    list.add("Element B");
    list.add("Element C");
    System.out.println("Current list : " + list);

    ListIterator<String> it = list.listIterator();
    while (it.hasNext()) {
        System.out.println(it.next() + ", " + it.previousIndex() + ", " + it.nextIndex());
    }

    it.add("Element D");
    System.out.println("After adding : " + list);

    it = list.listIterator(1);
    System.out.print("After modifying : ");
    while (it.hasNext()) {
        if ("Element D".equals(it.next())) {
            it.set("Element replace");
        }
    }
    System.out.println(list);
}</code>

5 Interview Focus Points

5.1 ArrayList vs LinkedList

ArrayList uses a dynamic array; LinkedList uses a doubly linked list.

Both are not thread‑safe and implement Collection .

ArrayList provides O(1) random access; LinkedList has O(n) for get / set .

Insertion and deletion in the middle are faster with LinkedList.

Memory overhead differs: ArrayList may have unused capacity; LinkedList stores extra node pointers.

5.2 Hashtable vs HashMap

Both implement Map , Cloneable , and Serializable and use chaining.

Hashtable is synchronized and does not allow null keys or values; HashMap is unsynchronized and permits null .

Initial capacities differ; HashMap expands to powers of two.

HashMap is generally faster; Hashtable is considered legacy.

5.3 LinkedHashMap vs TreeMap

LinkedHashMap preserves insertion order (or access order if configured); TreeMap sorts keys according to natural order or a custom comparator.

5.4 Set Implementations Comparison

HashSet : unordered, non‑synchronized, allows one null .

LinkedHashSet : maintains insertion order, non‑synchronized.

TreeSet : ordered via sorting, non‑synchronized, does not allow null keys.

5.5 Iterator vs ListIterator

ListIterator supports add() , hasPrevious() , previous() , and index methods; Iterator does not.

ListIterator can modify elements via set() ; Iterator cannot.

5.6 Collection vs Collections

Collection is the root interface for all collection classes, defining basic operations such as add and remove. Collections is a utility class that provides static methods for sorting, searching, and other bulk operations on collections.