ArrayList vs LinkedList in Java | Core Java

📊 ArrayList

What is ArrayList?

ArrayList is a resizable array implementation in Java's Collection Framework. It implements the List interface and provides dynamic storage of elements with fast random access using indexes.

ArrayList maintains an internal array that grows dynamically when elements are added. When the array becomes full, a new larger array is created and all elements are copied to it.

Java

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // Create an ArrayList
        ArrayList<String> fruits = new ArrayList<>();
        
        // Add elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        fruits.add("Mango");
        
        // Access element by index (fast - O(1))
        System.out.println("First fruit: " + fruits.get(0));
        
        // Insert at specific position (slower - O(n))
        fruits.add(1, "Strawberry");
        
        // Remove element
        fruits.remove("Banana");
        
        // Iterate through ArrayList
        System.out.println("All fruits: " + fruits);
    }
}

🔗 LinkedList

What is LinkedList?

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. Each element (node) contains the data and references (pointers) to both the previous and next nodes in the sequence.

LinkedList is ideal when you need efficient insertions and deletions at the beginning, middle, or end of the list, as these operations don't require shifting elements.

Java

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // Create a LinkedList
        LinkedList<String> fruits = new LinkedList<>();
        
        // Add elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        
        // Add at beginning (fast - O(1))
        fruits.addFirst("Strawberry");
        
        // Add at end (fast - O(1))
        fruits.addLast("Mango");
        
        // Remove first element (fast - O(1))
        fruits.removeFirst();
        
        // Access element (slower - O(n))
        System.out.println("Second fruit: " + fruits.get(1));
        
        // LinkedList can be used as Queue/Deque
        System.out.println("All fruits: " + fruits);
    }
}

⚡ Key Differences

Time Complexity Comparison

Operation	ArrayList	LinkedList
Access (get/set)	O(1) - Fast ✓	O(n) - Slow ✗
Insert at Beginning	O(n) - Slow ✗	O(1) - Fast ✓
Insert at End	O(1)* - Fast ✓ *amortized	O(1) - Fast ✓
Insert at Middle	O(n) - Slow ✗	O(n) - Moderate (if finding position)
Delete from Beginning	O(n) - Slow ✗	O(1) - Fast ✓
Delete from End	O(1) - Fast ✓	O(1) - Fast ✓
Memory Overhead	Low - Only array storage	High - Extra pointers (prev/next)

*Note: ArrayList's add operation at end is O(1) amortized, but may become O(n) when resizing occurs.

📊 Detailed Comparison

ArrayList vs LinkedList - Detailed Differences

Aspect	ArrayList	LinkedList
Data Structure	Resizable Array	Doubly Linked List
Random Access	Fast ✓ (implement RandomAccess interface)	Slow ✗ (no RandomAccess interface)
Insertion/Deletion	Costly in middle due to shifting ✗	Efficient in middle with position reference ✓
Memory Usage	Less memory (stores only elements) ✓	More memory (stores prev/next pointers) ✗
Implements Interfaces	List only	List + Deque (can be used as Queue/Stack)
Best Use Case	Frequent access/search, less modification	Frequent insertion/deletion at ends/middle
Iteration	Fast and efficient	Slightly slower than ArrayList

✅⚠️ Advantages & Limitations

✅ ArrayList Advantages

Fast random access (O(1)) - great for searching
Simple implementation with less code
Less memory overhead than LinkedList
Excellent for storing and accessing data by index
Better cache locality due to contiguous memory

⚠️ ArrayList Limitations

Slow insertion/deletion in middle (requires shifting)
Resizing overhead when capacity is exceeded
Not suitable for frequent modifications

✅ LinkedList Advantages

Efficient insertion/deletion at any position (O(1) with reference)
Can act as Queue, Deque, or Stack
No resizing overhead - grows dynamically
Ideal for implementing LRU cache
Better for frequent add/remove operations

⚠️ LinkedList Limitations

Slower random access (O(n))
Higher memory consumption (extra pointers)
Poor cache locality
Not suitable for frequent search operations

🎯 When to Use

When to Use ArrayList vs LinkedList?

📊

Use ArrayList when:

✓ Frequent random access is required
✓ Mostly reading/iterating through data
✓ Few insertions/deletions (mostly at end)
✓ Working with small to medium datasets

🔗

Use LinkedList when:

✓ Frequent insertions/deletions at beginning/middle
✓ Need Queue/Deque operations (FIFO, LIFO)
✓ Random access is rarely required
✓ Memory is not a primary concern

🌍 Real-World Example

Choosing the Right List Implementation

Scenario 1 - Music Playlist (ArrayList): A music player where users mostly shuffle through songs by index and rarely add/remove songs → Use ArrayList.

Scenario 2 - Task Scheduler (LinkedList): A task list where tasks are frequently added to the beginning or removed from the end → Use LinkedList (implements Queue).

Scenario 3 - Browser History (LinkedList): Efficiently adding/removing history entries from both ends → Use LinkedList as Deque.

🏆 Best Practices

Best Practices for Choosing Between ArrayList and LinkedList

📊

Default Choice: Use ArrayList as your default choice unless you specifically need LinkedList's features.

⚡

Performance Test: For large datasets, test both implementations with your specific use case to determine the best performer.

🔗

Queue Operations: If you need Queue/Deque operations, consider using ArrayDeque instead of LinkedList for better performance.

💾

Memory Conscious: If memory is critical and you don't need frequent insertions/deletions, use ArrayList.