ArrayList is a resizable array implementation of the List interface. It maintains insertion order, allows null and duplicate elements, and provides fast random access. However, its not thread-safe. Insertions and deletions in the middle of the list require shifting elements, making these operations slower.

Vector is similar to ArrayList in its underlying array-based structure but is thread-safe due to synchronized methods. It implements the same interfaces: List, RandomAccess, Cloneable, and Serializable. The synchronization makes it slower in single-threaded environments.

LinkedList uses a doubly-linked list structure, implementing List, Queue, and Deque interfaces. It is not thread-safe but can be made synchronized using Collections.synchronizedList(). It excels at insertions and deletions but has slower random access compared to array-based lists.

Underlying Data Structures

ArrayList and Vector both use Object[] arrays internally. When elements are added beyond capacity, a new larger array is created and elements are copied over.

LinkedList uses a doubly-linked list where each node contains references to both the previous and next nodes, allowing bidirectional traversal.

Thread Safety Comparison

ArrayList and LinkedList are not thread-safe. Vector achieves thread safety through synchronized methods, which incurs performance overhead.

To create thread-safe versions of ArrayList or LinkedList:

List<String> syncArrayList = Collections.synchronizedList(new ArrayList<>());
List<String> syncLinkedList = Collections.synchronizedList(new LinkedList<>());

Initial Capacity Settings

ArrayList initializes with a default capacity of 10 when no size is specified:

private static final int DEFAULT_CAPACITY = 10;

Vector also defaults to capacity 10:

public Vector() {
    this(10);
}

LinkedList, being a linked structure, has no concept of initial capacity since nodes are dynamically allocated.

Capacity Expansion Mechanisms

When the internal array fills up, both ArrayList and Vector create larger arrays and copy existing elements. ArrayList expands by approximately 1.5 times its current size:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Vector defaults to doubling its capacity but allows customization through the capacityIncrement parameter:

int newCapacity = (capacityIncrement > 0) 
    ? oldCapacity + capacityIncrement 
    : oldCapacity * 2;

Iterator Implementations

All three classes provide multiple iterator types:

• Itr: Basic Iterator implementation supporting hasNext(), next(), and remove()
• ListItr: Extends Itr with bidirectional traversal and element modification capabilities
• Spliterator: Java 8+ iterator supporting parallel processing

LinkedList additionally provides a DescendingIterator for reverse traversal.

Performance Analysis

Time Complexity Overview

Operation	ArrayList/Vector	LinkedList
Random Access (get)	O(1)	O(n)
Insert at End	O(1) amortized	O(1)
Insert at Beginning/Middle	O(n)	O(1)*
Delete at End	O(1)	O(1)
Delete at Beginning/Middle	O(n)	O(1)*

*Note: LinkedList insertion/deletion is O(1) for the operation itself, but O(n) to reach the position.

Benchmark: Insertion at Beginning

import java.util.*;

public class InsertionBenchmark {
    private static final int ELEMENT_COUNT = 100_000;
    
    public static void main(String[] args) {
        measureInsertPerformance(new ArrayList<>(), "ArrayList");
        measureInsertPerformance(new LinkedList<>(), "LinkedList");
        measureInsertPerformance(new Vector<>(), "Vector");
    }
    
    private static void measureInsertPerformance(List<Integer> list, String name) {
        long start = System.nanoTime();
        for (int i = 0; i < ELEMENT_COUNT; i++) {
            list.add(0, i);
        }
        long duration = (System.nanoTime() - start) / 1_000_000;
        System.out.println(name + " insertion time: " + duration + " ms");
    }
}

Sample output:

ArrayList insertion time: 7815 ms
LinkedList insertion time: 12 ms
Vector insertion time: 8200 ms

Benchmark: Random Access Performance

import java.util.*;

public class AccessBenchmark {
    private static final int ELEMENT_COUNT = 100_000;
    
    public static void main(String[] args) {
        runAccessTest(new ArrayList<>(), "ArrayList");
        runAccessTest(new LinkedList<>(), "LinkedList");
        runAccessTest(new Vector<>(), "Vector");
    }
    
    private static void runAccessTest(List<Integer> list, String name) {
        for (int i = 0; i < ELEMENT_COUNT; i++) {
            list.add(i);
        }
        
        long start = System.nanoTime();
        for (int i = 0; i < ELEMENT_COUNT; i++) {
            list.get(i);
        }
        long duration = (System.nanoTime() - start) / 1_000_000;
        System.out.println(name + " access time: " + duration + " ms");
    }
}

Sample output:

ArrayList access time: 5 ms
LinkedList access time: 42800 ms
Vector access time: 6 ms

Benchmark: Deletion Operations

import java.util.*;

public class DeletionBenchmark {
    private static final int ELEMENT_COUNT = 100_000;
    
    public static void main(String[] args) {
        runDeletionTest(new ArrayList<>(), "ArrayList");
        runDeletionTest(new LinkedList<>(), "LinkedList");
        runDeletionTest(new Vector<>(), "Vector");
    }
    
    private static void runDeletionTest(List<Integer> list, String name) {
        for (int i = 0; i < ELEMENT_COUNT; i++) {
            list.add(i);
        }
        
        long start = System.nanoTime();
        while (!list.isEmpty()) {
            list.remove(0);
        }
        long duration = (System.nanoTime() - start) / 1_000_000;
        System.out.println(name + " deletion time: " + duration + " ms");
    }
}

Sample output:

ArrayList deletion time: 2100 ms
LinkedList deletion time: 8 ms
Vector deletion time: 2050 ms

Multi-threaded Vector Performance

import java.util.*;

public class ConcurrentDeletionTest {
    private static final int TOTAL_ELEMENTS = 100_000;
    
    public static void main(String[] args) throws InterruptedException {
        Vector<Integer> vector = new Vector<>();
        for (int i = 0; i < TOTAL_ELEMENTS; i++) {
            vector.add(i);
        }
        
        Thread threadA = new Thread(() -> {
            for (int i = 0; i < TOTAL_ELEMENTS / 2; i++) {
                vector.remove(0);
            }
        });
        
        Thread threadB = new Thread(() -> {
            for (int i = 0; i < TOTAL_ELEMENTS / 2; i++) {
                vector.remove(0);
            }
        });
        
        long start = System.nanoTime();
        threadA.start();
        threadB.start();
        threadA.join();
        threadB.join();
        long duration = (System.nanoTime() - start) / 1_000_000;
        
        System.out.println("Concurrent deletion time: " + duration + " ms");
    }
}

The synchronized methods in Vector cause thread contention, resulting in longer execution times compared to single-threaded operations.

Selection Guidelines

• Use ArrayList when you need fast random access and mostly add/remove elements at the end
• Use LinkedList when you frequently insert or delete elements at various positions
• Use Vector only when thread safety is required in legacy code; for new code, prefer Collections.synchronizedList() or CopyOnWriteArrayList