What are the main differences between LinkedList and ArrayList in Java?

The main differences between LinkedList and ArrayList lie in their internal data structures and, consequently, in the performance of various operations:

Internal structure:

• ArrayList uses a dynamic array to store elements.
• LinkedList uses a doubly linked list, where each node contains data and references to the previous and next nodes.

Operation performance:

Operation	ArrayList	LinkedList	Reason
Adding to the end	O(1)	O(1)	ArrayList usually has space, LinkedList easily adds a new tail.
Adding at the beginning or middle	O(n)	O(1)	ArrayList requires shifting elements. LinkedList only needs to change a few links.
Removing from the end	O(1)	O(1)	No shifting occurs in ArrayList. LinkedList easily removes the tail.
Removing from the beginning or middle	O(n)	O(1)	ArrayList requires shifting elements. LinkedList only needs to change a few links.
Accessing element by index	O(1)	O(n)	ArrayList provides direct access by index. LinkedList requires traversal.
Searching for an element	O(n)	O(n)	Both require scanning the entire list.

Memory usage:

• LinkedList generally consumes more memory due to storing additional references to previous and next nodes.

Applicability:

• ArrayList is preferred when frequent access to elements by index and adding/removing at the end are common.
• LinkedList is preferred when frequent addition and removal of elements from the beginning or middle of the list are needed.

Example: Adding at the beginning

// ArrayList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add(0, "First"); // O(n) - shifting existing elements

// LinkedList
LinkedList<String> linkedList = new LinkedList<>();
linkedList.addFirst("First"); // O(1) - just changing references