Difference Between ArrayList and LinkedList

by

ArrayList and LinkedList are two popular implementations of the List interface in Java. While both of these classes implement the List interface and provide similar functionality, there are some key differences between them.

  1. Data Structure: ArrayList is internally backed by an array. This means that elements are stored in contiguous memory locations, and accessing an element by index is very fast. On the other hand, LinkedList is implemented as a doubly linked list. This means that elements are not stored in contiguous memory locations, and accessing an element by index is slower compared to ArrayList. However, inserting or removing an element in the middle of a LinkedList is faster than doing the same operation on an ArrayList.
  2. Insertion and Removal: As mentioned earlier, insertion and removal operations are faster in a LinkedList as compared to an ArrayList. This is because in a LinkedList, only the pointers of the affected nodes need to be updated, whereas in an ArrayList, all the elements after the insertion/removal point need to be shifted by one position.
  3. Random Access: Accessing an element by index is faster in an ArrayList as compared to a LinkedList. This is because ArrayList provides constant time O(1) access to any element by its index, while LinkedList provides linear time O(n) access to an element by its index.
  4. Memory Overhead: LinkedList uses more memory than ArrayList as it has to maintain pointers to the next and previous elements in the list, whereas ArrayList only needs to maintain the elements themselves.

In summary, use ArrayList when you need fast random access to elements by index and when the number of elements is known in advance. Use LinkedList when you need fast insertion and removal of elements, especially if the list is large and you don’t need to access elements by index frequently.

Example of ArrayList and LinkedList in Java:

Here are examples of ArrayList and LinkedList in Java:

Example of ArrayList:

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // create an ArrayList of integers
        ArrayList<Integer> numbers = new ArrayList<>();

        // add elements to the ArrayList
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);

        // print the ArrayList
        System.out.println("ArrayList: " + numbers);

        // remove an element from the ArrayList
        numbers.remove(3);

        // print the updated ArrayList
        System.out.println("Updated ArrayList: " + numbers);
    }
}

Example of LinkedList:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // create a LinkedList of strings
        LinkedList<String> names = new LinkedList<>();

        // add elements to the LinkedList
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("Dave");

        // print the LinkedList
        System.out.println("LinkedList: " + names);

        // remove an element from the LinkedList
        names.remove(2);

        // print the updated LinkedList
        System.out.println("Updated LinkedList: " + names);
    }
}

In both examples, we create a list (either ArrayList or LinkedList), add elements to it, remove an element, and then print the list before and after the removal.

Points to Remember:

Here are some important points to remember about ArrayList and LinkedList in Java:

  1. ArrayList and LinkedList both implement the List interface in Java.
  2. ArrayList is backed by an array, while LinkedList is implemented as a doubly linked list.
  3. ArrayList provides constant time O(1) access to an element by index, while LinkedList provides linear time O(n) access to an element by index.
  4. Insertion and removal of elements are faster in LinkedList compared to ArrayList.
  5. Accessing elements by index is faster in ArrayList compared to LinkedList.
  6. ArrayList is a better choice when you need fast random access to elements by index, while LinkedList is a better choice when you need fast insertion and removal of elements, especially if the list is large and you don’t need to access elements by index frequently.
  7. ArrayList uses less memory compared to LinkedList as it only needs to maintain the elements themselves.
  8. Both ArrayList and LinkedList support the add, remove, get, and size methods, as well as many other List interface methods.
  9. When iterating over a LinkedList, it is usually better to use an Iterator rather than a for loop, as the performance of the latter can be poor due to the O(n) access time.
  10. When iterating over an ArrayList, it is usually better to use a for loop rather than an Iterator, as the former can take advantage of the O(1) access time.