Understanding ArrayList and LinkedList

⏱ Estimated reading time: 2 min

Java provides dynamic data structures through the Collections Framework, and ArrayList and LinkedList are two widely used List implementations. They allow ordered storage of elements, can grow dynamically, and provide various utility methods.

1. ArrayList

Definition

• ArrayList is a resizable array implementation of the List interface.

• Maintains insertion order and allows duplicate elements.

• Provides fast random access using index.

Features

• Dynamic resizing when capacity exceeds.

• Allows null elements.

• Implements Serializable and Cloneable interfaces.

• Slower insertion/deletion in the middle of the list due to element shifting.

Example:

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        ArrayList list = new ArrayList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");
        
        System.out.println("ArrayList: " + list);
        list.remove(1); // Remove element at index 1
        System.out.println("After removal: " + list);
    }
}

Output:

ArrayList: [Java, Python, C++]
After removal: [Java, C++]

2. LinkedList

Definition

• LinkedList is a doubly-linked list implementation of the List and Deque interfaces.

• Maintains insertion order and allows duplicate elements.

• Better for frequent insertions and deletions.

Features

• Each element (node) contains data and pointers to previous and next nodes.

• Implements Queue and Deque interfaces, supporting FIFO operations.

• Slower random access compared to ArrayList (requires traversal).

Example:

import java.util.LinkedList;

public class Test {
    public static void main(String[] args) {
        LinkedList list = new LinkedList<>();
        list.add("Java");
        list.add("Python");
        list.addFirst("C#"); // Insert at beginning
        list.addLast("C++"); // Insert at end
        
        System.out.println("LinkedList: " + list);
        list.removeFirst(); // Remove first element
        list.removeLast();  // Remove last element
        System.out.println("After removal: " + list);
    }
}

Output:

LinkedList: [C#, Java, Python, C++]
After removal: [Java, Python]

3. Comparison: ArrayList vs LinkedList

4. Key Points

• Both ArrayList and LinkedList are part of java.util package.

• Both maintain insertion order and allow duplicate elements.

• Choose ArrayList for fast random access.

• Choose LinkedList for frequent insertion and deletion operations.

5. Conclusion

ArrayList and LinkedList are powerful list implementations in Java. Understanding their internal workings and performance characteristics helps in choosing the right data structure for specific scenarios, improving efficiency and scalability in Java applications.