Difference Between ArrayList and LinkedList

Hey everyone, welcome back to the blog! Today, we’re going to compare two commonly used list implementations in Java—ArrayList and LinkedList. While they both implement the List interface, they behave quite differently under the hood. So, let’s break down their differences and see when you should use one over the other.”

Difference Between ArrayList and LinkedList

1. ArrayList uses a dynamic array vs. LinkedList uses a doubly linked list

“Let’s start with the structure. ArrayList internally uses a dynamic array to store its elements. This means it’s essentially a resizable array which can grow or shrink as needed. The elements are stored in contiguous memory locations.”

Example for ArrayList:

import java.util.ArrayList;

public class ArrayListStructureExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        System.out.println(arrayList); // Output: [A, B, C]
    }
}

Output:

[A, B, C]

“On the other hand, LinkedList internally uses a doubly linked list. Each element is stored in a node, and each node contains a reference to both the next and the previous element in the list. This allows easier insertion and removal of elements, but the elements are not stored in contiguous memory.”

Example for LinkedList:

import java.util.LinkedList;

public class LinkedListStructureExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        System.out.println(linkedList); // Output: [A, B, C]
    }
}

Output:

[A, B, C]

2. ArrayList manipulation is slower vs. LinkedList manipulation is faster

“When it comes to manipulation, ArrayList can be slower. When you remove an element from an ArrayList, all subsequent elements must be shifted in memory to maintain the contiguous structure, making operations like deletion or insertion at arbitrary positions expensive.”

Example for ArrayList Manipulation:

import java.util.ArrayList;

public class ArrayListManipulationExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("A");
        arrayList.add("B");
        arrayList.add("C");
        arrayList.remove(1); // Removing element at index 1 (B)
        System.out.println(arrayList); // Output: [A, C]
    }
}

Output:

[A, C]

“In contrast, LinkedList is faster for manipulation operations like adding or removing elements, especially in the middle of the list. Since it’s a doubly linked list, all it needs to do is adjust the pointers of the neighboring nodes. There’s no need to shift elements in memory.”

Example for LinkedList Manipulation:

import java.util.LinkedList;

public class LinkedListManipulationExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.remove(1); // Removing element at index 1 (B)
        System.out.println(linkedList); // Output: [A, C]
    }
}

Output:

[A, C]

3. ArrayList consumes less memory vs. LinkedList consumes more memory

“Memory consumption is another important difference. ArrayList consumes less memory compared to LinkedList because it only stores the data itself in a single block of memory.”

Example for ArrayList Memory Use:

import java.util.ArrayList;

public class ArrayListMemoryExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            arrayList.add(i);
        }
        System.out.println("ArrayList size: " + arrayList.size()); // Output: ArrayList size: 100
    }
}

Output:

ArrayList size: 100

“LinkedList, on the other hand, consumes more memory. This is because each element is stored in a node, and each node contains two additional references—one for the next element and one for the previous element.”

Example for LinkedList Memory Use:

import java.util.LinkedList;

public class LinkedListMemoryExample {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 100; i++) {
            linkedList.add(i);
        }
        System.out.println("LinkedList size: " + linkedList.size()); // Output: LinkedList size: 100
    }
}

Output:

LinkedList size: 100

4. ArrayList acts as a list only vs. LinkedList acts as both a list and a queue

“ArrayList can only act as a list because it implements the List interface. Its primary function is to store and manage ordered data, but it’s not designed to support queue operations efficiently.”

Example for ArrayList as List:

import java.util.ArrayList;

public class ArrayListAsListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("A");
        arrayList.add("B");
        System.out.println(arrayList.get(0)); // Output: A
    }
}

Output:

A

“In contrast, LinkedList can act as both a list and a queue because it implements both the List and Deque interfaces.”

Example for LinkedList as List and Queue:

import java.util.LinkedList;

public class LinkedListAsListAndQueueExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.addLast("B"); // Adding as a list
        linkedList.addFirst("C"); // Queue operation, adding at the front
        System.out.println(linkedList); // Output: [C, A, B]
    }
}

Output:

[C, A, B]

5. ArrayList is better for storing and accessing data vs. LinkedList is better for manipulating data

“If your main requirement is storing and accessing data efficiently, ArrayList is the better choice. Since elements are stored in contiguous memory, accessing any element by its index is fast and efficient—this happens in constant time.”

Example for ArrayList Access:

import java.util.ArrayList;

public class ArrayListAccessExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("X");
        arrayList.add("Y");
        System.out.println(arrayList.get(1)); // Output: Y
    }
}

Output:

Y

“On the other hand, LinkedList shines when you need to manipulate data frequently, especially if you need to insert or remove elements from the middle or ends of the list.”

Example for LinkedList Manipulation:

import java.util.LinkedList;

public class LinkedListManipulationExample2 {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("X");
        linkedList.add("Z");
        linkedList.add(1, "Y"); // Inserting in the middle
        System.out.println(linkedList); // Output: [X, Y, Z]
    }
}

Output:

[X, Y, Z]

Summary Table

Feature	ArrayList	LinkedList
Internal Structure	Dynamic array	Doubly linked list
Manipulation Speed	Slower for insertion/deletion	Faster for insertion/deletion
Memory Usage	Lower memory usage	Higher memory usage due to node references
Interface Support	Implements List	Implements List and Deque
Optimal Use Case	Storing and accessing data	Frequent insertion and deletion of elements

Conclusion

That wraps up our comparison of ArrayList and LinkedList! To sum up: ArrayList is great for data storage and access, while LinkedList excels at manipulating data. I hope this helped you understand the key differences between these two data structures.