Java Collections Framework: Arrays, Lists, and Maps

Question

Explain the Java Collections Framework, including: - Arrays and their characteristics - List implementations (ArrayList, LinkedList) - Queue implementations - Set implementations - Map implementations (HashMap, TreeMap) - When to use each collection type - Performance characteristics and best practices

Answer

Arrays

Basic Array Characteristics

// Fixed-size array
int[] numbers = new int[5];
String[] names = {"Alice", "Bob", "Charlie"};

// Multi-dimensional array
int[][] matrix = new int[3][3];

// Array operations
numbers[0] = 1;                    // Set element
int length = numbers.length;       // Get length
Arrays.sort(numbers);              // Sort array
Arrays.fill(numbers, 0);           // Fill array

Array vs ArrayList

// Array (fixed size)
int[] array = new int[5];
array[0] = 1;
array[1] = 2;

// ArrayList (dynamic size)
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.remove(0);  // Remove element
list.add(3);     // Add element

Lists

ArrayList Implementation

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();

        // Adding elements
        list.add("First");
        list.add("Second");
        list.add(1, "Inserted");  // Insert at index

        // Accessing elements
        String first = list.get(0);

        // Removing elements
        list.remove("First");     // Remove by object
        list.remove(0);           // Remove by index

        // Checking existence
        boolean exists = list.contains("Second");

        // Iterating
        for (String item : list) {
            System.out.println(item);
        }

        // Using streams
        list.stream()
            .filter(s -> s.length() > 5)
            .forEach(System.out::println);
    }
}

LinkedList Implementation

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // Adding elements
        list.addFirst(1);     // Add at beginning
        list.addLast(2);      // Add at end
        list.add(1, 3);       // Add at index

        // Removing elements
        list.removeFirst();   // Remove first
        list.removeLast();    // Remove last

        // Queue operations
        list.offer(4);        // Add to end
        list.poll();          // Remove and return first
        list.peek();          // View first without removing
    }
}

Queues

Queue Implementations

public class QueueExample {
    public static void main(String[] args) {
        // PriorityQueue (natural ordering)
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(3);
        pq.offer(1);
        pq.offer(2);
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());  // Prints: 1, 2, 3
        }

        // ArrayDeque (double-ended queue)
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addFirst("First");
        deque.addLast("Last");
        deque.offerFirst("New First");
        deque.offerLast("New Last");

        // BlockingQueue (thread-safe)
        BlockingQueue<Integer> bq = new LinkedBlockingQueue<>();
        bq.offer(1);
        try {
            bq.put(2);  // Blocks if queue is full
            int item = bq.take();  // Blocks if queue is empty
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

Sets

Set Implementations

public class SetExample {
    public static void main(String[] args) {
        // HashSet (unordered, O(1) operations)
        HashSet<String> hashSet = new HashSet<>();
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Apple");  // Duplicate ignored

        // TreeSet (sorted, O(log n) operations)
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(3);
        treeSet.add(1);
        treeSet.add(2);
        // Prints: 1, 2, 3
        treeSet.forEach(System.out::println);

        // LinkedHashSet (maintains insertion order)
        LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("First");
        linkedSet.add("Second");
        linkedSet.add("Third");
        // Maintains order: First, Second, Third
        linkedSet.forEach(System.out::println);
    }
}

Maps

HashMap Implementation

public class HashMapExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();

        // Adding key-value pairs
        map.put("One", 1);
        map.put("Two", 2);

        // Accessing values
        Integer value = map.get("One");

        // Checking existence
        boolean containsKey = map.containsKey("One");
        boolean containsValue = map.containsValue(1);

        // Removing entries
        map.remove("One");

        // Iterating
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Using compute methods
        map.computeIfAbsent("Three", k -> 3);
        map.computeIfPresent("Two", (k, v) -> v * 2);
    }
}

TreeMap Implementation

public class TreeMapExample {
    public static void main(String[] args) {
        // Natural ordering
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("C", 3);
        map.put("A", 1);
        map.put("B", 2);
        // Prints: A=1, B=2, C=3
        map.forEach((k, v) -> System.out.println(k + "=" + v));

        // Custom ordering
        TreeMap<String, Integer> reverseMap = new TreeMap<>(
            Collections.reverseOrder());
        reverseMap.put("C", 3);
        reverseMap.put("A", 1);
        reverseMap.put("B", 2);
        // Prints: C=3, B=2, A=1
        reverseMap.forEach((k, v) -> System.out.println(k + "=" + v));
    }
}

Performance Characteristics

Time Complexity

Collection Type    | Add    | Remove | Get    | Contains
------------------|--------|--------|--------|----------
ArrayList         | O(1)*  | O(n)   | O(1)   | O(n)
LinkedList        | O(1)   | O(1)   | O(n)   | O(n)
HashSet           | O(1)*  | O(1)*  | O(1)*  | O(1)*
TreeSet           | O(log n)| O(log n)| O(log n)| O(log n)
HashMap           | O(1)*   | O(1)*  | O(1)*  | O(1)*
TreeMap           | O(log n)| O(log n)| O(log n)| O(log n)

Space Complexity

Collection Type    | Space Complexity
------------------|------------------
ArrayList         | O(n)
LinkedList        | O(n)
HashSet           | O(n)
TreeSet           | O(n)
HashMap           | O(n)
TreeMap           | O(n)

Best Practices

Collection Selection

// Use ArrayList when:
// - Random access is needed
// - Size is known or small
ArrayList<String> list = new ArrayList<>();

// Use LinkedList when:
// - Frequent insertions/deletions in middle
// - Queue/Stack operations needed
LinkedList<String> linkedList = new LinkedList<>();

// Use HashSet when:
// - Unique elements needed
// - Order doesn't matter
HashSet<String> set = new HashSet<>();

// Use TreeSet when:
// - Sorted unique elements needed
TreeSet<String> treeSet = new TreeSet<>();

// Use HashMap when:
// - Key-value pairs needed
// - Order doesn't matter
HashMap<String, Integer> map = new HashMap<>();

// Use TreeMap when:
// - Sorted key-value pairs needed
TreeMap<String, Integer> treeMap = new TreeMap<>();

Thread Safety

// Synchronized collections
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

// Concurrent collections
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> concurrentList = new CopyOnWriteArrayList<>();

Initial Capacity

// Specify initial capacity for better performance
ArrayList<String> list = new ArrayList<>(1000);
HashMap<String, Integer> map = new HashMap<>(1000, 0.75f);

Testing

public class CollectionsTest {
    @Test
    public void testArrayList() {
        ArrayList<String> list = new ArrayList<>();
        list.add("Test");
        assertEquals("Test", list.get(0));
        assertEquals(1, list.size());
    }

    @Test
    public void testHashMap() {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Key", 1);
        assertEquals(Integer.valueOf(1), map.get("Key"));
        assertTrue(map.containsKey("Key"));
    }

    @Test
    public void testSet() {
        HashSet<String> set = new HashSet<>();
        set.add("Test");
        set.add("Test");  // Duplicate
        assertEquals(1, set.size());  // Only one unique element
    }
}

Conclusion

Choose collections based on:
Access patterns
Size requirements
Ordering needs
Thread safety requirements
Consider performance implications
Use appropriate initial capacities
Consider thread safety when needed
Use collections that best match your use case