Java Collections Essentials — Part 2

There are three components that extend the collection interface i.e List, Queue and Sets. Let’s discuss about List.

Java List is an ordered collection that allows duplicate elements. Here’s a breakdown of the main List types:

• ArrayList
• LinkedList
• Vector
• Stack

ArrayList

List<E> list = new ArrayList<>();

• Resizable array implementation
• Offers fast random access

Best for: Scenarios requiring frequent random access and infrequent insertions/deletions

ArrayList provides constant-time O(1) access to elements via get() and set() methods, making it efficient for random access operations. Its backing array structure allows for quick retrieval of elements by index.

Limitations: Slow insertions/deletions in the middle

When inserting or removing elements in the middle of an ArrayList, subsequent elements need to be shifted, resulting in O(n) time complexity for these operations. This can lead to performance degradation for large lists with frequent modifications.

Main algorithms:

• Add: add(E element)
• Get: get(int index)
• Remove: remove(int index)
• Search: indexOf(Object o)

import java.util.ArrayList;
import java.util.List;

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

        // Add elements
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // Get element by index
        System.out.println("Element at index 1: " + list.get(1));

        // Set element at index
        list.set(1, "Blueberry");

        // Remove element by index
        list.remove(2);

        // Search for element
        int index = list.indexOf("Apple");
        System.out.println("Index of Apple: " + index);

        // Print all elements
        System.out.println("List contents: " + list);
    }
}

LinkedList

List<E> list = new LinkedList<>();

• Doubly-linked list implementation
• Also implements Deque interface

Best for: Frequent insertions/deletions, especially at the beginning or end

LinkedList provides constant-time O(1) performance for add and remove operations at both ends of the list. Its doubly-linked structure allows for efficient manipulation of elements without the need for shifting.

Limitations: Higher memory overhead, slower random access

LinkedList consumes more memory than ArrayList due to the storage of additional pointers for each element. Random access operations have O(n/2) time complexity, making them slower compared to ArrayList’s O(1) access.

Main algorithms:

• Add: add(E element), addFirst(E element), addLast(E element)
• Remove: remove(), removeFirst(), removeLast()
• Get: get(int index)

import java.util.LinkedList;

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

        // Add elements
        list.add("Red");
        list.addFirst("Green");
        list.addLast("Blue");
        list.addLast("White");
        list.addLast("Yellow");

        // Remove elements
        String first = list.removeFirst();
        String last = list.removeLast();
        String first = list.remove(); //by default it removes first element
        String indxEle = list.remove(1); // removes element by index

        // Get element
        String element = list.get(0);

        System.out.println("Removed first: " + first);
        System.out.println("Removed last: " + last);
        System.out.println("Remaining element: " + element);
    }
}

Vector

List<E> list = new Vector<>();

• Thread-safe dynamic array (legacy class)

Best for: Multi-threaded environments requiring synchronization

Vector is thread-safe, providing synchronized methods for concurrent access. This makes it suitable for scenarios where multiple threads need to access and modify the list simultaneously.

Limitations: Performance overhead due to synchronization

The synchronization in Vector methods can lead to performance overhead in single-threaded environments or scenarios where external synchronization is preferred.

Main algorithms: Similar to ArrayList, but with synchronized methods

import java.util.Vector;

public class VectorExample {
    public static void main(String[] args) {
        // Create a Vector to hold String elements
        Vector<String> vector = new Vector<>();

        // Add elements to the Vector
        vector.add("Apple");
        vector.add("Banana");
        vector.add("Cherry");
        vector.add("Date");
        vector.add("Elderberry");

        // Display the contents of the Vector
        System.out.println("Initial Vector: " + vector);

        // Get an element at a specific index
        int indexToGet = 2; // Let's get the element at index 2
        String elementAtIndex = vector.get(indexToGet);
        System.out.println("Element at index " + indexToGet + ": " + elementAtIndex);

        // Remove an element at a specific index
        int indexToRemove = 1; // Let's remove the element at index 1 (Banana)
        String removedElement = vector.remove(indexToRemove);
        System.out.println("Removed element at index " + indexToRemove + ": " + removedElement);

        // Display the contents of the Vector after removal
        System.out.println("Vector after removal: " + vector);

        // Search for an element in the Vector
        String searchElement = "Cherry";
        int foundIndex = vector.indexOf(searchElement);
        
        if (foundIndex != -1) {
            System.out.println("Element '" + searchElement + "' found at index: " + foundIndex);
        } else {
            System.out.println("Element '" + searchElement + "' not found in the Vector.");
        }

        // Display final state of the Vector
        System.out.println("Final Vector: " + vector);
    }
}

Stack

Stack<E> stack = new Stack<>();

• Last-In-First-Out (LIFO) stack, extending Vector

Best for: LIFO operations

Stack is designed specifically for Last-In-First-Out (LIFO) operations, making it ideal for scenarios that require this behavior, such as implementing undo functionality or parsing expressions.

Limitations: Inherits Vector’s synchronization overhead

Since Stack extends Vector, it inherits the synchronization overhead, which may not be necessary in all use cases and can impact performance.

Main algorithms:

• Push: push(E item)
• Pop: pop()
• Peek: peek()

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Create a Stack to hold Integer elements
        Stack<Integer> stack = new Stack<>();

        // Push elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        System.out.println("Stack after push operations: " + stack);

        // Peek at the top element of the stack
        int topElement = stack.peek();
        System.out.println("Element at top of the stack: " + topElement);

        // Pop an element from the stack
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);
        System.out.println("Stack after pop operation: " + stack);

        // Search for an element in the stack
        int searchElement = 20;
        int position = stack.search(searchElement);
        
        if (position != -1) {
            System.out.println("Element " + searchElement + " found at position: " + position);
        } else {
            System.out.println("Element " + searchElement + " not found in the stack.");
        }

        // Check if the stack is empty
        boolean isEmpty = stack.empty();
        System.out.println("Is the stack empty? " + isEmpty);
    }
}

A detailed breakdown of Queue collection type will be covered in Java Collections Essentials — Part 3