Scalable Human Blog

An ArrayList and a LinkedList are both data structures used to store a collection of elements, but they have some key differences in terms of their implementation and performance.

ArrayList	LinkedList
Implemented as a dynamic array	Implemented as a doubly-linked list
Fast random access to elements by index	Fast insertion and removal of elements anywhere in the list
Slow insertion or removal of elements in the middle of the list	Slow access to elements by index

ArrayList Example

import java.util.ArrayList;

public class Example {
    public static void main(String[] args) {
        // Create an ArrayList of Strings
        ArrayList<String> names = new ArrayList<String>();
        
        // Add some elements to the ArrayList
        names.add("John");
        names.add("Mary");
        names.add("Bob");

        // Access an element by index
        System.out.println("Second name is: " + names.get(1));

        // Insert an element at a specific index
        names.add(1, "Mike");
        System.out.println("After adding Mike, the list is: " + names);

        // Remove an element by index
        names.remove(2);
        System.out.println("After removing the third element, the list is: " + names);

        // Remove an element by value
        names.remove("John");
        System.out.println("After removing John, the list is: " + names);

        // Check if an element exists in the list
        boolean containsMary = names.contains("Mary");
        System.out.println("Is Mary in the list? " + containsMary);

        // Get the size of the list
        int size = names.size();
        System.out.println("The list contains " + size + " elements.");
    }
}

ArrayList Methods:

• add(element): Adds an element to the end of the list.
• add(index, element): Inserts an element at the specified position in the list.
• set(index, element): Replaces the element at the specified position in the list with the specified element.
• get(index): Returns the element at the specified position in the list.
• remove(index): Removes the element at the specified position in the list.
• remove(element): Removes the first occurrence of the specified element from the list.
• clear(): Removes all elements from the list.
• contains(element): Returns true if the list contains the specified element, otherwise returns false.
• size(): Returns the number of elements in the list.
• isEmpty(): Returns true if the list contains no elements, otherwise returns false.
• iterator(): Returns an iterator over the elements in the list.
• toArray(): Returns an array containing all of the elements in the list in proper sequence.
• subList(fromIndex, toIndex): Returns a view of the portion of the list between the specified fromIndex, inclusive, and toIndex, exclusive.
• trimToSize(): Trims the capacity of this ArrayList instance to be the list’s current size.
• ensureCapacity(minCapacity): Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

LinkedList Example

import java.util.LinkedList;

public class Example {
    public static void main(String[] args) {
        // Create a LinkedList of Integers
        LinkedList<Integer> numbers = new LinkedList<Integer>();
        
        // Add some elements to the LinkedList
        numbers.add(5);
        numbers.add(10);
        numbers.add(15);

        // Access an element by index
        System.out.println("Second element is: " + numbers.get(1));

        // Insert an element at the beginning
        numbers.addFirst(3);
        System.out.println("After adding 3, the list is: " + numbers);

        // Insert an element at the end
        numbers.addLast(20);
        System.out.println("After adding 20, the list is: " + numbers);

        // Remove the first element
        numbers.removeFirst();
        System.out.println("After removing the first element, the list is: " + numbers);

        // Remove the last element
        numbers.removeLast();
        System.out.println("After removing the last element, the list is: " + numbers);

        // Check if an element exists in the list
        boolean containsTen = numbers.contains(10);
        System.out.println("Does the list contain 10? " + containsTen);

        // Get the size of the list
        int size = numbers.size();
        System.out.println("The list contains " + size + " elements.");
    }
}

LinkedList Methods:

• add(element): Adds an element to the end of the list.
• addFirst(element): Inserts an element at the beginning of the list.
• addLast(element): Inserts an element at the end of the list.
• get(index): Returns the element at the specified position in the list.
• set(index, element): Replaces the element at the specified position in the list with the specified element.
• remove(index): Removes the element at the specified position in the list.
• removeFirst(): Removes the first element in the list.
• removeLast(): Removes the last element in the list.
• contains(element): Returns true if the list contains the specified element, otherwise returns false.
• size(): Returns the number of elements in the list.
• iterator(): Returns an iterator over the elements in the list.
• descendingIterator(): Returns a descending iterator over the elements in the list.
• offer(element): Inserts the specified element at the end of the list.
• poll(): Retrieves and removes the head of the list, or returns null if the list is empty.
• peek(): Retrieves, but does not remove, the head of the list, or returns null if the list is empty.

Also P.S. Not an exhaustive list!

When to use a LinkedList?

• You need to frequently insert or remove elements from the middle of the list. Because a LinkedList is implemented as a doubly-linked list, adding or removing an element only requires updating the references in the previous and next elements, which is a very fast operation.
• You need to iterate through the list in both directions. A LinkedList provides a next() and previous() method that allows you to iterate through the list in both directions, whereas an ArrayList only allows you to iterate in one direction.
• You have a lot of element insertion and removal but not many random access, due to its implementation a LinkedList is not efficient in terms of random access, and it can be slow comparing to other data structures like ArrayList.
• You need a Queue implementation. LinkedList is also a implementation of the Queue interface, which means you can use its methods like add(), offer(), remove(), poll() and peek() to implement a queue data structure.
• You need a Deque implementation. LinkedList is also a implementation of the Deque interface, which means you can use its methods like addFirst(), offerFirst(), removeFirst(), pollFirst() and peekFirst() to implement a double ended queue data structure.

Keep in mind that depending on the scenario, other data structures such as ArrayList, Vector, or even custom data structures may perform better for a specific use case.

When to use an ArrayList?

• You need to frequently access elements by index. Because an ArrayList is implemented as a dynamic array, it provides fast O(1) random access to elements by index.
• You have a lot of random access but not many element insertion and removal. ArrayList is efficient in terms of random access, but it can be slow when comparing to other data structures like LinkedList when it comes to insertion or deletion of elements.
• You need a List implementation. ArrayList is an implementation of the List interface which means you can use its methods like add(), remove(), get(), set() to implement a List data structure.
• You need a stack implementation. ArrayList can be used to implement a stack data structure, by using its methods like add(), remove() and get() you can use it as a stack.
• You don’t need to worry about thread-safety. ArrayList is not synchronized, which means it may not be suitable for use in a multithreading scenario. If you need a thread-safe version of an ArrayList, you can use the Vector class which is similar to ArrayList but is synchronized.

It is worth noting that, depending on the scenario, other data structures such as LinkedList, HashTable, or even custom data structures may perform better for a specific use case.

📚 Further Reading & Related Topics

If you’re exploring the differences between ArrayList and LinkedList in Java, these related articles will provide deeper insights:

• Java 16 and the Standardization of Records: Simplifying Data Classes – Explore how Java continues to refine its data structures, such as records, to simplify code and improve performance.

• Exploring Java 17’s Enhanced Pseudo-Random Number Generators (PRNG): A Dive into JEP 356 – Learn how Java is evolving its core features, such as randomness and data structure performance, alongside ArrayLists and LinkedLists.