📋 Java List Interface - Complete Guide

“The List interface provides ordered collections with indexed access, making it perfect for scenarios where element position matters and you need to maintain insertion order.”

🎯 What is the List Interface?

The List interface is a subinterface of Collection that represents an ordered collection (sequence) where:

• Elements are stored in insertion order
• Indexed access is supported (get/set by position)
• Duplicate elements are allowed
• Null values are permitted (implementation dependent)

🔗 Key Characteristics

Feature	Description	Example
Ordered	Maintains insertion order	[a, b, c] stays [a, b, c]
Indexed	Access by integer index	list.get(0) returns first element
Duplicates	Same element can appear multiple times	[a, b, a] is valid
Positional Operations	Insert/remove at specific positions	add(index, element)

📊 List Hierarchy and Implementations

🌳 Class Hierarchy

Collection<E>
└── List<E> (interface)
    ├── ArrayList<E> - Dynamic array implementation
    ├── LinkedList<E> - Doubly-linked list implementation
    ├── Vector<E> - Synchronized dynamic array (legacy)
    └── Stack<E> - LIFO stack extending Vector (legacy)

📈 Performance Comparison Matrix

Operation	ArrayList	LinkedList	Vector	Best Choice
Random Access	O(1)	O(n)	O(1)	ArrayList
Sequential Access	O(1)	O(1)	O(1)	All equal
Insert at Beginning	O(n)	O(1)	O(n)	LinkedList
Insert at End	O(1)*	O(1)	O(1)*	All equal
Insert at Index	O(n)	O(n)	O(n)	Context dependent
Delete at Beginning	O(n)	O(1)	O(n)	LinkedList
Delete at End	O(1)	O(1)	O(1)	All equal
Delete at Index	O(n)	O(n)	O(n)	Context dependent
Search	O(n)	O(n)	O(n)	All equal
Memory Overhead	Low	High	Low	ArrayList
Thread Safety	❌	❌	✅	Vector

* Amortized complexity - may be O(n) during resize

🔧 List Interface Methods

📋 Core List Methods

public interface List<E> extends Collection<E> {
    // Positional access operations
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);

    // Search operations
    int indexOf(Object o);
    int lastIndexOf(Object o);

    // List iteration
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);

    // Range operations
    List<E> subList(int fromIndex, int toIndex);

    // Java 8+ additions
    default void replaceAll(UnaryOperator<E> operator);
    default void sort(Comparator<? super E> c);

    // Inherited from Collection
    boolean add(E e);
    boolean remove(Object o);
    boolean contains(Object o);
    int size();
    boolean isEmpty();
    Iterator<E> iterator();
    // ... more methods
}

💻 Method Usage Examples

public class ListMethodExamples {
    public void demonstrateListMethods() {
        List<String> fruits = new ArrayList<>();

        // Adding elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add(1, "Orange"); // Insert at specific index

        // Accessing elements
        String firstFruit = fruits.get(0);
        fruits.set(1, "Mango"); // Replace element at index

        // Searching
        int appleIndex = fruits.indexOf("Apple");
        int lastAppleIndex = fruits.lastIndexOf("Apple");

        // Removing elements
        fruits.remove(0); // Remove by index
        fruits.remove("Banana"); // Remove by object

        // Range operations
        List<String> subList = fruits.subList(0, 2);

        // Sorting
        fruits.sort(Comparator.naturalOrder());

        // Replacing all elements
        fruits.replaceAll(String::toUpperCase);
    }
}

🚀 ArrayList Implementation

💡 What is ArrayList?

ArrayList is a resizable array implementation of the List interface that provides:

• Fast random access (O(1) for get/set)
• Efficient end operations (O(1) amortized for add/remove)
• Low memory overhead
• Dynamic resizing as needed

🔧 ArrayList Construction

public class ArrayListConstructionExamples {
    public void demonstrateConstruction() {
        // Default constructor (initial capacity 10)
        ArrayList<String> list1 = new ArrayList<>();

        // With initial capacity
        ArrayList<String> list2 = new ArrayList<>(100);

        // From existing collection
        List<String> existing = Arrays.asList("a", "b", "c");
        ArrayList<String> list3 = new ArrayList<>(existing);

        // Using Arrays.asList (fixed-size list)
        List<String> fixedList = Arrays.asList("x", "y", "z");

        // Using List.of (immutable list)
        List<String> immutableList = List.of("p", "q", "r");
    }
}

📊 ArrayList Performance Characteristics

public class ArrayListPerformanceExample {
    public void demonstratePerformance() {
        ArrayList<Integer> numbers = new ArrayList<>();

        // Adding elements (O(1) amortized)
        for (int i = 0; i < 1000000; i++) {
            numbers.add(i);
        }

        // Random access (O(1))
        int middleElement = numbers.get(500000);

        // Sequential access (O(1) per element)
        for (int number : numbers) {
            // Process each number
        }

        // Insertion at beginning (O(n) - avoid for large lists)
        numbers.add(0, -1);

        // Insertion at end (O(1) amortized)
        numbers.add(1000001);
    }
}

🔗 LinkedList Implementation

💡 What is LinkedList?

LinkedList is a doubly-linked list implementation that provides:

• Fast insertion/deletion at both ends (O(1))
• Efficient sequential access
• Flexible structure for frequent modifications
• Higher memory overhead per element

🔧 LinkedList Construction

public class LinkedListConstructionExamples {
    public void demonstrateConstruction() {
        // Default constructor
        LinkedList<String> list1 = new LinkedList<>();

        // From existing collection
        List<String> existing = Arrays.asList("a", "b", "c");
        LinkedList<String> list2 = new LinkedList<>(existing);

        // LinkedList specific methods
        LinkedList<String> list3 = new LinkedList<>();
        list3.addFirst("First");
        list3.addLast("Last");
        list3.offer("Offer"); // Adds to end
        list3.offerFirst("OfferFirst");
        list3.offerLast("OfferLast");
    }
}

📊 LinkedList Performance Characteristics

public class LinkedListPerformanceExample {
    public void demonstratePerformance() {
        LinkedList<String> names = new LinkedList<>();

        // Fast operations at both ends
        names.addFirst("Alice");    // O(1)
        names.addLast("Bob");       // O(1)
        names.removeFirst();        // O(1)
        names.removeLast();         // O(1)

        // Queue operations
        names.offer("Charlie");     // O(1) - adds to end
        String first = names.peek(); // O(1) - views first element
        String removed = names.poll(); // O(1) - removes and returns first

        // Stack operations
        names.push("David");        // O(1) - adds to beginning
        String top = names.peek();  // O(1) - views first element
        String popped = names.pop(); // O(1) - removes and returns first
    }
}

⚠️ LinkedList Considerations

public class LinkedListConsiderations {
    public void demonstrateConsiderations() {
        LinkedList<String> list = new LinkedList<>();

        // 1. Random access is slow
        for (int i = 0; i < 1000; i++) {
            list.add("Item" + i);
        }

        // This is O(n) - very slow for LinkedList!
        String item = list.get(500);

        // 2. Better to use iterator or enhanced for-loop
        for (String element : list) {
            // O(1) per element - much faster
        }

        // 3. Use LinkedList-specific methods when possible
        list.addFirst("NewFirst");  // Better than add(0, "NewFirst")
        list.addLast("NewLast");    // Better than add("NewLast")
    }
}

🎯 When to Use Which Implementation

📊 Decision Matrix

Use Case	ArrayList	LinkedList	Reasoning
Random Access	✅ Best	❌ Poor	ArrayList provides O(1) access
Sequential Access	✅ Good	✅ Good	Both are efficient
Frequent Insertions	❌ Poor	✅ Best	LinkedList handles changes better
Memory Efficiency	✅ Best	❌ Poor	ArrayList has lower overhead
Queue Operations	❌ Poor	✅ Best	LinkedList has built-in queue methods
Stack Operations	❌ Poor	✅ Best	LinkedList has built-in stack methods