What are the differences between ArrayList and LinkedList?

Underlying Data Structures

The fundamental difference between these two list implementations lies in how they store data in memory. An ArrayList is backed by a dynamic array, which provides a contiguous block of memory to store elements. This structure allows for fast, index-based access because the exact memory address of any element can be calculated using a simple offset from the array's starting point. Conversely, a LinkedList uses a doubly-linked structure where each element is wrapped in a node object that contains references to both its predecessor and successor. Because nodes are scattered throughout the heap, the computer cannot jump directly to a specific index. Instead, the program must traverse the links one by one starting from either the head or the tail to reach a specific position. This architectural distinction defines almost every performance trade-off you will encounter in technical interviews regarding these collections.

import java.util.*;

public class DataStructureExample {
    public static void main(String[] args) {
        // ArrayList uses an underlying array
        List<String> arrayList = new ArrayList<>(Arrays.asList("A", "B", "C"));
        
        // LinkedList uses a chain of Node objects
        List<String> linkedList = new LinkedList<>(Arrays.asList("A", "B", "C"));
        
        System.out.println("ArrayList internal structure is a contiguous array.");
        System.out.println("LinkedList internal structure is a series of nodes.");
    }
}

Access Time Complexity

When we analyze performance, we use Big O notation to describe how the execution time grows relative to the input size. For an ArrayList, retrieving an element by its index is a constant time operation, denoted as O(1). Because the computer knows the memory address of the first index and the size of each element, it performs a simple calculation to reach any index instantly. This makes ArrayList the superior choice for read-heavy operations where you frequently access elements by their position. In contrast, reaching an element in a LinkedList is an O(n) operation in the worst-case scenario. Because there is no index-based memory calculation available, the machine must follow the 'next' pointers starting from the beginning of the list until it arrives at the target index. For very long lists, this linear traversal becomes prohibitively expensive, which is why developers should avoid LinkedList for index-heavy access patterns.

import java.util.*;

public class AccessComparison {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3));
        // O(1) time - direct memory calculation
        int val = list.get(1); 

        List<Integer> linked = new LinkedList<>(Arrays.asList(1, 2, 3));
        // O(n) time - traverses links to reach index 1
        int val2 = linked.get(1);
        System.out.println("Access values: " + val + ", " + val2);
    }
}

Insertion and Deletion Performance

Insertion and deletion performance reveals the hidden costs of managing memory. Adding an element to the middle of an ArrayList is an O(n) operation because all elements following the insertion point must be physically shifted in memory to maintain contiguity. If the array is full, it must also trigger a resize, which involves creating a larger array and copying every existing reference over to the new space. However, LinkedList insertions or deletions at a known position are O(1) once you have reached that node. Since the operation only requires updating a few reference pointers (the 'prev' and 'next' pointers of adjacent nodes), the structure does not need to move existing elements. This makes LinkedList highly efficient for scenarios like a queue or a sliding window where you are constantly modifying the ends of the list, provided you already have a reference to the node you are modifying.

import java.util.*;

public class MutationExample {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        // O(1) insertion: just update node references
        list.addFirst("New Task");
        list.addLast("Old Task");
        
        ArrayList<String> arr = new ArrayList<>();
        // O(n) insertion: requires shifting elements
        arr.add(0, "Important");
        System.out.println("List state: " + list + ", " + arr);
    }
}

Memory Overhead Considerations

Beyond execution speed, you must consider the memory footprint of your chosen collection. The ArrayList is more space-efficient because it stores only the object references in a continuous block of memory. The only overhead is the unused capacity of the array if it has not been filled to its current limit. On the other hand, a LinkedList is significantly heavier in terms of object allocation. Every single element inserted into a LinkedList must be wrapped in a specific 'Node' wrapper object. This wrapper holds the element data plus two reference fields—one for the previous node and one for the next node. For a list containing millions of items, the memory cost of these extra reference objects adds up quickly, leading to higher heap utilization and increased pressure on the garbage collector compared to the streamlined array approach used by the ArrayList.

import java.util.*;

public class MemoryOverhead {
    public static void main(String[] args) {
        // ArrayList stores references contiguously
        ArrayList<Integer> arr = new ArrayList<>();
        
        // LinkedList creates a new Node wrapper object for every item
        // Each Node stores: (item, next_ref, prev_ref)
        LinkedList<Integer> list = new LinkedList<>();
        
        arr.add(100);
        list.add(100);
        System.out.println("LinkedList creates internal objects for each element.");
    }
}

Selecting the Correct Implementation

In a professional software development environment, the decision between these two structures should be driven by the specific access patterns of your algorithm. You should default to using an ArrayList unless your performance profiling clearly indicates that your application performs a high volume of insertions or deletions from the middle or the beginning of a massive list. In modern hardware, the cache locality of an ArrayList—where elements are stored in physically adjacent memory locations—often makes it faster than a LinkedList even in scenarios where the theoretical complexity might suggest otherwise. The LinkedList is best suited for specific data structure implementations, such as a Deque, where you consistently add and remove items from the ends of the collection. Always prefer the simplicity and performance of an ArrayList for standard storage needs unless you have a rigorous requirement for the specialized insertion behavior of a linked structure.

import java.util.*;

public class SelectionStrategy {
    public static void main(String[] args) {
        // Use ArrayList as the default choice
        List<String> data = new ArrayList<>();
        data.add("Default choice for general use");
        
        // Use LinkedList for specialized scenarios like a Queue/Stack
        Deque<String> queue = new LinkedList<>();
        queue.offerFirst("Front");
        System.out.println("Strategy: Use ArrayList for speed and LinkedList for structure.");
    }
}

Interview questions

All java interview questions →

Check yourself

Take the full java quiz →