What is the Difference Between ArrayList and LinkedList in Java?

Both implement the List interface but have different internal implementations affecting performance.

ArrayList (Dynamic Array)

import java.util.*;

public class ArrayListExample {
    public static void main(String[] args) {
        List arrayList = new ArrayList<>();
        
        // Adding elements - O(1) amortized
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }
        
        // Fast random access - O(1)
        int value = arrayList.get(50000);
        System.out.println("Value at index 50000: " + value);
        
        // Slow insert/delete in middle - O(n)
        arrayList.add(0, -1); // Shifts all elements
        
        // Set value - O(1)
        arrayList.set(1000, 999);
        
        // Remove by index - O(n)
        arrayList.remove(0);
        
        // Internal: contiguous memory block
        // Default capacity: 10, grows by 50% when full
    }
}

LinkedList (Doubly Linked List)

public class LinkedListExample {
    public static void main(String[] args) {
        List linkedList = new LinkedList<>();
        
        // Fast insert/delete at ends - O(1)
        linkedList.add(10);   // Adds at end
        linkedList.add(0, 5); // Adds at beginning
        
        // Slow random access - O(n)
        // int value = linkedList.get(50000); // Slow!
        
        // LinkedList-specific methods
        ((LinkedList) linkedList).addFirst(1);
        ((LinkedList) linkedList).addLast(100);
        ((LinkedList) linkedList).removeFirst();
        ((LinkedList) linkedList).removeLast();
        
        System.out.println("First: " + ((LinkedList) linkedList).getFirst());
        System.out.println("Last: " + ((LinkedList) linkedList).getLast());
        
        // Internal: doubly linked nodes with prev and next pointers
    }
}

Performance Test

public class PerformanceTest {
    public static void main(String[] args) {
        int size = 100000;
        
        // Test 1: Add elements at end
        List arrayList = new ArrayList<>();
        long start = System.nanoTime();
        for (int i = 0; i < size; i++) arrayList.add(i);
        long arrayAddEnd = System.nanoTime() - start;
        
        List linkedList = new LinkedList<>();
        start = System.nanoTime();
        for (int i = 0; i < size; i++) linkedList.add(i);
        long linkedAddEnd = System.nanoTime() - start;
        
        System.out.println("Add at end - ArrayList: " + arrayAddEnd/1_000_000 + "ms");
        System.out.println("Add at end - LinkedList: " + linkedAddEnd/1_000_000 + "ms");
        
        // Test 2: Add at beginning
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) arrayList.add(0, i);
        long arrayAddBegin = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 1000; i++) linkedList.add(0, i);
        long linkedAddBegin = System.nanoTime() - start;
        
        System.out.println("Add at beginning - ArrayList: " + arrayAddBegin/1_000_000 + "ms");
        System.out.println("Add at beginning - LinkedList: " + linkedAddBegin/1_000_000 + "ms");
        
        // Test 3: Random access
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) arrayList.get(i);
        long arrayGet = System.nanoTime() - start;
        
        start = System.nanoTime();
        for (int i = 0; i < 10000; i++) linkedList.get(i);
        long linkedGet = System.nanoTime() - start;
        
        System.out.println("Random access - ArrayList: " + arrayGet/1_000_000 + "ms");
        System.out.println("Random access - LinkedList: " + linkedGet/1_000_000 + "ms");
    }
}

Performance Comparison Table

When to Use Which?

// Use ArrayList when:
// - Frequent random access (get/set operations)
// - Adding/removing at end only
// - Memory efficiency important

List names = new ArrayList<>();

// Use LinkedList when:
// - Frequent add/remove at beginning or middle
// - Implementing Queue/Deque
// - No need for frequent random access

Queue queue = new LinkedList<>(); // Perfect for Queue
Deque deque = new LinkedList<>();  // Perfect for Deque

// Example: Implementing a simple queue
Queue taskQueue = new LinkedList<>();
taskQueue.offer("Task 1");
taskQueue.offer("Task 2");
String nextTask = taskQueue.poll(); // Retrieves and removes head

Choose wisely based on your use case. Learn more at Online Learner!