ArrayList vs LinkedList in Java

-

Java’s Collections Framework provides two commonly used List implementations: ArrayList and LinkedList. While both implement the List interface, they differ in their underlying data structures, performance, and use cases. Let’s break down their differences with examples and diagrams.

1. Underlying Structure

  • ArrayList → Backed by a dynamic array. Elements are stored in contiguous memory.
  • LinkedList → Implemented as a doubly-linked list. Each node stores data + pointers to the previous and next node.

Diagram:

ArrayList (Dynamic Array)
[ 0 ] → [ 1 ] → [ 2 ] → [ 3 ] → [ 4 ]
(index based access)

LinkedList (Doubly Linked Nodes)
NULL ← [0 | *] ↔ [1 | *] ↔ [2 | *] ↔ [3 | *] → NULL

2. Code Example

ArrayList Example:

import java.util.*;

public class ArrayListExample {
    public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // Random access is fast
        System.out.println("Element at index 1: " + list.get(1));
    }
}

LinkedList Example:

import java.util.*;

public class LinkedListExample {
    public static void main(String[] args) {
        List list = new LinkedList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // Insertion at the beginning is efficient
        list.add(0, "Go");

        System.out.println("First Element: " + list.get(0));
    }
}

3. Performance Comparison

Operation ArrayList LinkedList
Random Access (get) O(1) ✅ O(n) ❌
Insertion / Deletion at end O(1) (Amortized) O(1)
Insertion / Deletion in middle O(n) O(n) (but O(1) if iterator used)
Memory Usage Less overhead More overhead (extra node pointers)

4. When to Use What?

  • Use ArrayList when you need fast random access and memory efficiency.
  • Use LinkedList when your application requires frequent insertions and deletions in the middle or at ends.

Rule of Thumb: If you’re unsure, start with ArrayList. It is generally faster and more commonly used in real-world applications.

5. Quick Benchmark (Conceptual)

ArrayList get(index):  O(1) → very fast
LinkedList get(index): O(n) → slower as size grows

Example with 1M elements:
- ArrayList get(500000) ≈ nanoseconds
- LinkedList get(500000) ≈ milliseconds

Conclusion

Both ArrayList and LinkedList have their place in Java development. However, due to cache locality, memory efficiency, and overall speed, developers tend to prefer ArrayList in most scenarios. Reach for LinkedList only if your problem domain specifically benefits from frequent insert/delete operations in the middle of the list.

Comments

Post a Comment

Popular posts from this blog

Spring Boot on AWS EC2: Upload to S3 Securely Using IAM Role

-
When running a Spring Boot application on AWS EC2 , the most common security mistake is hardcoding AWS access keys inside application.properties . This is unnecessary and risky. AWS already provides a secure mechanism: IAM Roles attached to EC2 . In this blog, you will learn how to upload and download files to Amazon S3 from Spring Boot running on EC2 without any access keys , using: Spring Profiles AWS SDK v2 Instance Metadata Service (IMDS) IAM Roles Why Access Keys Are a Bad Idea on EC2 Typical S3 setups use: Access key Secret key Region Bucket This works only for local development. It should NOT be used on EC2. Problems with access keys: Stored in config or code (high risk) Might leak through Git, logs, or screenshots Require manual rotation Not needed if app runs on EC2 AWS automatically manages temporary credentials using the EC2 Instance Profile (IAM Role) . Architecture: EC2 → IAM Role → S3 Spring Boot app r...
Read more

Java Streams Intermediate Operations Explained with Examples

-
Image
The Java Stream API lets you process collections in a fluent, declarative style. In this post, we’ll walk through the most useful intermediate operations with simple examples. Note: Examples below use Java 8 compatible collect(Collectors.toList()) . If you’re on Java 16+, you can replace it with toList() . 1) filter() — Select elements by a condition Keeps only elements that match the predicate. List<Integer> list = Arrays.asList(1,2,3,4,5,6,7,8,9,10); List<Integer> res = list.stream() .filter(num -> num % 2 != 0) // keep only odd numbers .collect(Collectors.toList()); System.out.println(res); // [1, 3, 5, 7, 9] 2) map() — Transform each element Applies a function to every element and returns a stream of results. List<String> strs = Arrays.asList("rama", "anjaneya", "krishna"); List<String> upper = strs.stream() .map(String::toUpperCase) .collect(Collectors.toList()); System.o...
Read more

ConcurrentHashMap vs Synchronized HashMap in Java

-
Image
Introduction In multi-threaded Java applications, managing shared data safely and efficiently is crucial. Two common approaches are using Synchronized HashMap (via Collections.synchronizedMap(...) ) and ConcurrentHashMap . While both aim to provide thread-safety, their implementations and performance characteristics differ significantly. This post explores these differences in detail. What is a Synchronized HashMap? Created by wrapping a regular HashMap using: Map<K, V> syncMap = Collections.synchronizedMap(new HashMap<>()); Enforces synchronization at the object level , meaning only one thread can access the map at any time (read or write). Supports null keys and values since it relies on HashMap behavior. Iterators are fail-fast , throwing ConcurrentModificationException if the map is modified while iterating. Simpler implementation, suitable when concurrency is low or performance is not cri...
Read more